본문 바로가기

Problem Solving/백준

 (56)
백준 1005 ACM Craft www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 이 문제는 알고리즘 & 자료구조 카테고리에 기록한 이전 포스팅을 반드시 참조하기 바란다. 건물을 짓는 순서들은 모두 모아 사이클이 없는 단방향 그래프로 구성해 볼 수 있다. 위상정렬 후에 앞에서부터 건설 시간을 넘겨주면 된다. 그리고 각 정점에서는 부모 정점에서 내려오는 값들 중 최댓값만 취하여 갱신해주면 된다. 그렇게 목표 건물까지 누적하면 답을 구할 수 있다 위상정렬, DP #include #incl..
백준 13325 - 이진 트리 www.acmicpc.net/problem/13325 13325번: 이진 트리 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 �� www.acmicpc.net 이 문제는 이진트리를 다루는 방법을 익히기에 좋은 문제라고 생각한다. 이진트리에서는 하나의 노드가 단 2개의 자식 노드만 가질 수 있다. 보통 1. 자식노드들에서 부모 노드로 올라올 때 어떠한 처리를 통해서 2개의 자식 노드가 가지는 값들을 합치거나, 나누거나, 평균값을 구하거나 등의 처리를 하는 경우가 있고, 2. 반대로 부모노드에서 자식 노드로 내려갈 때, 어떠한 처리를 통해 나눠주거나 하는 메커..
백준 2133 - 타일 채우기 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 이 문제는 다이나믹 프로그래밍의 대표적인 유형 중 하나인 타일 채우기 관련 문제이다. 타일을 채우는 방식에서 어떠한 규칙성을 찾아 적용시키면 된다. 이 문제도 필자가 이전 포스팅들에서 여러 번 말했듯이 각 정점에서 일정한 규칙을 계속 적용시킬 수 있기에, 정점과 정점 간 각기 다른 간선을 가지는 그래프가 아니라 DP문제임을 생각해 볼 수 있다. 이 문제는 가로변의 길이가 홀수이면 채울수 있는 경우가 없다. 그 점은 조금만 생각해보면 알 수 있다. 가로길이가 짝수인 경우만 생각한다. 일단 3X2의 공간을 채우는 방법부터 살..
백준 1562 - 계단 수 www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 비트마스킹, 다이내믹 프로그래밍, 재귀+메모, 분할 정복이 모두 들어있는 좋은 문제다. 위의 그림은 문제의 내용을 표현한다. 계단 수여야 하므로 이전보다 하나 작거나 큰 수가 이번에 온다. 맨 위의 123454의 경우에는 그 다음에 3,5 두 개의 수가 올 수 있다. 즉, 2가지로 갈래가 나눠진다. 789 다음에는 8만 가능하다 3210 다음에는 1만 가능하다. 여기까지 파악된 것은 N자리의 숫자를 만들어야 하고, 현재 수를 알면 다음 수가 뭐가 되는지 알 수 있다는 점이다. 이제 중요한 것은 0부터 9까지 모든 숫자가 나왔는지이다...
백준 3151 - 합이 0 www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 이 문제는 이전 포스팅에서 다루었던 백준 2473 - 세 용액 문제의 살짝 업그레이드 버전이라고 생각한다. 세 용액 문제에서는 0에 가까운 값을 찾기만 하면 되기 때문에 가장 가까운 인덱스들만 확인하면 되었다. 하지만 이번에는 0이 되는 모든 경우의 수를 합산해야 한다. 물론 그냥 전부 확인하려면 시간 초과가 나게 된다. 이번에도 이분탐색과 정렬의 힘을 활용하자! 문제의 예제에 대한 설명은 문제에 잘 되어있으므로, ..
백준 2473 - 세 용액 www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이 문제는 알고리즘 & 자료구조를 공부한다면, 반드시 한 번쯤은 거쳐가고, 거쳐야만 하는 기본적(?)이면서도 중요한 문제라고 생각한다. 그리고 다양한 풀이가 있을 수 있어서 좋다. 위의 그림은 문제에서 주어진 예제를 다루고 있다. 항상 그렇듯이 이 문제에서도 정렬의 힘을 다시 느낄 수 있다. 입력을 받은 후 정렬하고, 총 3개의 수를 뽑아야 하므로 루프 2개로 2개를 뽑아준다 (여기까지 O..
백준 2075 N번째 큰 수 www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 정렬 또는 우선순위 큐를 통해 해결할 수 있다. 문제의 메모리 제한을 눈여겨 보자. 12MB로 평소와 다르다. int형 정수 1개는 4byte를 갖는다고 한다. 1천개면 4kb이고, 1백만개면 4MB이니 12메가 바이트는 겨우 3백만개의 정수만 담을 수 있는 것이다. 문제의 조건에서 N이 1500이므로 1500 x 1500 = 2,250,000 (225만)개의 정수가 필요하므로 다 담을 수 있을 것 같지만,..
백준 1654 랜선 자르기 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이 문제 또한 이분탐색의 기본적인 문제이다. 문제에서 보면 랜선의 길이는 최대 2^31-1까지 될 수 있다고 했는데 이는 int 범위 내에서 가장 큰 값이다. 이처럼 이분탐색 문제는 어마어마한 범위를 주는 경우가 많다. 어차피 몇 번만 탐색하면 전 범위를 다 볼 수 있기 때문이다. 이분탐색 문제를 몇 개 풀고 나면 이분탐색의 기본 포맷이 잡힐 것이다. 아래와 같다. 먼저 문제의 상한..

티스토리툴바