문제 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번의 뒤집기 연산으로 이동..

문제 https://www.acmicpc.net/problem/10265 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 SCC로 새롭게 구성한 컴포넌트 별로 최대, 최소 인원을 파악해 배낭 문제로 값을 구해야 했던 문제로 굉장히 어려웠다.. 일단 인원 마다 같이 가고 싶은 인원(pick)을 가리키도록 그래프로 표현해보자. 1번 인원이 2번 인원과 가고 싶다면 다음과 같이 표현된다. 관계를 이런식으로 나타냈을 때 예제의 입력인 12 3 2 3 4 5 6 7 4 7 8 8 12..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 DSF문제 중에서도 그리디 알고리즘으로 해결하는 문제이다. 항상 최선의 선택을 하는 그리디 방식으로 이번 문제를 해결하면, 다음의 세 가지 경로 선택 중에서 다음과 같은 우선순위를 정하면 된다. 1. 오른쪽 위를 방문 2. 오른쪽을 방문 3. 오른쪽 아래를 방문 이런 식으로 오른쪽 위를 항상 먼저 방문한다면 생성되는 파이프 라인을 최대한 오른쪽 위로 밀착시킬 수 ..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 2-SAT 해설 [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 2-SAT 문제 목록 [백준] 2 - SAT - 3(11280) - Platium 4 [백준] 2 - SAT - 4(11281)★ + 답 출력하기 - Platium 3 [백준] 아이돌(3648)★ - Platium 4 [백준] 호텔 관리(16915) + 식 세우기 -Platium 3