다이나믹 프로그래밍(동적 계획법) 이란? 다이나믹 프로그래밍은 재귀에 대한 최적화이다. 이말은 중복된 부분에 대한 문제가 있다면, 이에 대한 결과를 저장해둔다. 그리고 동일한 부분에서의 문제가 다시 발생한다면, 이 결과를 재사용하는 방법이다. 이런 사례는 피보나치 수열에서 쉽게 찾아볼 수 있다. 피보나치 수열의 점화식은 다음과 같다. f(n) = f(n - 1) + f(n - 2) 이때 n = 4라고 한다면, f(4) = f(3) + f(2) 를 구해야 하는데, 이때 전에 구해두었던 f(3) 과 f(2)의 값을 다시 구하지 않고 저장해두었다가 다시 사용하는 것을 의미한다. 특징 커다란 문제를 나누어 해결하는 편이다. 앞서 말했듯이, 이전에 풀었던 문제와 동일한 문제일 경우, 다시 연산 하는 것이 아니라 ..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구해야 한다. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 풀이 방식 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 다음 n = 5일때 다음과 같은 삼각형이 있다고 하자. 다음 풀이의 핵심은 이전 값의 계산을 ..

백트래킹 이란? 완전 탐색을 하던 도중, 현재의 탐색이 무의미한 경우 되돌아가는 알고리즘을 의미한다. 말 그대로 모든 경우의 수에 대해서 탐색을 하던 도중, 조건과 맞지 않을 경우에 대해서는 탐색을 하지 않고 돌아간다는 뜻이다. 유명한 문제로 N-Queens 문제가 존재한다. 특징 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다. 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에, 재귀를 사용해야 하는 경우가 많다. 조건에 맞지 않는 다면, 이전의 어떤 지점으로 돌아갈 지 정하는 것이 중요하다. 가지치기를 어떻게 구성하느냐에 따라 코드의 효율이 달라진다. 주로 백트래킹을 구현하다 보면, void함수와 전역 변수를 쓰면 쉽게 풀리는데 이는 다른 알고리즘에서 자중하..

문제 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 문제 설명 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 풀이 방식 처음엔 (모든 색종이의 넓이 - 중복된 넓이) 이런 방식을 통해 답을 구하려고 하였다. 하지만 이 방법이 간과한 부분은 n장의..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 오름차순의 수열을 구하는 프로그램을 작성해야 한다. 풀이 방식 A = { 70, 30, 50, 60, 70, 0, 10} 다음과 같은 수열이 있다고 하자. brute force식으로 구해보면 다음과 같다. 어떻게 해도 이 블로그 보다 설명을 잘 할 수 없으니 모르겠다면 참고 하도록 하자. 백준 11053번 가장 긴 증가하는 부분 수열 파..

문제 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 N개의 자연수와 자연수 M이 주어 졌을때, 다음 조건을 만족하는 길이가 M인 수열을 모두 구하면 됨. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 개인적으로 문제를 파악하기엔 중복 순열을 구하되, 비내림차순 조건을 만족하면 되겠다고 생각하고 문제를 푼 것 같다. 풀이 방식 내가..

문제 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 설명 아래와 같은 조건으로 나열하면 된다. 1. 길이가 짧은 것 부터 2. 길이가 같다면 사전 순으로 3. 중복은 제거한다. 풀이 방식 알고리즘 적으로 적어둘만 한건 없는 것 같다. 솔루션 #include #include #include using namespace std; bool compare(string a, string b) { if (a.length() != b.length()) return a.length() < b.length(..

문제 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 설명 봄보니 (Bomboni) 게임. N x N 크기의 랜덤한 사탕으로 채워져있는 판이 있다. 사탕 색이 다른 인접두 칸을 고른 뒤, 두 칸의 사탕을 교환한다. 마지막으로, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다. (뭐, 대충 옛날 애니팡 같은 게임 규칙.) 풀이 방식 이 문제는 brute force 방식 즉, 모든 방법을 다 탐색해야 한다. 1. 우선 (i, j)와 (i, j+1)의 위치를 바꾼다. 2. 그 다음엔 모든 row에 대해서 조..