CS/알고리즘

[Algo] LIS (최장 증가 부분 수열)

LIS란? 최장 증가 부분 수열을 의미한다. 어떠한 수열이 주어졌을 때, 그 중 몇 개의 수를 골라내서 만든 수열을 '부분 수열'이라고 한며, 그 몇 개의 수가 오름차순으로 증가하는 형태일 때 이를 '증가하는 부분 수열'이라고 한다. 증가하는 부분 수열 중 길이가 가장 긴 부분수열이 '최장 증가 부분 수열'이다. 예를 들어, [10 20 10 30 40 50]수열이 있을 때, [10 20 10], [20 30] [20 10 40 50] 등 여러 부분 수열을 만들 수 있다. 그 중 최장 증가 부분 수열은 [10 20 30 40 50] 이다. Solving LIS problem - LIS 길이 구하기 수열의 첫 번째 숫자부터 순회하면서, 이 숫자를 포함했을 때 오름차순 형태를 유지할 수 있는지, 다시 말해 ..

[Algo] DP (dynamic programming)

DP(dynamic programming) 복잡한 문제를 여러 개의 간단한 작은 문제로 나누어 푼 다음 작은 문제의 답을 모아 최종적으로 문제를 해결하는 방법 "중복되는 부분 문제"와 "최적 부분 구조"를 만족할 때 사용 중복되는 부분 문제(overlapping subproblem): 동일한 부분 문제(작은, 간단한 문제)를 반복적으로 해결 최적 부분 구조(optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능 Memorization, 이전에 해결한 하위 문제의 답을 저장해서 반복 작업을 줄이는 것이 핵심

[Algo] 유클리드 호제법 (최대공약수, 최소공배수 구하기)

유클리드 호제법/알고리즘 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 " 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. " 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 최대공약수 구하기 유클리드 호제법을 이용해 두 수 a, b의 최대공약수를 구할 수 있다. /* get_gcd: parameter로 주어지는 두 수 a, b의 최대공약수를 구하는 함수 (a > b) */ int ge..

[Algo] 다익스트라 알고리즘 (dijkstra)

Dijkstra Algorithm DP 를 이용한 대표적 최단 경로 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있음 음의 간선 불가능 Idea " 최단 거리는 여러 개의 최단 거리로 이루어져 있다 " 출발 정점에서 가장 가까운 정점을 중간 정점으로 했을 때의 거리와 비교하여 최단 거리를 업데이트 ex) 출발 정점이 1이고, 1에서 가장 가까운 정점인 4를 중간 정점으로 했을 때, 3, 5의 경우 1에서 바로 가는 것보다 중간 정점인 4를 거쳐서 가는 것이 더 가까움 출발 정점인 1에서 3과 5로 가는 최단 거리를 3, 7로 업데이트 모든 정점에 대해 출발 정점에서 가까운 순서대로 위 동작을 반복하면 출발 정점에서 각 정점까지의 최단 경로를 알 수 있음 1과 가장 가까운..