[Algorithm] 구현 - 시뮬레이션
* Python을 기준으로 합니다구현 - 시뮬레이션 (Simulation)- 개념시뮬레이션 : 문제에서 주어진 과정을 하나씩 차례대로 직접 수행해 나가는 유형 시뮬레이션 문제 접근하기- 주어진 문제를 최대한으로 분리하기- 예외 처리는 독립적인 함수로 구분하기특히 시뮬레이션 문제는 2차원 배열을 활용하는 경우가 많으므로 행렬 연산을 응용해서 사용할 수도 있음- 문제가 길기 때문에 잘 분석해야함- 구현1. 행렬 연산행렬 덧셈, 뺄셈, 곱셈#행렬 덧셈def matrix_sum(a,b): result = [] for arow ,brow in zip(a, b): row = [] for aele, bele in zip(arow, brow): row.append..
[Algorithm] 최대공약수, 최소공배수
* Python을 기준으로 합니다최대공약수 (Greatest Common Divisor, GCD) & 최소공배수 (Least Common Multiple, LCM)- 개념최대공약수 : 두 수의 약수들 중에서 공통되면서 가장 큰 약수최소공배수 : 두 수의 배수들 중에서 공통되면서 가장 작은 배수기본적으로 최대공약수, 최소공배수 모두 완전 탐색으로 찾을 수 있음- 최대공약수의 경우 $O(N)$의 time complexity, 최소공배수는 $O(NM)$의 time complexity가 소모됨이때 유클리드 호제법을 활용하면 최대공약수 계산을 $O(\log n)$으로 해결 가능함유클리드 호제법두 수 $a, b$ ($a>b$)에 대해, $a$를 $b$로 나눈 나머지를 $r$이라 하면, $a$와 $b$의 최대공약수는..
[Algorithm] 소수 판별 - 에라토스테네스의 체
* Python을 기준으로 합니다소수 판별 - 에라토스테네스의 체 (Sieve of Eratosthenes)- 개념소수 : 2보다 큰 자연수 중 1과 자기 자신 만을 약수로 가지는 수기본적으로 완전 탐색을 사용할 수 있지만, $O(n)$의 time complexity가 소모되므로 큰 수에 대해서는 비효율적임- 이때 자연수의 약수는 대칭적으로 구해진다는 것을 고려하면, $O(\sqrt{n})$의 time complexity로 줄일 수 있음에라토스테네스의 체 : $N$ 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있고, $O(n \log \log n)$의 time complexity를 가짐에라토스테네스의 체 동작과정2부터 $N$까지의 모든 자연수를 나열남은 수 중에서 처리되지 않은 가장 작은 자연수 $..
[Algorithm] 최장 증가 부분 순열, 최장 공통 부분 수열
* Python을 기준으로 합니다 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) & 최장 공통 부분 수열 (Longest Common Subsequence, LCS) - 개념 부분 수열 : 주어진 수열 중 일부를 뽑아 새로운 수열을 만들 때, 기존의 상대적인 순서를 유지하는 수열 최장 증가 부분 수열 (LIS) : 부분 수열의 원소가 오름차순을 유지하면서 가장 길이가 긴 수열 일반적으로 다이나믹 프로그래밍으로 해결가능함 LIS 길이 계산에 다이나믹 프로그래밍 적용하기 다이나믹 프로그래밍을 활용하기 위해서는 전체 문제가 중복되는 최적 부분 구조로써 분해 가능해야함 - 최적 부분 구조 : 전체 수열에 대한 LIS 길이는 각 원소로 끝나는 LIS 길이 중 최대값을 구..
[Algorithm] 신장 트리 - 프림 / 크루스칼 알고리즘
* Python을 기준으로 합니다 신장 트리 (Spanning Tree) - 프림 / 크루스칼 알고리즘 - 개념 신장 트리 : 모든 노드와 연결되어 있으면서 사이클이 존재하지 않는 부분 그래프 이때 간선 개수는 노드의 개수 보다 하나 적음 최소 신장 트리 (Minimum Spanning Tree, MST) : 가중치 합이 최소인 신장 트리 - 이때 구해지는 최소 신장 트리는 여러 개일 수 있음 최소 신장 트리 구하기 공통적으로 그리디 전략을 이용하고, $E$개의 노드 $V$개의 간선에 대해 $O(E \log V)$의 time complexity를 가짐 프림 알고리즘 (Prim Algorithm) 임의의 노드를 선택하여 최소 신장 트리에 추가 최소 신장 트리와 연결되어 있는 노드 중에서 가장 가중치가 작은..
[Algorithm] 다이나믹 프로그래밍
* Python을 기준으로 합니다 다이나믹 프로그래밍 (Dynamic Programming) - 개념 다이나믹 프로그래밍 (동적 계획법) : 전체 문제를 각각의 부분 문제로 나눈 다음 하나의 결과로 합쳐서 해결하는 방법 즉, 전체 문제를 부분 문제로 나누어 해결할 수 있어야 하고 동시에 중복되는 부분 문제가 존재하는 경우 사용 다이나믹 프로그래밍의 구현 메모이제이션 (Memoization) : 하향식 (Top-down) 방식 - 주어진 문제를 작은 부분 문제로 나누어 가면서 전체 문제를 해결하는 방식 - 재귀를 기반으로 이전 값들이 모두 계산되어 있다는 가정 하에 나머지 계산을 수행함 타뷸레이션 (Tabulation) : 상향식 (Bottom-up) 방식 - 작은 부분 문제부터 해결한 다음, 해당 과정을..