본문 바로가기

Problem Solving

 (67)
백준 4196 도미노 www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 본 블로그 SCC관련 포스팅에서 num값이 크면 가장 멀리 있는 정점까지 도달할 수 있는 가능성이 있다고 하였다. 약간 위상정렬에서 순서가 가장 앞서는 정점에서 시작해야 모든 정점을 돌 수 있는 것처럼, SCC를 찾을 때 첫 번째 DFS에서 매겨둔 num값 중 가장 큰 값에서 시작하면 가장 멀리 갈 가능성이 있다. (절대 항상 그런건 아니다. 주의!) 이 도미노 문제는 어떠한 블록을 넘어뜨리면 가장 멀리 가는 경우 (또는 가장..
백준 6543 그래프의 싱크 www.acmicpc.net/problem/6543 6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net 이 문제는 SCC를 활용할 수 있는 문제이며, 본 블로그 내의 SCC 관련 포스팅을 꼭 같이 참조하기 바란다. 이 문제는 SCC를 찾기만 하는 게 아니다. SCC를 이루는 요소에서 다른 정점 어디라도 갈 수 있는데, 돌아오지 못한다면 답이 아니게 된다. 위의 그림은 이전 SCC포스팅에서 사용한 그림이다. 위와 같은 그래프에서는 1-2-3이 원래 SCC를 이루지만, 3에서 4와 5도 갈 수 있고, 4와 5에서는 1..
백준 17142 연구소 3 (삼성 기출) www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이 문제도 삼성 문제의 유명한 연구소 시리즈 중 하나이다. 이런 격자구조가 나오면 항상 BFS/DFS/DP 등을 생각하게 되는데, 이 문제도 BFS로 풀었다. 다만 조합을 끼얹어야 한다. 바이러스를 놓을 수 있는 위치들은 맵 상에 표시되어있고, 그 중에서 가장 빠른 확산을 일으킬 수 있는 최적의 M개를 골라야 하는데, 이 M개 선택에 있어 순서는 중요하지 않다. 그래서 순열이 아니라 조합이 된다. 조합에 대해서는 N과 ..
백준 17144 미세먼지 안녕! (삼성 기출) www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 전형적인 구현 및 시뮬레이션 문제이다. 구현 및 시뮬레이션 문제를 풀 때는, (사실 모든 문제가 마찬가지지만) 주어진 조건을 잘 파악하여야 한다. 그리고 중복되는 부분이나 자주 호출되는 부분이 있는지 확인해보고, 예외 상황 등을 파악한다. 그리고 모듈화 (함수나 클래스 등으로 코드의 일정 단위를 묶어주는 등)를 잘해주어야 한다. 보통 이런 격자구조가 나오면 기본적으로 좌, 우, 위, 아래 탐색을 해주는 BFS..
AtCoder: ABC 180 D atcoder.jp/contests/abc180/tasks/abc180_d D - Takahashi Unevolved AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 곱셈과 덧셈을 통해서 숫자를 키워줄 수 있고, 상한선을 넘지 않는 한에서 가장 많은 횟수의 연산을 하여야 한다는 것이 문제의 조건이다. 곱셈을 하면 숫자가 급격히 커지므로, 일정 수 이상이 되면 (혹은 아예 처음부터) 곱셈을 한 결과는 항상 덧셈을 한 결과보다 크게 된다. 즉, 곱셈을 먼저 할 수 있는 만큼 하고(그나마 처음에 숫자가 작을 때) 곱셈을 한 결..
백준 1948 임계경로 www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 이 문제는 위상정렬로 풀 수 있는데, 조금 더 생각할 부분이 있다. 최장거리는 구할 수 있지만, 최장거리를 만드는 경로의 개수를 세는 부분이다. 사실 최장거리를 구하기 위해 꼭 위상정렬을 할 필요는 없으나, 그 방법을 소개하고자 한다. 위상정렬을 모른다면 반드시 본 블로그내의 관련 포스팅을 참조하기 바란다. 위의 그림과 같이, 각 정점에 들어오는 간선의 개수 (indegree)를 정리..
백준 2252 줄 세우기 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 위상 정렬로 풀이되는 대표적인 문제 중의 하나이다. 입력이 pair로 주어지며, (a,b)를 받아서, 아래와 같이 그래프를 구성한다. cin>>a>>b; graph[a].push_back(b); indegree[b]++; 입력을 모두 받은 후, indegree값이 0인 값들을 모두 큐에 집어넣고 (BFS 돌리듯이) 하나씩 빼면서 - 위상정렬된 벡터 등에 push 해주기 - 연..
백준 1005 ACM Craft www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 이 문제는 알고리즘 & 자료구조 카테고리에 기록한 이전 포스팅을 반드시 참조하기 바란다. 건물을 짓는 순서들은 모두 모아 사이클이 없는 단방향 그래프로 구성해 볼 수 있다. 위상정렬 후에 앞에서부터 건설 시간을 넘겨주면 된다. 그리고 각 정점에서는 부모 정점에서 내려오는 값들 중 최댓값만 취하여 갱신해주면 된다. 그렇게 목표 건물까지 누적하면 답을 구할 수 있다 위상정렬, DP #include #incl..

티스토리툴바