2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 읽기 해당 문제는 최단 경로를 구하는 문제라 판단하고 그리 어렵지 않을 것이라 생각했다. 하지만 20퍼센트 쯤에서 본 “틀렸습니다”라는 문구..!! 일단 문제 풀이를 시작해보자. 문제 풀기 NxM 크기의 일반적인 맵에 0으로 표현된 빈 칸, 1로 표현된 벽이 존재한다. 0, 0에서 N-1, M-1까지 가는 최단 거리를 찾으면서, 그 중에서 벽 한 개는 뚫을 수 있다. 이는 크게 어렵지 않게 생각했다. 최단 거리이기 때문에 DFS와 ..

1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 읽기 일단 해당 문제는 트리.. 이지만 잊지 말아야 할 것은 트리도 어쨌든 그래프라는 것이다. 이 문제를 풀기 위해서 어떻게 할 지 고민하다가, 처음에는 플로이드 워샬이 생각났다. 모든 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이기에, 이를 조금 수정하면 최장 거리를 구하는 것도 할 수 있을 것이라 생각했다. 그래서 알고리즘을 다시 살펴봤는데, 시간 복잡도가 V^3이라 어림도 없었다. (해당 문제에서 V = 10000이다) 두..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 읽기 해당 문제는 트리의 아주 기초적인 문제이다. 최근 트리 문제를 많이 풀지 못해서 어제 코테를 쳤는데 기초적인 트리 문제를 제출하지 못했다! 이게 너무 아쉬워서 오늘부터는 트리 문제를 중점적으로 풀어보려 한다. 문제 풀기 해당 문제에서 주어지는 트리는 이진 트리이다. 처음에 트리를 어떻게 저장할 지 고민하다가, 이전에 많이 사용했던 class 방식을 사용하기로 했다. 문제 풀이 과정은 크게 다음과 같다. 트리를 저장할 자료구조를 정의한다. 트..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 읽기 일단 해당 문제를 읽고 나서는 완전 탐색 말고는 딱히 방법이 떠오르지는 않았다. 그래서 DFS와 BFS를 생각했고, DFS는 깊이 우선 탐색이라 끝이 없을 것 같아서.. 백퍼 시간 초과 날 거 같았다. 그래서 최소 연산의 개수를 구하는 것이기 때문에 BFS를 바로 적용해서 해결했다. 문제 풀기 문제는 크게 어렵지 않다. 주어진 명령어마다 요구사항에 따라서 정확하게 구현한다면 틀리지는 않을 것이다. 또한 같은 숫자로 또 탐색하지 않도록 하기..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 읽기 처음 문제를 읽었을 때는 시간 제한이 6초이고, T의 범위가 나와있지 않아서 좀 당황했었다.. 어쨌든 문제를 해결하려는데, 저번에 IOIOI를 풀었을 때처럼 한 번에 연산이 되는 게 아니라서 생각을 좀 했었다. 문제 풀이는 다음과 같은 과정을 통해 이루어졌다. ArrayList 1개와 이진 삽입 정렬 - 시간 초과 우선순위 큐 2개와 Map - OK TreeMap 사용하기 - Good 문제 풀기 ArrayList 1개와 이진 삽입 정렬 - 잘못된 ..

6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 읽기 최근 코테를 쳐보고 나니 어떤 문제라도 시간 복잡도를 고려하면서, 정확하게, 그리고 한 번에 푸는 연습을 해야 할 필요성을 느꼈다. 그래서 티어는 그리 높지 않지만 정답 비율이 낮은 클래스 문제들부터 하나씩 풀고 있다! 문제 풀기 그럼 해당 문제를 분석해보자. 이 문제는 처음에는 하나씩 증가/감소 시키는 방법이 떠오를 것이지만, M과 N의 크기를 봤을 때 그렇게 완전 탐색으로는 절대 불가능하다. M = 4만, N = 4만이므로, 숫자가 매우 크다. (이때..