ImYena

유클리드 호제법/유클리드 알고리즘(Euclidean Algorithm) 2개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같음 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 시간복잡도 O(logN) 기존의 하나씩 나누어서 구하는 방식으로 최대공약수를 구하게 될 경우 시간복잡도 O(N) 예시) 78696과 19332의 최대공약수 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 18..

그리디/탐욕 알고리즘 Greedy Algorithm 최적해를 구하는 데에 사용되는 근사적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방법 조건 탐욕스런 선택 조건(greedy choice property) 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이 최적 부분 구조 조건(optimal substructure) 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것 예시 Good Case 가장 단 기간에 서울에서 부산까지 도착하는 거리를 구하려면 그 순간 순간 가장 빠른 최단 경로를 구하면 된다. 즉, 서울에서 대구까지의 최적의 거리, 대구에서 부산까지의 최적의 거리를 구하는 것이 그리디 알고리즘이라고 할 수 있다. 또한, 각각의 선택이..

동적 계획법(Dynamic Programming) 복잡한 문제를 간단한 여러 개의 하위문제로 나누어 푼 다음, 그것을 결합하여 최종적인 문제 해결을 하는 방법 부분 문제 반복(Overlapping Subproblem)과 최적 부분 구조(Optimal Substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용 이미 진행된 연산을 기록했다가 사용하는 방식 메모이제이션(Memoization) 하위 문제의 연산의 값을 배열에 저장하여 재사용 하는 방식 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것 접근 방식 하위 문제 정의; 전체 문제를 하위 문제로 단순화메모이제이션 테이블 정의점화식 정의; 재귀적인 구조를 활용 할 수 있는 점화식을..

완전탐색 알고리즘 / 브루트 포스(Brute Force) 더보기 Brute: 짐승같은, 무식한, 짐승같은 + Force: 힘 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법 완전탐색 알고리즘 가능한 모든 경우의 수 모두 탐색 장점 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져옴 그렇기 때문에 예외 없이 100%의 확률로 정답만 출력 단점 문제의 복잡도(Complexity)에 매우 민감하다 탐색 방법 선형 구조; 전체적으로 탐색하는 순차 탐색 비선형 구조 너비 우선 탐색(BFS, Breadth First Search) 깊이 우선 탐색(DFS, Depth First Search)

백트래킹(Backtracking) 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 해(정답)을 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 완전 탐색X 최적화 문제와 결정 문제를 푸는 방법 재귀 사용 재귀의 특성상 틀리더라도 틀린 부분을 찾는 것이 힘듦 가지치기(Prunning) 해를 찾아가는 도중 해당 경로가 해가 될 것 같지 않으면 더이상 가지 않고 되돌아 가는 방식 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 감 접근 방식 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 트리의 가지 중 해결책이 존재 트리를 검사하기 위해 깊이 우선 탐색(DFS) 시도 → 탐색 중 오답을 만나면 이전 분기점으로 백 -> 시도해 보지 않은 해결책이 있으면 시도 -> 해결 ..

재귀(Recursion) 어떠한 것을 정의할 때 자기 자신을 참조하는 것 재귀적 정의 또는 순환 정의 라고도 함 재귀 함수(Recursive Function) / 재귀 알고리즘(Recusive Algorithm) 하나의 함수에서 자기 자신을 다시 호출해 수행하는 알고리즘 귀납적 문제 해결 방식(기존의 절차지향적인 문제 해결 방식과는 다름) 모든 재귀 함수는 반복문으로 치환 가능 상황에 따라서 반복문이 코드가 너무 길고 복잡해질 경우 재귀 함수 사용 반복문 대신 재귀 함수로 구현했을 경우 코드가 간결하지만, 메모리/시간 측면에서 손해 자기 자신을 여러 번 호출하는 것은 비효율적! 재귀 호출 시에는 스택 영역에 계속 누적됨 접근방식 함수의 정의 Base Condition 정의(필수) 자기 자신을 호출하지 않..