문제 https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제. 단순히 모든 도로들 중 K개의 도로들을 선택하여 cost를 0으로 만든다면, 모든 조합의 최대 수는 Combination(50000 , 20) 일 것이다. 이는 절대 시간안에 계산해낼 수 있는 수치가 아니다. 따라서 다익스트라를 진행하면서 방문하게 되는 간..

문제 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 풀이 solved.ac 난이도: Gold 3 다익스트라를 두 번 적용해야 했던 문제. 다익스트라는 최단 경로 알고리즘 중에서 단일 시작점 알고리즘으로 하나의 시작점에서 다른 모든 점까지의 거리를 구한다. 하지만 문제에서는 파티가 진행되는 마을을 도착점으로 하고, 다른 모든 점에서 해당 점을 향해 최단 경로로 이동해야한다. 그렇다면, 반대로 파티 마을을 시작점으로..

문제 https://algospot.com/judge/problem/read/HANOI4 algospot.com :: HANOI4 하노이의 네 탑 문제 정보 문제 하노이의 탑은 세 개의 기둥에 꽂혀 있는 N개의 원반을 가지고 하는 게임입니다. N개의 원반은 크기가 모두 다르며, 게임의 시작 때는 그림과 같이 맨 왼쪽의 기둥 algospot.com 풀이 종만북 난이도: 중 재귀 함수 문제의 대표 격인 하노이 탑 문제에 기둥을 1개 더 추가하여 4개인 상태로 해결하는 문제이다. 이번 문제의 핵심은 각 기둥에 꽂혀있는 원판들의 상태를 어떻게 저장하느냐이다. 단순히 4개의 기둥들이 어떤 원판을 가지는지 stack을 사용하여 표현한다면 4개의 스택(각각의 기둥)을 가지는 구조체로 나타낼 수 있을 것이다. 1 2 ..

문제 https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 풀이를 생각해내는 것은 어렵지 않았지만 구현이 까다로웠던 문제이다. 일단 모든 좌표를 정점으로 만드는 것은 수직선과 수평선이 최대 100,000개이기 때문에 시간 초과는 물론 메모리도 초과해버린다. 하지만 버스의 수는 최대 5000개로 모든 버스를 충분이 정점으로 표현해낼 수 있는 수치이다. 따라서 버스들 ..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 일반 BFS 문제 [백준] 스타트링크(5014) - Gold5 [백준] 숨바꼭질 2(12851) - Gold5 [백준] 버스 갈아타기(2536) - Gold1 [백준] 환승 (5214)★ + 더미노드 - Gold1 [알고스팟] Sorting Game(SORTGAME)★ - 중 [알고스팟] 어린이날(CHILDRENDAY)★★ - 상 양방향 탐색(Bidirectional serach) [알고스팟] 하노이의 네 탑(HANOI4)★ +양방향 탐색 해설 - 중

문제 https://algospot.com/judge/problem/read/CHILDRENDAY 풀이 종만북 난이도: 상!! 상당히 어려운 BFS 문제이다. 문제를 보면 생각나는 간단한 풀이는 자릿수를 사용해 모든 경우의 수를 생성해 보는 것이지만 당연히 시간 초과가 발생한다. 일단 다음의 두 가지 조건만을 만족하는 최소 자연수 C를 구하는 방법을 생각해보자. (어린이의 수를 children_num, 욕심쟁이의 수를 greedy_num이라고 하자.) C를 children_num으로 나눈 나머지는 greedy_num이다. C는 d에 포함된 숫자들로만 구성된다. 이를 구하기 위해서 나머지 연산의 분배 법칙을 이용하자. (A*B) mod n = ((A mod n) * (B mod n)) mod n 따라서 다..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 이전 문제인 [백준] 숨바꼭질(1697)의 다음 단계 문제입니다. 이전 문제는 단순히 BFS를 적용하면 풀 수 있었지만 이번에는 최단 시간으로 도달하는 방법 수 까지 구해야합니다. 각 위치의 최단 시간은 수빈이의 시작 위치로 부터 BFS를 하여 도달할 때의 탐색 깊이를 의미합니다. 만약 해당 위치로의 경로가 여..

문제 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 단순히 같은 하이퍼 튜브로 연결된 역들을 양방향 간선으로 이어 문제를 해결하면 시간 초과 또는 메모리 초과가 발생하는 문제였다. 그 이유는 최대 개수인 1000개의 역이 서로 연결된다면 양방향 간선으로 연결 시, 약 1,000,000(=1000^2) 개의 간선이 생성된다. 여기에 최대 1000개의 하이퍼 튜브가 존재한다면..

문제 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 풀이 solved.ac 난이도: Gold 5 간단한 BFS 문제. 시작하는 층, S에서 G까지 도달할 수 있는 최소 버튼 push 수를 구해야 한다. 이는 최단 거리를 구하는데 특화된 BFS의 영역이다. 특정 층 floor에서 위(floor + U) 또는 아래(floor - D)층으로 이동할 때 이미 방문했다면 해당 층으로 갈 수 있는 최단 push는 이미 구했으므로 더 이상 계산할 필요가 없다. 하지만..

문제 https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com 풀이 종만북 난이도: 중 BFS문제들은 2차원 좌표상에서 이동하는 문제가 많은데 이번 문제는 전혀 다른 BFS 적용 문제라 신선했다. (그리고 어려웠다...) 1 2 3 4 수열의 구간들이 반전되어 나타나는 수열은 다음과 같이 그래프로 표현이 가능하다. 각 노드들은 1 2 3 4에서 한 구간 만을 반전시킨 것이므로 1번의 뒤집기 연산으로 이동..