알고리즘 2023. 10. 6.
백트래킹 Backtracking
백트래킹 개념 1. 여러 가지 선택지 (옵션) 들이 존재하는 상황에서 한 가지를 선택한다 2. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다 3. 이런 선택을 반복하면서 최종 상태에 도달한다 4. 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다 백트래킹과 깊이우선탐색(DFS)의 차이 DFS는 완전탐색의 방법 중 한 가지이다. 백트래킹은 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다. (Prunning 가지치기) 깊이 우선 탐색이 모든 경로를 추적하는데 비해, 백트래킹은 불필요한 경로를 조기에 차단한다. 깊이 우선 탐색을 하기에는 경우에 수가 너무나 많다. 즉 N! 가지의 경우의 수를 가진 문제에 대해 깊..
알고리즘 2023. 9. 29.
이중 탐색 Binary Search, 퀵 정렬 Quick Sort
이진 검색 이진 검색 Binary Search 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다 검색 과정 자료의 중앙에 있는 원소를 고른다 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 종료한다 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다 찾고자 하는 값을 찾을 때까지 1~4의 과정을 반복한다 알고리즘: 반복구조 binar..
알고리즘 2023. 9. 28.
분할 검색 - 개념과 병합 정렬
분할 정복 병합 정렬 분할 정복 분할 정복 기법 유래 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔 둘로 나뉜 연합군을 한 부분씩 격파함 설계 전략 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다 통합 (Combine) : (필요하다면) 해결된 해답을 모은다 Top-down approach 반복 (Iterative) 알고리즘 O(n) Interative_Power(x, n) result = 1 FOR i in 1 -> n result = result * x RETURN result 분할 정복 기반의 알고리즘 ..
알고리즘 2023. 9. 27.
비트마스킹 - 부분집합, 조합
완전 검색 - 부분집합 부분집합 조합 부분집합 Powerset 비트 연산자 연산자 연산자의 기능 & 비트 단위로 AND 연산을 한다 | 비트 단위로 OR 연산을 한다 ^ 비트 단위로 XOR 연산을 한다 ~ 단항 연산자로서 피연산자의 모든 비트를 반전시킨다 피연산자의 비트 열을 오른쪽으로 이동시킨다 부분집합의 수 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 $2^n$개이다 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다 반복문을 이용하여 부분집합 구하기 sel = {0, 0, 0, 0} for i in 0 to 1: sel[0] = i for j in 0 to 1: sel[1] = j for k in 0 to 1: sel[2] = k..
알고리즘 2023. 9. 25.
자료구조 트리 Tree - 정의, 이진 트리
Tree 트리 이진 트리 트리 트리의 개념 비선형 구조 원소들 간에 1:N 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다 노드 중 최상위 노드를 루트(root)라 한다 나머지 노드들은 n(≥0) 개의 분리 집합 T1, …, Tn으로 분리될 수 있다 이들 T1, …, Tn은 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리 (subtree)라 한다 용어 정리 노드 (node) 트리의 원소 트리 T의 노드: A, B, C, D, E, F, H, I, J, K 간선 (edge) 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드 (r..
알고리즘 2023. 9. 24.
자료구조 연결 스택, 연결 큐
연결 스택 Linked Stack 리스트를 이용해 스택을 구현할 수 있다 스택의 원소: 리스트의 노드 스택 내의 순서는 리스트의 링크를 통해 연결됨 Push: 리스트의 마지막에 노드 삽입 Pop: 리스트의 마지막 노드 반환/삭제 변수 top 리스트의 마지막 노드를 가리키는 변수 초기 상태: top = null 리스트를 이용해 Push와 Pop 연산 구현 null 값을 가지는 노드를 만들어 스택 초기화 원소 A 삽입 push(A) 원소 B 삽입 push(B) 원소 C 삽입 push(C) 원소 반환 pop Push/Pop push(i) { // 원소 i를 스택에 push temp = createNode(); temp.data = i; temp.link = top; top = temp; } pop() { te..
알고리즘 2023. 9. 7.
재귀 호출, Memoization
재귀 호출 재귀 호출이란? 再歸 자기 자신을 호출하여 순환 수행되는 것 함수 호출은 메모리 구조에서 스택을 사용한다. (이름만 같은 다른 메서드) 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능 저하가 발생한다 일반적으로 기본 부분 (Base case), 재귀 부분 (Recursive case)로 구성된다 Base case: 재귀 호출에서 빠져나가기 위한 조건 (탈출 조건) Recursive case: 자신을 호출하는 부분 (Base case로 유도하는 방향으로 작성한다) 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다 하고자 하는 연산에서 여러 가지 분기가 있을 때 적용하기 좋다. 재귀 호출 작성 재귀 호출의 예) 팩토리얼 계산 함수에서 실행해야 하는 작업의 특성..
알고리즘 2023. 8. 30.
패턴 매칭 - 브루트 포스, 보이어 무어
패턴 매칭 패턴 매칭에 사용되는 알고리즘들 고지식한 패턴 검색 알고리즘 ex) 브루트 포스 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 고지식한 알고리즘 (Brute-Force) 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작 알고리즘 설명 고지식한 패턴 검색 알고리즘 // p[] : 찾을 패턴 -iss // t[] : 전체 텍스트 - This iss a book // M : 찾을 패턴의 길이 // N : 전체 텍스트의 길이 // i : t의 인덱스 // j : p의 인덱스 BruteForce(char[] p, char[] t) { i = 0, j = 0 while(j
알고리즘 2023. 8. 25.
탐욕 알고리즘 Greedy Algorithm
탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다 탐욕 알고리즘의 동작 과정 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합 (Solution Set)에 추가한다 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지 확인한다 곧, 문제의 제약 조건을 위반..
알고리즘 2023. 8. 24.
완전 검색 Exhaustive Search
완전 검색 Exhaustive Search Baby-gin Game 설명 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 카드가 연속적인 번호를 갖는 경우는 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라 한다. 그리고, 6장의 카드가 run과 triplet으로만 구성된 경우를 baby-gin으로 부른다 6자리의 숫자를 입력받아 baby-gin의 여부를 판단하는 프로그램을 작성하라 입력 예 667767은 두 개의 triplet이므로 baby-gin이다 (666, 777) 054060은 한 개의 run과 한 개의 triplet이므로 역시 baby-gin이다 (456, 000) 101123은 한 개의 triplet이 존재하나, 023이 run이 아니므로 baby-gi..
