[알알알] week04 개념

스파르타코딩클럽  - 알고보면알기쉬운알고리즘 내용 정리

트리 - 이진 트리, 완전 이진 트리

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식을 가진다.

완전 이진 트리(Complete Binary Tree)는 최하단 왼쪽 노드부터 삽입해야함.

 

이진 트리	완전 이진 트리

이미지 출처: https://ddmix.blogspot.com/2016/03/binary-tree-errata.html

 

편의를 위해 0번째 인덱스 사용 안함 [None]을 기본으로 넣어둠.

• 현재 인덱스 * 2 = 왼쪽 자식의 인덱스
• 현재 인덱스 * 2 + 1 = 오른쪽 자식의 인덱스
• 현재 인덱스 // 2 = 부모의 인덱스

트리의 높이 = 루트 노드 ~ 가장 아래의 리프 노드

최대 노드의 개수 = 2^k

1                      level 0. 1개

2 3                  level 1. 2개

4 5 6 7           level 2. 4개

8 9 ..... 15      level k. 2^k 개

 

높이 h에 최대 노드 개수 = 2^(h+1) -1 

-1을 하는 이유는 첫 인덱스에 none 을 넣어두기 때문.

 

완전 이진트리의 최대 개수가 N일 때 h는

2^(h+1) -1  = N

O(log(N)) !

 

힙(heap) : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

부모 노드의 값이 항상 자식보다 커야 한다. 따라서 가장 큰 값이 맨 위로 가야함.

최대값 맨 위: Max 힙, 최솟값 맨 위 : Min 힙이 있음.

 

원소 추가 규칙

1. 원소를 맨 마지막에 넣는다

2. 부모 노드와 비교해 더 크면 자리 바꾼다

3. 부모 노드보다 작거나, 가장 위에 도달하지 않을 때까지 2과정 반복.

(부모노드보다 크거나, 가장 위에 도달하면 멈춤)

4. 데이터를 삽입

 

맥스 힙 원소 추가

원소 삭제 규칙

스택과 논리가 비슷하다 (LIFO), 맨 위의 원소만 제거 가능 + 다른 위치 삭제 못함

1. 루트 노드와 맨 끝의 원소 교체

2. 맨 뒤에 있는 원소(원래 루트 노드) 삭제함. (값을 가지고 있어야 함!!)

3. 변경된 노드와 자식 노드 비교. 자식>변경 노드 : 자리 바꿈

4. 자식노드가 부모노드보다 크거나 가장 바닥에 도달하지 않을 때까지 반복

5. 2에서 제거한 루트노드 반환

 

삭제

그래프

비선형 구조 - 표현에 초점, 선형구조 - 자료 저장, 꺼내기에 초점

그래프 : 연결 관계에 초점 맞춰짐

노드(Node)	연결관계를 가진 각 데이터 정점(Vertex)이라고도 함.
간선(Edge)	노드 간의 관계 표시한 선
인접 노드(Adjacent Node)	간선으로 직접 연결된 노드(정점)

무방향 (간선의 방향이 없음)

인접 행렬(2차원 배열로 그래프의 연결 관계 표현)

즉각적으로 연결되었는지 알 수 있음 O(노드^2) 만큼 공간 사용(모든 조합 연결 여부 저장)

 

graph = [ [False, True, False, False],

[True, False, True, False],

[False, True, False, True],

[False, False, True, False] ]

 

 

인접 리스트(링크드 리스트로 그래프의 연결관계 표현)

각 리스트를 돌아봐야함 O(간선)만큼의 시간, 모든 조합 연결 여부 저장안해도됨 O(노드 + 간선) 공간

 

graph = { 0: [1], 1: [0, 2] 2: [1, 3] 3: [2] }

 

DFS & BFS

출처 : http://dawoonjeong.com/algorithm-graph-bfs-dfs/

DFS(Depth First Search )

 

끝까지 파고듬 .

최대 깊이 만큼의 공간 필요(공간 적게 씀) 최단 경로 탐색 힘듦.

• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
• 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
• 만약 끝에 도달했다면 리턴한다.

재귀 함수 이용해서 구현 가능!

visited라는 배열에 방문한 노드를 기록해서 방문하지 않은 원소를 찾아감.

1. 루트 노드를 스택에 넣으며 시작

2. 현재 스택의 노드를 visitied에 추가

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가.

4. 2부터 반복

5. 스택이 비면 탐색 종료!

 

 

BFS

갈라진 모든 경우의 수를 탐색.

모든 분기 수 다 저장해야해서 공간 많이 씀. 시간 오래 걸림

 

인접한 노드 먼저 방문  = 방문하지 않은 모든 노드 저장 후 가장 처음 넣은 노드부터 탐색 (큐!)

1. 루트 노드를 큐에 넣습니다.

2. 현재 큐의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가딕 비면 탐색을 종료한다.

 

방문한 노드와 접한 노드 adjacent_node[current_node]

Dynamic Programming

피보나치 수열 - 재귀함수

Fibo(n) = Fibo(n-1) + Fibo(n-2)

탈출 조건은 n == 1 or n == 2 일 때 1

(Fibo(1) 과 Fibo(2)는 1로 고정되어있음)

 

출처 : https://yaboong.github.io/algorithms/2018/02/05/dynamic-programming-1/

동적 계획법(복잡한 문제를 여러 개의 문제로 나누어 푸는 방법)을 사용한다!

메모이제이션(Memoization) : 결과 기록

겹치는 부분 문제(Overlapping Subproblem) : 각 구간마다 시간을 계산해 최적의 시간을 구한다.

 

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.

2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.

3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.