본문 바로가기

분류 전체보기

 (84)
백준 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..
AtCoder : ABC 178 D - Redistribution atcoder.jp/contests/abc178/tasks/abc178_d D - Redistribution AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 이 문제 역시 대표적인 형식의 DP문제이다. 앞선 포스팅에서 살펴본 간단한 DP문제들은 이전 히스토리에서 한 개나 두 개 정도를 참조하여 현재의 값을 구하였다 (기본 피보나치 수열은 이전 값 2개를 참조하여 현재의 값을 구한다). 하지만 이번에는 꽤나 많은 값을 가져와야 한다. 수열의 합이 S가 되고, 각 수는 3이상이므로 첫 수는 항상 3부터 시작해서 따져봐도 좋다..
AtCoder : ABC 178 C - Ubiquity atcoder.jp/contests/abc178/tasks/abc178_c C - Ubiquity AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp DP문제이다. 점화식을 파악할 수 있다면 쉽고 간단한 문제겠지만, 그게 떠오르지 않는다면 역시 어렵다... 이러한 문제에 대해 어떻게 접근해야 할까? 이전 포스팅들에서 꾸준히 얘기하고 있지만, 필자가 이해하는 동적계획법(DP) 적용의 근거는 어떠한 정점(상황)에서 일정한 규칙을 적용하여 일정한 간격만큼 떨어진 다음 정점으로 넘어갈 때에 있다. 어떠한 정점에서 연결된 정점이 한 ..
Codeforces Round #667 (Div.3) Problem - D codeforces.com/contest/1409/problem/D Problem - D - Codeforces codeforces.com 이 문제는 숫자가 매번 증가하기만 할 뿐이라는 점에 착안해야 한다. 27이라는 숫자가 있을 때, 각 자리에 있는 숫자들은 2와 7이다. 그리고 그들의 합은 9. 지금부터 편의상 9를 27의 '숫자합'이라고 부르겠다. 7이라는 숫자가 있다고 한다면, 7에서 1을 증가시키면 8이 된다. 8은 7보다 숫자합이 크다. 8에서 또 1을 증가시키면 9가 되고. 9의 숫자합은 8의 그것보다 크다. 여기까지 보면, 숫자를 1씩 증가시키기 때문에 숫자합은 점점 커질 뿐이다. 하지만! 수가 길어질 때 (자릿수가 하나 더 생겼을 때) 드디어 숫자합은 작아질 수 있다. 방금 전 예시의 9..

티스토리툴바