본문 바로가기

Problem Solving/백준

 (56)
백준 2352 반도체 설계 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 이 문제는 이런 유형을 아예 처음 보았다면 이것이 LIS인지 쉽게 떠올리기 어려울 수도 있다. LIS에 대한 내용은 이전 포스팅에서 정리해두었으니 참조 부탁드린다. 위와 같이, 1에서 시작한 선은 4로 연결되고, 3에서 시작한 선은 6에서 끝난다. 그 시작점과 끝점을 두줄에 걸쳐 나열하였다. 윗줄에 1, 2, 3, 4, 5, 6을 굳이 쓴 이유는 출발점이 증가하는 순서대로 나열되어있다는 것을..
백준 19238 스타트 택시 (삼성 기출) www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 약간의 자료구조 설계와 BFS를 주로 사용하여 해결할 수 있다. 항상 그렇듯이, 이러한 구현 문제는 문제의 조건을 신경 써서 잘 읽고, 흐름과 스토리를 잘 파악해야 한다. 주요한 조건들은 아래와 같다 - 승객을 고를 때는 최단거리에 있는 승객을 선택한다. - 승객마다 가고자 하는 목적지가 있고, 거기까지는 무조건 이동한다. (그 승객의 목적지가 멀다고 승차거부 등을 하지 ..
백준 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..
백준 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 해주기 - 연..

티스토리툴바