Tie up loose ends!

제약조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략 해를 찾기 위해 후보군에서 제약조건을 점진적으로 검사하다가, 해당 후보군이 제약조건을 만족할 수 없다고 판단되면 더 이상 연관된 후보들을 검사하지 않고 다른 후보군으로 넘어가 최적의 해를 찾음 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)을 상태공간트리(State Space Tree)를 통해 표현함 각 후보군을 DFS 또는 BFS 방식으로 확인 Promising : 해당 후보군이 조건에 맞는지 검사 Pruning(가지 치기) : 조건에 맞지 않으면, 바로 다른 후보군으로 넘어가 탐색 시간을 절약함 (예제) N Queen 문제 - NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하..

하나의 정점에서 다른 모든 정점까지의 가장 짧은 거리를 구하는 알고리즘 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단 거리를 갱신하는 기법으로, 너비우선탐색(BFS)과 유사함 첫 정점부터 각 정점 간의 거리를 저장할 배열을 만든 후, 첫 정점의 인접 정점부터 거리를 계산하면서 가장 짧은 거리를 해당 배열에 업데이트 해나간다. 첫 정점의 거리는 0, 나머지는 무한대로 배열을 초기화하고, 우선순위 큐에 첫 정점만 먼저 넣는다. 우선순위 큐에서 정점을 꺼내고, 정점부터 인접 정점까지 거리를 배열에 저장된 값과 비교해 짧은 거리를 업데이트 한다. 거리가 업데이트 된 경우, 해당 정점을 우선순위 큐에 넣는다. 다시 우선순위 큐에서 정점을 하나 꺼내고, 위 과정을 우선순위 큐에 꺼낼 정점이 없을 때까..

여러 경우 중 하나를 결정해야할 때마다 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종 값을 구함 (예제 1) 지불해야 하는 값이 4,720원일 때 1원, 50원, 100원, 500원으로 동전의 수가 가장 적게 지불할 경우는? (예제 2) 부분 배낭 문제(Fractional Knapsack Problem) - 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제, 물건을 쪼개 일부분만 배낭에 넣을 수 있음 탐욕 알고리즘은 매순간 판단에 의존하므로 반드시 최적의 해를 구할 수 있는 것은 아니다. 따라서 근사치 추정에 활용된다. '시작' 노드에서 leaf node까지 가장 작은 값을 찾는 경로 탐욕 알고리즘 적용시 : 시작 → 7 → 12 이므로 19..

너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식(Queue 활용) 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식(Stack 활용) 노드 수를 V, 간선 수를 E라고 하면 BFS, DFS 모두 시간 복잡도는 O(V+E)

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 탐색할 자료는 반드시 정렬이 되어있어야 함 탐색할 자료의 중간 값과 찾을 데이터를 비교해서 찾을 데이터가 더 크면, 자료의 첫번째 값에서 중간 값까지 값 중에서 다시 탐색함 시간 복잡도는 O(𝑙𝑜𝑔𝑛)

기준점(Pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(Left), 큰 데이터는 오른쪽(Right)으로 모으는 작업을 재귀적으로 수행한 뒤, Left + Pivot + Right 값을 리턴하는 알고리즘 기준점은 보통 리스트의 맨 앞, 또는 맨 뒤의 데이터를 사용함 분할 정복(DAC; Divide and Conquer) 기법 중 하나로 재귀 함수를 이용함 시간 복잡도는 O(𝑛𝑙𝑜𝑔𝑛)

리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나누고, 각 부분 리스트를 정렬 후 다시 하나의 리스트로 병합함 분할 정복(DAC; Divide and Conquer) 기법 중 하나로 재귀 함수를 이용함 시간 복잡도는 O(𝑛𝑙𝑜𝑔𝑛)

동적 계획법 (DP; Dynamic Programming) 입력 크기가 작은 문제들을 해결한 후, 해당 문제의 해를 활용해서 보다 큰 크기의 문제를 해결하며 최종적으로 전체 문제를 해결하는 알고리즘 (상향식 접근법) Memoization 기법(프로그램 실행시 이전에 계산한 값을 저장하고 재활용해서 전체 실행 속도를 높이는 기술)을 사용함 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨 예) 피보나치 수열 분할 정복 (DAC; Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 (하향식 접근법) 일반적으로 재귀 함수로 구현함 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 예) 병합 정렬, 퀵 정렬 (예제) 피보나치 수열

함수 안에서 동일한 함수를 호출하는 형태 파이썬은 한번에 호출되는 재귀 호출이 1000회 이하가 되어야 함 (예제 1) 팩토리얼 값을 구하는 함수 (예제 2) 숫자가 들어있는 리스트의 모든 요소 합을 구하는 함수 (예제 3) 거꾸로 읽어도 같은 단어(회문, Palindrome)를 판별할 수 있는 함수 (예제 4) n이 1이 될 때까지 홀수면 (3*n+1)을 하고, 짝수면 2로 나누는 함수 (예제 5) 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하는 함수

1. 버블 정렬 (Bubble Sort) - 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 * 버블 정렬 시간 복잡도 : O(n^2) 2. 삽입 정렬 (Insertion Sort) - 해당 인덱스(key값) 앞에 있는 데이터(B)부터 비교해서 key값이 더 작으면, B값을 뒤 인덱스로 옮기는 정렬 알고리즘 * 삽입 정렬 시간 복잡도 : O(n^2) 3. 선택 정렬 (Selection Sort) - 주어진 데이터 중 최소값을 찾아 앞에 위치한 데이터와 교체하는 정렬 알고리즘 * 삽입 정렬 시간 복잡도 : O(n^2)