내 맴

- Backtracking Algorithm ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ 모든 경우의 수를 전부 고려한다 ( 브루트 포스 Algorithm과 유사) ✔ 최적화(optimization) 문제와 결정(decision) 문제 ( yes or no question) 를 해결할수있다. ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - 순서 1. State Space Tree에서 DFS를 실시한다 2. 각 Node가 promising한 지 점검 3. If Node가 promising한 경우 → 자손 Node 탐색 Else non promising한 경우 → 부모 Node..

- Fractional Knapsack n개의 물건과 1개의 배낭이 있다 물건 i의 무게는 W(i), 이익은 P(i), 배낭용량은 M까지 가능하다 물건들을 배낭에 섞어서 넣되, 무게가 M을 넘지 않으면서 이윤이 최대가 되도록 물건을 담는 방법? (물건을 잘라서 담을 수 있다) 예시 ) 이익, 무게 등 무엇을 기준으로 잡고 greedy algorithm을 수행할지에 따라 결과가 다르다. 그러나 Fractional Knapsack 문제에서는 물건의 무게당 이익이 큰것을 기준으로 잡고 Algorithm을 짜면 항상 최적의 이익을 얻을 수 있다. 단, 단위 무게 당 이익이 큰 순서대로 정렬이 되어있어야만 하며, 정렬이 되어있다면 Time complexity는 O(n)이 된다 그러므로 최대 이익은 31.5가 된다..

- BFS ( Breath First Search ) : Root Node 방문 후, 그 Node의 후손과 같은 level에 있는 Node들을 먼저 Search - 구현 방법 1. GRAPH 표현해주기 ( python ) : Dictionary 과 List 자료형을 사용해준다 1개의 Node와 연결되어있는 Node들을 모두 다 표현해준다 # 1. GRAPH로 나타내기 - Dictionary 사용 graph={ 'A': ['B','C'], 'B':['A','D','E'], 'C':['A','F','G'], 'D':['B','H', 'I'], 'E':['B','J'], 'F':['C'], 'G':['C'], 'H':['D'], 'I':['D'], 'J':['E'] } 2. BFS 구현하기 ( python )..

- DFS ( Depth First Search ) : Root Node 방문 후, 그 Node의 후손들을 왼쪽에서 오른쪽으로 Search - 구현 방법 1. GRAPH 표현해주기 ( python ) : Dictionary 과 List 자료형을 사용해준다 1개의 Node와 연결되어있는 Node들을 모두 다 표현해준다 2. DFS 구현하기 ( python ) : Stack를 이용하여 구현한다. - 전체 code

- Quick Sort 설명 : pivot을 설정하고 partition을 수행하여 pivot값을 고정시킨다. 1. pivot을 설정하기 2. partition과정 수행 → pivot이 고정됨 3. pivot보다 큰 부분과 작은 부분 각각 quick sort 다시 시행 - Partition 과정 1. i= 맨처음 수 , j= 맨 마지막 수 2. (1) i가 하나씩 커지면서 i>pivot이 되면 멈춤 (2) j가 하나씩 작아지면서 j

- Bubble Sort 설명 : 인접한 두 원소 검사하여 정렬 list의 원소 갯수: n개 일때 1. (n-1)번 회전하면서 제일 큰 값을 고정시킨다. 1. 첫번째 원소와 두번째 원소 비교 → 작은 수가 앞으로 오게 exchange 2. 두번째 원소와 세번째 원소 비교 → 작은 수가 앞으로 오게 exchange ..... 고정된 원소까지 반복 - python code

- Merge Sort 설명 ✔ divide & conquer방법을 이용함 ✔ n개의숫자들을 반으로 나눠 2개의 부분으로 분할하고 → 각각의 부분을 재귀적으로 정렬한 후 → 2개의 정렬된 부분을 merge하여 정렬 - Mergesort (1) 1개의 정렬되지 않은 배열을 2개의 배열로 분할하는것을 반복 → 배열의 원소 갯수가 1개가 될때까지 반복 (2) 양쪽의 배열의 크기가 둘 다 1개가 되면 merge시켜준다 ✔ 입력 크기가 n=6 , list A= [ 9, 20, 5, 15, 3, 11 ]인 경우 초록색 화살표는 divide하는 과정, 노란색 화살표는 merge하는 과정을 의미한다. - Merge ✔ 두개의 정렬된 배열을 하나의 정렬된 배열로 합치는 function ✔ A=[1,,,,h] 와 B=[1..

- Selection Sort 설명 고정이 되는 수와 나머지 수들을 비교해서 제일 작은 수와 고정된 수를 바꿔서 정렬한다 1. i=0 , j=i+1부터 시작한다 2. i는 고정 , j값을 하나씩 늘려가면서 A[i]보다 작은 값인 min값을 찾는다 3. If min값을 찾으면, A[i]와 min값을 exchange 하고 i+1해주기 Else A[i]보다 작은 값이 존재하지 않으면 (A[i]가 제일 작은 값인 경우) i+1해주기 - python code