ALGORITHM (5) 썸네일형 리스트형 백준 2564번 경비원 문제 이해 블록의 가장자리로만 이동이 가능할 때, 동근이와 각 상점까지의 최소 거리의 합을 구하는 문제다. 위의 그림에서 동근이는 X, 상점은 1, 2, 3이다. 상점 1까지의 최소 거리는 12, 2까지는 6, 3까지는 5이고 그 합은 23이다. 풀이 설명 동근이가 있는 면을 기준으로 왼쪽이나 오른쪽 면에 있는 상점들까지의 최소 거리는 각각 왼쪽으로 가는 길, 오른쪽으로 가는 길이다. 하지만 반대편에 있는 상점은 동근이를 기준으로 왼쪽으로 도는것과 오른쪽으로 도는 것 중 하나가 최소 거리다. 입력은 동서남북을 각각 4, 3, 2, 1로, 해당하는 면에서 상점의 위치는 가로면은 왼쪽부터, 세로면은 위쪽부터의 거리로 주어진다. 그렇기 때문에 동근이가 어떤 면에 있느냐에 따라 계산 식이 달라진다. 하지만 위의.. 백준 5014번 스타트링크 문제 이해 총 F층으로 이루어진 건물의 G층에 스타트링크가 위치한다. 강호는 현재 S층에서 G층으로 이동하려 한다. 엘리베이터는 위로 U층 올라가는 버튼, 아래로 D층 내려가는 버튼 두 가지다. 강호가 G층에 도착하기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약 엘리베이터로 G층까지 이동할 수 없다면 "use the stairs"를 출력한다. 풀이 설명 step이라는 배열을 두고, step[s]부터 시작해서 위, 아래로 이동하며 step[n]에 n층까지 이동하는 데 눌러야 할 최소 버튼 수를 저장하는 방법을 사용했다. 해결 방법은 다음과 같다. 1. F의 최댓값인 1,000,000 + 1 크기로 step 배열을 두고, -1로 초기화한다. 2. step[S]에 0을 저장하고 (S는 강호가 이동을.. 백준 1107번 리모컨 문제 이해 이동하고 싶은 채널 번호가 주어지면 그 채널까지 이동하는 데 리모컨 버튼을 최소 몇 번 눌러야 하는지를 구하는 문제다. 리모컨 버튼은 0에서 9까지의 숫자 버튼, -버튼, +버튼이 있고, 채널은 0부터 무한대까지 있다. 숫자버튼 중 몇 개의 버튼은 고장이 나 있을수도 있다. 현재 채널은 100이다. 이동하고 싶은 채널 N이 주어지면, 고장이 나지 않은 버튼의 조합으로 N과 같거나 가장 가까운 숫자를 만든 뒤, N채널까지 -나 +버튼을 통해 이동하는 것이 최소로 버튼을 누르는 방법이다. 풀이 설명 주어진 버튼으로 N을 만들지 못하는 경우 가장 가까운 숫자를 만들어야 하는데, 어떻게 그걸 만드느냐가 문제다. 손으로 푸는 것처럼 숫자를 만들자니 고려해야 할 것들이 너무 많아 완전 탐색을 통해 해결했.. 백준 1476번 날짜 계산 문제 이해 3개의 수 E, S, M으로 나타낸 연도를 우리가 알고 있는 연도로 몇 년인지 구하는 문제다. E, S, M의 범위는 각각 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19이고, 1년이 지날 때 마다 각 수에 1을 더한다. E는 1에서 15까지의 숫자가 반복되는 것이고, S는 1에서 28까지의 숫자가, M은 1에서 19까지의 숫자가 반복되는 것이다. 예를 들어, 1 1 1년은 1년이고, 15 15 15는 15년, 1 16 16은 16년이다. 이 문제는 연도 - E = 15의 배수, 연도 - S = 28의 배수, 연도 - M = 19의 배수라는 것을 활용하면 된다. (참고) 증명 E = 1, S = 2, M = 3이고, 정답년도는 year라고 하자. E에 E의 최대범위인 15를 더하.. 백준 1167번 트리의 지름 문제 이해 처음에는 트리와 그래프를 혼동했던 것 같다. 그래서 아래와 같은 상황이 발생할 수 있다고 생각하여 트리의 모든 경로를 검사하는 코드를 짰더니 시간 초과가 발생했다. 그런데 트리는 그래프와는 다르게 여러 노드가 한 노드를 가리킬 수 없다 (위키백과). 그러므로 이 문제의 경우 1. 한 노드에서부터 탐색을 하며 가장 먼 노드를 찾은 뒤, 2. 다시 그 노드부터 탐색을 하며 가장 먼 거리를 찾으면 된다. (참고) 증명 트리의 지름은 언제나 리프노드 사이에서 존재한다. 임의의 노드에서 가장 먼 리프 노드를 먼저 찾은 후, 그 리프 노드에서 가장 먼 리프노드까지의 거리가 트리의 지름이다. 아래와 같은 트리가 있다고 하자. 탐색의 시작 노드를 4번으로 했을 때, 가장 먼 리프 노드는 7번이고 거리는 11.. 이전 1 다음
