PS
11660 - 구간 합 구하기 5
이 문제는 2차원 누적 합을 잘 사용해야 하는 문제이다. 문제 내용을 살펴보면, $N \times N$ 크기의 2차원 표를 입력받아 $M$개의 2차원 구간합을 구하는 것이 목표이다. 그런데 만약 표를 입력받아 순회하며 합을 구하는 브루트포스 방식으로 단순히 구현하면 최악의 경우 100000 1024 1024번(1천억 번) 연산하므로 시간초과가 날 것이다...
15552 - 빠른 A+B
이 문제는 PS 언어를 자바로 바꾸면서 빠른 입출력을 연습하기 위해 푼 문제이다. 가끔 시간복잡도에 문제가 없음에도 입출력 과정에서 시간이 많이 걸려 TLE를 받는 경우가 있기 때문에, 빠른 입출력을 쓰는 습관을 기르는 것이 좋다.
1991 - 트리 순회
이 문제는 이진 트리 순회 방법을 연습하는 문제이다. 문제 설명에도 나와있지만, 이진 트리를 순회하는 방법에는 크게 preorder, inorder, postorder 방식이 있다. preorder의 경우는 root-left-right, inorder은 left-root-right, postorder은 left-right-root 순으로 순회하게 된다. 참...
20055 - 컨베이어 벨트 위의 로봇
이 문제는 제시한 과정을 코드로 구현해 작동 과정을 시뮬레이션하여 답을 구해야 하는 시뮬레이션 문제이다.
2606 - 바이러스
전형적인 그래프 탐색 문제이다. 1번 컴퓨터가 바이러스에 먼저 감염되면, 1번 컴퓨터와 네트워크로 인접한 컴퓨터들이 바이러스에 감염되게 된다. 마찬가지로 x번 컴퓨터가 바이러스에 감염되면, x번 컴퓨터와 인접한 모든 컴퓨터들은 바이러스에 감염된다. 즉 먼저 감염된 1번 컴퓨터를 시작으로 dfs나 bfs를 통해 인접한 컴퓨터들을 탐색하면 되는 문제이다.
1914 - 하노이 탑
🔗 수학적 귀납법을 통한 재귀를 사용하면 풀 수 있는 문제이다.