겜돌이의 개발일지

개요 자신보다 큰 값(혹은 작은 값)이 언제 처음 오는지에 대해 구해야 할 때, 가장 쉽게 떠올릴 수 있는 방법은 2중 for 문을 쓰는 것이다. 예를 들어 다음과 같이 숫자가 있다고 할 때 3 4 1 5 2 각각의 숫자에 대해 그 수보다 큰 수가 처음 등장하는 인덱스(0부터 시작)를 나타내면 다음과 같다. num : 3(1) 4(3) 1(3) 5(x) 2(x) 2중 포문을 사용하게 되면, n개의 원소에 대해 시간 복잡도는 O(n^2)이다. 이를 스택을 사용하면 한 번만 순회를 돌면서, 즉 O(n)만에 자신보다 큰 인덱스를 찾을 수 있다. Monotonic Stack monotonic stack의 원리는 간단하다. stack에 들어있는 원소가 내림차순(혹은 오름차순)이 되게 정리만 해주면 된다. 1. 즉..

개요 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면, 플로이드-와샬 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 이차원 배열을 사용해 최소값을 계속 저장해두기 때문에, 다이나믹 프로그래밍 기법의 일부로도 볼 수 있다. 설명 A에서 B로 가는 최소 비용과 A에서 C를 거쳐 B로 가는 최소 비용을 비교한다. 다음과 같은 비용을 가지는 양방향 그래프가 있다고 가정하다. 초기값을 먼저 표시하면 다음 표와 같다. 1을 지날 때 다음 영역을 갱신 해줘야 한다. 4 -> 1-> 5 (반대도 같음)의 비용이 14이므로 INF에서 갱신해준다. 2를 지날 때 3 -> 2 -> 4 (반대도 같음)의 비용이 7로, 기존의 비용 8보다 더 저렴하..

문제 백준 14890 경사로 C++ 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이해 자체는 어렵지 않은 문제였다. 1. 이차원 배열에 값을 넣어주고 2. 행 / 열을 검사하면서 경사로를 놓을 수 있는지 확인한다. 경사로를 놓을 수 있는지 확인하는 과정은 다음과 같다. 1. 현재 값과 다음 값의 차를 구한다. 2-1) 차가 0인 경우 : 평지이므로 다음 구역으로 넘어간다. 2-2) 차가 1인 경우 : 현재가 더 높다. 따라서 내리막길이 필요하므로 다음 구역부터 그 다음 구역으로 가면서 내리막길을 설치할 수 있는 지 확인한다...

문제 백준 2343 기타 레슨 C++ 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 조건을 보고, 이분 탐색으로 해결할 수 있음을 유추해야 합니다. 순서를 변경하면 안 되고, 모든 동영상을 포함해야 하므로 mid 값에 대해 이분 탐색을 실행합니다. 조건을 만족하면 더 작을 mid 값을, 조건을 만족하지 못한다면 더 큰 mid값을 찾습니다. 길이의 합이 int 범위를 넘어설 수 있으므로 long long으로 선언해주고, mid 값의 최대는 100,000 * 10,000 = 10억이므로 범위에 유의합니다. 58%..

문제 백준 2805 나무 자르기 C++ 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 전형적인 이분 탐색 문제입니다. low = 0, high는 나무의 최대 높이로 설정한 뒤, mid 값을 바꿔가며 이분 탐색을 시행합니다. low > high 조건을 만족하기 전의 result 값이 최종결과가 됩니다. sum은 int 범위를 초과할 수 있으므로 long long 타입으로 설정합니다. 한편, N의 최대 개수가 백만이라 시간초과가 나지 않을까 걱정했지만, C++은 N ..

개요 분기 한정법은 백트래킹 기법과 같이 상태 공간 트리를 구축하여 문제를 해결하는 방법이다. 최적 해를 구하는 문제에 주로 사용된다. 원리 마디를 검색할 때마다, 마디가 유망한 지 여부를 결정하기 위해서 한계값(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까지의 최단 거리를..