1. 문제 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 17069번: 파이프 옮기기 2 (acmicpc.net) 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net n*n에서 조건에 맞게 (0,0)에서 시작해서 ..
1. 기본적인 $O(n^{2})$ 알고리즘 기본 알고리즘을 다시 한번 생각해보자. 수열 s를 처음부터 순회하면서, i번째 원소를 읽었을때, 0~i번째 원소까지 최장 증가 부분수열의 길이는... i보다 작은 인덱스 j에 대하여, dp배열의 0~j까지 모두 순회해서, j번째 숫자가 i번째 숫자보다 작다면, 그러한 j번째 숫자가 만드는 최장 증가 부분수열에 i번째 숫자를 포함시키면 된다 이렇게 찾은 최장증가부분수열의 길이들의 최댓값이 i번째 원소가 들어가는 최장 증가 부분수열의 길이였다 다익스트라 알고리즘에서 최단거리를 역추적하듯이 생각해보면 아주 심플하다 역추적을 위한 배열 p를 생각해서 현재 i번째 원소에 대한 dp값이 1이라면.. 최장 길이가 1이라는 뜻이니까 자기 자신이 최장 증가 수열의 시작점이니 p..
1. 문제 사용할 수 있는 동전이 1원,4원,6원이 있다. 거스름돈 8원을 내주기 위해 사용할 수 있는 최소 동전의 개수는? 그리디 방법으로 접근하면, 가장 큰것부터 내주면 최소라고 생각할 수 있으니까, 6원, 1원, 1원 그러나 실제 최적해는 4원, 4원으로 2개이다 그리디 방법이 항상 최적해를 보장해주지 않아서, 다른 방법으로 문제를 해결할 필요가 있다 - 완전 검색(백트래킹 이용가능) - 다이나믹 프로그래밍 2. 재귀 알고리즘 3가지 동전 각각 선택하면 작은 부분문제가 생긴다 1원짜리 동전을 선택하면 >> 7원에 대한 최적해 + 1원 1개 >> 7원에 대한 최적해는 1원,4원,6원으로 다시 나눌 수 있음 4원짜리 동전을 선택하면 >> 4원에 대한 최적해 + 4원 1개 6원짜리 동전을 선택하면 >> ..
1. 문제 어떤 수열이 왼쪽에서 오른쪽으로 순서대로 나열된다. 3,2,6,4,5,1.... 만약 이러한 나열된 순서를 유지하면서, 크기가 점진적으로 커지면서, 가장 긴 부분수열은 어떻게 찾을 수 있을까 이러한 부분수열은 연속적으로 고를 필요는 없다. 예를 들어 위 수열에서 3,4,5는 크기가 점점 커지는 부분수열이다. 2. 완전 검색 단순하게 완전 탐색을 수행해서 찾아낼 수도 있다 주어진 수열의 모든 부분집합을 구한다. 부분집합의 원소들이 증가하는 수열인지 검사한다. 증가하는 수열일때, 부분수열의 길이의 최댓값을 갱신한다. 당연히, 부분집합의 크기가 긴 것부터 조사하면, 처음으로 찾게되는 증가수열이 가장 긴 증가수열일 것이다. #완전탐색으로 최장증가 부분수열 찾기 s = [3,2,6,4,5,1] n = ..
1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..
1. 개요 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"에 사용할 수 있는 알고리즘이다. -------------------------------------------------------------------------------------------------------- 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하면서 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘은 또한 단계마다 "거쳐 가는 노드"를 기준으로 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
