겜돌이의 개발일지

개요 분기 한정법은 백트래킹 기법과 같이 상태 공간 트리를 구축하여 문제를 해결하는 방법이다. 최적 해를 구하는 문제에 주로 사용된다. 원리 마디를 검색할 때마다, 마디가 유망한 지 여부를 결정하기 위해서 한계값(bound)을 계산한다. 한계값이 현재까지의 최적의 해보다 좋지 않으면 유망하지 않은 것이다. 이 마디는 더 이상 검색할 필요가 없다. 위 그림은 최소 등산 코스를 찾는 과정 중 하나이다. 이미 80이라는 최적의 해를 찾은 상태에서 최소 100, 200의 거리를 갖는 등산로 A, B를 조사할 필요는 없다. 즉, A와 B는 유망하지 않다. A와 B 중에서 A가 더 작은 값을 가질 수 있으므로, A 먼저 조사하는 것이 좋다. 위 그림은 반대로 최대 가치의 보물을 찾는 과정이다. 이미 180이라는 최..

개요 N-queens 문제는 N * N 체스판에 N개의 퀸을 서로 공격받지 않게 놓는 방법의 개수를 구하는 문제이다. 예시 n = 4일 때 정답의 개수를 구해보자. 먼저 각 열에는 한 개의 퀸을 놓을 수 있다. 무작정으로 놓을 수 있는 모든 경우에 수를 고려하면 다음과 같다. 총 4 * 4 * 4 * 4 = 256가지의 경우에 대해 놓을 수 있는지 각각 검사해야 한다. 하지만 (2, 1)에 퀸을 놓는 순간 조건을 만족하지 않으므로 이후 자식 노드들은 검사하지 않아도 된다. 따라서 백트래킹을 활용하면 검사해야 하는 가짓 수를 줄일 수 있다. 스도우 코드 상태공간트리 예제 코드(C++) n을 입력받아 n * n 체스판에서 n개의 퀸을 놓을 수 있는 총 방법의 개수를 출력하는 코드 1 2 3 4 5 6 7 8..

개요 0-1 배낭 문제는 n개의 물건에 대해 최대 가치가 되도록 담는 알고리즘이다. 시간복잡도 분석 각각의 물건은 넣는다 / 넣지 않는다의 2개의 경우가 있으므로 단순히 시간 복잡도를 계산하면 O(2^n)이다. Dynamic Programming으로 해결 i > 0이고 w > 0일 때, 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고 이익을 P[i][W]라고 하면 P[i][W]는 다음과 같이 구할 수 있다. 이 알고리즘의 시간복잡도는 이다. W = 10이고, 품목이 다음과 같을 때의 0-1 배낭 문제 예시 문제점 불필요한 항을 계산한다. (위 그림에서 P[3][8]과 P[3][9]를 구할 필요는 없다.) 위 그림의 경우 총 n(4) * W(10)의 40번의 비교가 필요하다. 아래와 같..

개요 허프만 코드란 최적 이진 코드를 만드는 알고리즘 중 하나이다. Fixed-length binary code 코드의 길이가 고정적이다. ex) a : 00, b : 01, c : 11 등 문제점 : 자주 나타나는 코드의 길이도 고정이므로 낭비가 생긴다. Variable-length binary code 코드의 길이가 가변적이다. ex) a : 10, b: 0, c : 11 등 자주 나타나는 코드의 길이를 줄일 수 있다. 문제점 : 위의 예시에서 d를 00으로 표기하는 방법을 추가하면 00이 d인지, bb인지 구별할 수 없어진다. optimal binary code (최적 이진 코드) 주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드이다. Prefix code 한..

개요 다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서, 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제이다. 알고리즘의 단계는 다음과 같다. 1. F는 공집합으로 둔다. 2. Y(최단 경로가 확정된 집합)에는 시작 정점 v1을 포함해 {v1}으로 둔다. 3. 최종해답을 얻을 때까지 다음 과정을 반복한다. (a) 선정 절차 / 적정성 점검 : V-Y에 속한 정점 중에서, v1에서 Y에 속한 정점만을 거쳐서 최단 경로가 되는 v를 선정한다. (b) v를 F에 추가한다. (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검 : Y = V가 되면 T = (V, F)가 최단경로를 나타내는 그래프가 된다. 예시 초기화 : v1에서 v2~v5까지의 최단 거리를..

문제 백준 2667 단지번호붙이기 (C++) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 일반적인 BFS / DFS 문제입니다. 이차원배열을 탐색하면서, 방문하지 않았다면 bfs를 시행합니다. 근처에 1인 지역들을 모두 탐색해 cnt로 반환합니다. cnt를 result vector에 넣어주고 정렬합니다. 그 후 result vector의 원소들을 하나씩 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 백준 1260 DFS와 BFS (C++) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 탐색의 가장 기본 of 기본 문제입니다. 주어진 조건에 따라 V부터 DFS 및 BFS를 실행하고, node를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..

문제 백준 15654 N과 M (5) C++ 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 n과 m (1)에서 출력값이 1 ~ n 이었다면 n과 m (5)는 사용자 입력을 받아 출력을 해야한다. 알고리즘이 바뀌는 건 없다. 백트래킹을 사용하여 순열을 출력하면 된다. 단 출력 시에는 1 ~ n을 출력하는 것이 아니라 사용자 입력을 받아 오름차순으로 정리한 vector를 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

문제 백준 13335 트럭 C++ 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 풀이 트럭이 순차적으로 다리를 건너므로(FIFO) 큐를 이용한다. 3단계로 나눠서 풀면 편하다. 다리 위로 안 올라간 트럭들의 Queue와 다리 위에서 움직이고 있는 트럭 Queue 다리 위에서 움직이고 있는 트럭의 거리를 1증가시켜줄 임시 Queue 3개를 선언한다. 1단계 - 이미 다리 위에 있는 트럭들을 모두 1칸 앞으로 이동시킨다. 1-1 : 이 때 트럭이 다리를 건넜으면, ..

1. 간선 정렬 2. 가중치 낮은 간선 부터 이어줌. 3. 두 노드가 이미 선택되었다면 이어주지않고 패스