dev.ssun

트리와 이진트리 트리(Tree) 계층적인 구조 표현 용어 트리는 노드(node)들과 노드들을 연결하는 링크(link) 로 구성됨 부모-자식 관계 루트노드를 제외한 모든 노드는 부모-자식 관계를 가짐 형제 관계 부모가 동일한 노드들 리프(leaf) 노드 자식이 없는 노드들 조상-자손 관계 부모-자식 관계를 확장한 것 부트리(subtree) 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리 레벨 루트 노드부터 레벨 1 부터 부여된다 (0으로 시작할 수 있음) 높이 위 트리 높이는 4이다 트리의 기본적인 성질 노드가 N개인 트리는 항상 N-1개의 링크를 가진다 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는 다는..

6장 힙 정렬(Heap Sort) https://www.youtube.com/watch?time_continue=1731&v=4ULxG2Q3vgU&feature=emb_title Heap Sort 최악의 경우 시간복잡도 O(nlog2n) 이진 힙 자료구조 사용 Heap의 정의 완전 이진 트리이면서 Heap property를 만족하는 것 Tree : 계층적 관계를 표현한다 Full Binary Tree : 모든 레벨에 노드들이 꽉 차있는 형태 Complete Binary Tree : 마지막 레벨을 제외하면 완전히 꽉 차있음, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개의 노드가 비어있을 수 있음 Heap은 일차원 배열로 표현이 가능하다 : A[1..n] Heap은 complete binary 형태이기 때..

BFS & DFS 정말 좋은 영상입니다. 1. 깊이 우선 탐색(DFS: Depth-First Search) 노드를 방문할 때 마다 인접한 노드를 모두 방문한다., Stack 이나 재귀로 구현 모든 경로를 방문해야 할 경우 사용에 적합 2. 너비 우선 탐색(BFS: Breadth-First Search) 레벨 단위로 노드를 방문한다., Queue로 구현 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합 3. DFS & BFS를 슈도 코드로 나타내기 깊이우선탐색(DFS) // DFS - pseudo code // 1. 시작할 노드를 스택에 push 한다. // 2. 스택에서 노드를 하나 pop한다. // 3. If pop한 노드와 인접한 노드가 있는 지 확인한다. // 3-1. po..

빠른 정렬은 분할정복법으로 한다. merge와 비슷하지만 다른 점은 합병 단계에 아무것도 하지 않는 다는 것이다. 분할정복법 분할 : 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다. elements in lower parts ≤ elements in upper parts 기준을 pivot 이라 하고 해당 값을 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 오도록 한다. 정복 : 각 부분을 순환적으로 정렬한다. (recursive) 합병 : nothing to do (아무것도 하지 않음) 정복 작업을 하게 되면 전체가 정렬된 것으로 본다 시간복잡도 평균 - O(NlogN) / 최악 - O(n^2) 의사 코드로 표현하기(pseudo-code) /// data[p...r] 원소를 정렬한다. func ..

4강 합병 정렬(merge sort) 합병 정렬은 다음과 같은 단계를 가진다 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제를 순환적으로 해결 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 [6, 4, 1, 2, 3, 5, 7, 8] 을 예시로 합병 정렬하면 아래 그림과 같은 단계로 정렬이 진행된다. 1차원 배열을 가장 작은 단위, 즉 1의 단위까지 쪼갠다. 가장 작은 단위로 쪼갠 후 배열의 왼쪽/오른쪽 값을 비교한다. 작은 값을 새 배열에 추가하고, 다음 작은 값을 새 배열에 추가한다. 비교하는 과정하고 추가하는 과정이 종료되는 어느 한쪽 배열에 값은 남게 되는 데 이때 반복문을 이용해 왼쪽 배열부터 새 배열에 모두 추가하고, 오..

3강 기본적인 정렬 알고리즘 정리 정렬 알고리즘 종류 simple, slow bubble sort insertion sort selection sort quick quick sort merge sort heap sort O(N) radix sort 1. Selection Sort (선택 정렬) 선택 정렬은 배열의 값 중 하나를 선택해 기준으로 두고 정렬하는 알고리즘이다. data[Int] 변수가 있을 때 배열의 data[i]을 기준으로 두어 변수에 값을 저장한다. (data[i]을 배열의 min 값으로 예상) min 값과 data[i+1] 값을 비교하여 data[i+1] > min 이면 min에 data[i+1] 값을 대입한다. data[i] 과 min 값을 swap 한다. 1~3번까지 반복한다. // ..

순환(Recursive) 개념과 기본 예제 3 정리 Designing Recursion; 순환 알고리즘의 설계 1. 순환 알고리즘 설계 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함 모든 case는 결국 base case로 수렴해야 함 KeyPoint - 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라 2. 예제 - 순차 탐색 data[0]에서 data[n-1] 사이에서 target을 검색한다 // 6. 순차 탐색 - 변경 전 func search(data: [Int], n: Int, target: Int) -> Int { for i in 0.. 배열의 시작 인덱스를 뜻하는 암시적 매개변수 if data[i] == target { ret..

순환(Recursive) 개념과 기본 예제 2 정리 Recursive Thinking; 순환적으로 사고하기 1. Recursion은 수학 함수 계산에만 유용한가? → 다른 많은 문제들을 recursion으로 해결할 수 있다 많은 예제들 문자 개수 세기 문자열을 뒤집어 출력하기 2진수로 변환하여 출력 배열의 합 구하기 데이터 파일로 부터 n개의 정수 읽어 오기 ... 1. 2진수 변환 출력 예제 // 4. 2진수로 변환하여 출력 func printBinary(n: Int) { // 음이 아닌 정수 n을 이진수로 변환하여 인쇄한다 if n < 2 { print(n, terminator: "") } else { printBinary(n: n / 2) // n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후..

순환(Recursive) 개념과 기본 예제 1 정리 순환(Recursive) 자기 자신을 호출하는 함수 1. 순환은 항상 무한 루프에 빠질까? 단순 호출만 하면 발생 가능 // 1. 무한 루프 예제 func infinityLoop() { print("Hello, World!") infinityLoop() } infinityLoop() recursion이 적절한 구조를 가지게 해서 무한 루프에 빠지지 않도록 함 2. 적절한 구조? func sum(n: Int) -> Int { if n == 0 { // Base Case - n이 0이면 종료 return 0 } else { return n + sum(n: n-1) // Recursive Case - 반복하다가 n이 0이 되는 순간이 온다 } } Base C..