Kwin's Development Diary.

0-1 배낭 문제 (Knapsack Problem) : 담을 수 있는 무게의 최댓값이 정해진 배낭에 일정한 가치와 무게가 정해져 있는 짐들을 골라 배낭에 담기는 최대의 가치를 구하는 문제 특징 ① 동적 계획법(다이나믹 프로그래밍, DP : Dynamic Programming)으로 해결할 수 있다. ② 다른 버전으로는 물건을 쪼갤 수 있는 Fraction Knapsack Problem이 있다. 알고리즘 ① 물건의 정보를 표에 저장해둔다 ② DP배열을 만든다 (열은 물건 0~i번까지 넣을 수 있음을 의미하고 행은 0~n까지 넣을 수 있음을 의미한다) - i, j에서 i번째 물건까지 중에 배낭에 넣을 수 있는지 없는지 판단하여 최적의 방법을 저장한다. ㄴ 넣는 것이 최적 = [i - 1][j - i번째 물건 ..

다익스트라 알고리즘(Dijkstra Algorithm) : 음의 가중치가 없는 가중 그래프에서의 최단 경로를 구하는 알고리즘 특징 ① 그래프에서 음의 가중치가 없어야 한다. ( ↔ 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)) 알고리즘 ① V1부터 Vn까지 연결된 간선 인접 행렬 또는 인접 리스트에 저장 ② V1부터 방문하여 V1에서 갈 수 있는 정점에 대해 최소 거리 갱신 및 다음 방문 예정지로 저장 V1 V2 V3 V4 V5 V1 0 1 2 5 INF V2 1 0 2 3 INF V3 2 2 0 INF 4 V4 5 3 INF 0 1 V5 INF INF 4 1 0 더보기 V1 V2 V3 V4 V5 V1 0 1 3 5 INF V1 V2 V3 V4 V5 V1 0 1 3 5 → 4 ..

문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한..

문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제의 정답을 인접 행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. 문제 접근 방법 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)으로 그래프를 ..

문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 ..

문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 출력 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이..

문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 문제 접근 방법 n!이라는 숫자의 일의 자리부터 처음으로 0이 아닌 수가 나오기 이전까지 총 0의 개수를 출력하는 문제이다. 예를 들면 3! = 6이므로 일의 자리부터 0이 아니므로 0을 출력 10! = 3268800이므로 일의 자리부터 십의 자리까지 0이 나오므로 2를 출력 이런식의 문제이다. 그렇다면 n이 입력되면 n!을 구해야 하는 것인가? 결론부터 말하면 아니다. n!은 1~n의 곱으로 만들어진 수이다. 그렇다면 맨 뒷자리에 0이 오려면 인수로 10이 있다는 소리가 된다. 아직 이정도의 정보만으..

플로이드-와샬(Floyd-Warshall Algorithm) = 플로이드 알고리즘, 로이-와샬 알고리즘, 로이-플로이드 알고리즘, WFI 알고리즘 : 음의 사이클이 없는 가중 그래프에서 최단 경로를 찾는 알고리즘이다 특징 ① 음의 간선이 있는 가중 그래프에서 사용 가능 (≠ 다익스트라 알고리즘(Dijkstra Algorithm)) 알고리즘 ① V1부터 Vn까지 연결된 간선 인접 행렬에 저장 ② 경유하는 정점으로 V1~Vn을 설정 (k) ③ 시작 정점(i)을 V1~Vn, 도착정점(j)을 V1~Vn으로 하는 경우 모두 탐색 이때, 의 값이 + 보다 1. 작거나 같으면 그냥 넘어감 2. 크면 값 대체 더보기 Before graph V1 V2 V3 V4 After graph V1 V2 V3 V4 V1 0 INF..

너비 우선 탐색(Breath First Search, BFS) : 하나의 정점으로부터 시작하여 인접한 정점들을 우선으로 탐색하여 최종적으로 모든 정점을 탐색하는 방법 특징 ① 목표 지점까지 최단 길이(경로)를 보장한다. ② 경로가 길수록 인접한 정점이 많이 생겨나므로(저장되므로) 저장 공간이 많이 필요하다. ③ 선입선출(FIFO, First In First Out) 구조이다. BFS 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue ③ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue 하여 구한 정점에서 ②반복 ④ 큐가 공백이 될 때까지 ②~③반복 더보기..

문제 세준이는 양수와 +, -, 그러고 괄호를 가지고 식을 만들었다. 그러고 나서 세준이는 괄호를 모두 지웠다. 그러고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 문제 접근 방법 괄호가 없는 식이 입력으로 주어진다. 이때 우리는 식의 결괏값을 최소로 만들어야 한다..