공부하자

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 간단한 문제인거 같은데, 생각보다 많이 헤맸다... 일단 가중치 없는 그래프 탐색이니 BFS 문제로 갈피를 잡고 들어갔으나, 각 인덱스 마다 계속 BFS를 하는것으로 방향을 잡고 풀다가 계속 틀렸다. 이유인 즉, 자식노드가 복수일 경우에는 해당 방법으로는 절대 부모노드를 구할 수 없기 때문이다. 따라서, 그냥 루트 노드 1에서부터 BFS를 한번만 돌리는 방향으로 바꾸어 풀었다. 처음에 왜 이 생각을 못했을까 싶다. 생각해보면 정말 당연한건데 말이다. 부모노드를..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #1697 숨바꼭질의 연장선상에 있는 문제이다. 숨바꼭질 3는 아예 다익스트라로 노선을 변경해서 풀면 그나마 풀어냈었는데, 2는 오히려 같은 BFS 코드를 공유하는 문제인지라, 방법을 생각해내는것에 더 어려움을 겪었다. 일단 문제 자체는 가중치가 없는 그래프를 탐색하여 최단거리를 도출해야 하기 때문에 BFS를 이용해 풀었고, 기존 #1697에서 썼던 코드를 일..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이전에 작성했던 #1697 숨바꼭질 문제의 연장선상에 있는 문제이다. 당시엔 가중치가 없는 그래프에서 최단 경로를 찾는 형식이었기에, BFS를 이용해서 해결했었지만, 이번엔 가중치가 새로 생겼다. 걸어가는 경우와 순간이동을 하는 경우 두가지 경우의 가중치가 다르기 때문에 BFS가 아닌 다익스트라를 이용하여 문제를 풀어야 한다. 필자가 기존에 다익스트라를 활용하..

https://www.acmicpc.net/problem/25757 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 실버5 난이도라 매우 쉽다. 중복제거 매커니즘만 알고있으면 5분만에 풀수 있을 정도다. 입력받은 사람들의 명단에서 중복되는 값들을 제거 한 후, 중복 없는 자료구조의 크기만큼 케이스에 따라 1이나 2나 3으로 나눠주면 된다. 다만 여기서, "임스는 한 번 같이 플레이한 사람과는 다시 플레이하지 않습니다." 라는 조건이 있기 때문에, 한번 플레이한 사람은 ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net #1697 숨바꼭질과 매우 비슷한, 따로 인접리스트나 그래프를 순회하지 않고 최단거리를 구하는 형태의 문제이다. 거의 똑같은 매커니즘을 공유한다고 보면 되는데, 굳이 다른점이라고는 세부 조건과 출력형식이 다르다는 것...? 이전에 풀었던 문제를 복기하며 한번 더 풀어보았다. 항상 BFS를 이용할때에 명심할 점은, 한번 방문했던 케이스는 visited 배열에 저장되므로 다시 방문할 필요성이 없다는 것 이다. 이..

https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 그간 계속 그래프 탐색 문제들 위주로만 풀다가 오랜만에 기본 구현 문제를 풀어보았다. 백준 문제집에 "IT기업 및 대기업 계열사 코테보면서 비슷했던 문제들" 이란 이름의 문제집이었는데, 정말 실제 코테에 나올법한 문제들이 많은 것 같았다. 이미 풀었던 문제들도 몇몇 있었는데, 이 문제는 이번에 처음 풀어봤다. 난이도 자체는 실버5여서 오 금방 풀겠는데? 하고 시작했다가 의외로..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #1012 유기농 배추와 똑같은 문제이다. 하나 다른점이라고 하면 입력받은 행렬에 대해 상하좌우 뿐만 아니라 대각선 방향까지 접근해서 탐색을 돌려야 한다는 것. 그 부분 말고는 딱히 어려운 점이 없었다. 오랜만에 BFS 문제를 풀어보니 잘 기억이 나지 않는 부분이 있었다. 분명 다익스트라 풀때보다 매커니즘 자체는 더 쉬운데,,, 아직 몸에 익숙하지 않아서 그런 것 같다. #include #i..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐에 관련된 간단한 예제이다. 입력되는 인덱스들의 절댓값이 더 작은 원소들을 출력하고, 절댓값이 같다면 실제 인덱스 값이 더 작은 (쉽게 말해 양수와 음수중 음수를 출력) 값을 출력하면 된다. 이 매커니즘을 구현하려면 먼저 우선순위 큐 라는 자료구조를 알고 있어야 한다. 우선순위 큐에 대한 내용은 다음 게시글에서 자세하게 작성해 놓았다. https://jhoon-st..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이번 문제는 왕복 경로에 대한 다익스트라 수행에 대한 내용이다. 보통 다익스트라 라고 함은, 방향성 그래프에서 시작점과 도착점에 대한 경로의 최소비용을 구하는 알고리즘이다. 하지만 이 문제는 특정 경유지를 제시해주고, 시작점에서 출발하여 경유지를 경유한 다음 다시 원점으로 돌아오는 왕복 경로에 대한 탐색을 요구한다. 문제에서 요구하는 조건이 얼핏보면 복잡해 보이지만 ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 활용하는 기초중의 기초 문제다. 문제에서 요구하는대로 입력을 받아 다익스트라 알고리즘을 통해 도시간의 최소비용을 구해서 출력하기만 하면 된다. 필자는 다익스트라 알고리즘 구현에 배열 자료구조 대신 우선순위큐를 활용하여 구현하였다. 다익스트라를 구현할때에는 배열을 사용하는 것보다 우선순위큐를 사용하는것이 훨씬 좋다. 정점의 개수를 V, 간선의 ..