문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 재귀를 사용해 풀었습니다. 현재 구역의 색상이 모두 같으면 해당 색상을 출력합니다. 만약 다르다면 4개의 구역으로 분할하고 재확인해 괄호와 함께 출력합니다. 재귀를 이용하여 색상이 다르면 계속해서 분할하여 확인하게 됩니다. 코드 자바 import java.util.*; import java.io.*; public class Main { public static char[][..

문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 전화번호 목록을 정렬합니다. 그러면 전화번호 목록의 앞뒤의 시작이 같은지만 확인하면 됩니다. 코드 파이썬 import sys input = sys.stdin.readline def solution(): for i in range(n-1): if phone_num[i+1].startswith(phone_num[i]): return "NO" return "YES" t..

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 DFS(깊이 우선 탐색)를 사용해 풀었습니다. 양방향 간선이므로 graph의 부모, 자식 노드에 해당하는 공간에 서로를 가중치와 함께 추가합니다. 트리의 지름을 구하는 방법은 다음과 같습니다. 루트 노드로부터 거리가 가장 먼 노드를 구합니다. 구한 노드로부터 거리가 가장 먼 노드까지의 거리를 구합니다. 코드 파이썬 import sys sys.setrecursionli..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 BFS(너비 우선 탐색)를 사용해 풀었습니다. 아기 상어의 위치(baby_shark)를 찾아 해당 위치의 값을 0으로 바꾸고 위치를 저장합니다. BFS 함수 내의 fish 리스트에는 같은 거리 상에 있는 먹을 물고기들을 저장합니다. 상하좌우를 확인하며 0 혹은 같은 크기의 물고기는 지나가고, 아기 상어보다 작은 물고기를 fish 리스트에 추가합니다. 만약 먹을 수 있는 물고기가 ..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 visited는 앞서 방문한 위치를 체크하여 재방문하지 않도록 하고, 경로 및 이동 거리를 저장합니다. visited를 벽 부수기 전후로 나누어 체크합니다. visited[x][y][0] : 벽 부수기 전 경로 visited[x][y][1] : 벽 부수기 후 경로 이동할 위치의 이동 거리를 현재 위치의 이동 거리에 1을 더해 구합니다. 코드 파이썬 import ..

문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 DFS(깊이 우선 탐색), 백트래킹을 사용해 풀었습니다. check 배열을 사용해 같은 알파벳이 적힌 칸을 두 번 지날 수 없도록 합니다. ord 함수를 사용해 알파벳을 0~25의 값을 가지도록 합니다. 처음엔 딕셔너리를 사용해 알파벳을 체크해줬다. 그런데 계속 시간초과가 떠서 찾아보니 딕셔너리는 시간복잡도가 최소 O(1)에서 최대 O(n)까지 가능하다고 하여 리스트 인덱싱으로 ..