목표가 생기면 무작정 달려들어야지. 실패를 두려워 할 여유같은 건 없을 때니까

[주제]- 그래프의 탐색 종류와 구현 모델 [정의] 1. 깊이 우선 탐색(Depth First Search, DFS)- DFS 알고리즘은 어떠한 선택을 하건 잘 동작하며, 누구를 우선 선택할 것인지에 대한 기준은 개발자가 결정해도 되는 단순한 문제 ★ 핵심 3가지- 한 사람에게만 연락하면 됨- 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알림- 처음 연락을 시작한 사람의 위치에서 연락은 끝이 남 ■ 그림(깊이 우선 탐색의 과정) - '나나'로부터 연락을 시작한다고 가정 - 나나는 '만수' 또는 '포포'에게 연락이 가능한데 여기서는 '포포'를 선택- 포포는 연결되어 있는 '길동'에게 연락- 길동은 '만수' 또는 '김민' 또는 '철수'에게 연락이 가능한데 여기서는 '철수'를 선택- 최종적으로 '김민..

[주제]- 해쉬 테이블의 개념 [정의] 사원 번호(Key)직원(Data)00150홍길동01320고길동00099아무개 - 표(Table) 형태의 자료구조- 저장되는 데이터가 키(Key) 값과 데이터 값이 하나의 쌍으로 구성됨- 키 값이 없으면 데이터를 저장할 수 없으며, 키 값을 중복될 수 없음 ■ 그림(해쉬 함수) - 일정한 규칙으로 작성된 중복되지 않는 고유 값을 함수를 통해 쉽게 구분할 수 있는 값으로 변경 ※ 해쉬함수(Hash Function): 넓은 범위의 값을 좁은 범위의 값으로 변경하는 역할 - 하지만 해쉬함수가 단순한 산술 연산으로만 되어있으면 값이 중복되어버리는 충돌 현상이 발생됨 - 위 그림은 테이블의 메모리 상황을 표현- 칠해진 영역이 데이터가 저장된 슬롯- 데이터가 저장되는 위치가 골..

[주제]- 균형 잡힌 이진 탐색 트리인 AVL 트리의 개념 [정의]- 이진 탐색 트리는 '저장 순서에 따라 탐색의 성능 차이가 커지는 단점'이 존재- 위 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라고 함- 종류(AVL 트리, 2-3 트리, 2-3-4 트리, Red-Black 트리, B 트리)- 'G. M. Adelson-Velskii와 E. M. Landis'에 의해 고안되었으며, 이름의 앞글자를 따서 AVL 트리라고 함 ■ 그림(균형 잡힌 이진 탐색 트리 예시) ■ 그림(균형 인수) - 균형 인수: 균형의 정도를 표현하는 단위- 균형 인수의 절대값이 크면 클수록 그만큼 트리의 균형이 무너진 상태 ※ 균형 인수 값 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 - AVL 트리는 균형 ..

[주제]- 이진 탐색 트리의 개념 [정의]- 이진 탐색 트리에는 데이터를 저장하는 규칙이 있음. 그 규칙은 특정 데이터의 위치를 찾는데 사용됨- 이진 트리 + 데이터의 저장 규칙 = 이진 탐색 트리 [중요]- 이진 탐색 트리의 노드에 저장된 키(Key)는 유일- 루트 노드의 키는 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크며, 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작음- 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키- 왼쪽/오른쪽 서브 트리도 이진 탐색 트리- 삽입 과정과 탐색 과정은 동일하게 진행 ※ 키는 정수 값으로 설정했다는 가정 ■ 그림(이진 탐색 트리) ■ 그림(이진 탐색 트리의 데이터 삽입 과정) - 비교대상이 없을 때까지 내려감- 비교대상이 없는 때 ..

[주제]- 보간 탐색의 개념 [정의]- 이진 탐색의 비효율성을 개선시킨 알고리즘 [중요]- 효율적인 탐색을 위해서는 '어떻게 찾을까'가 아닌, 효율적인 탐색을 위한 '저장방법'이 무엇인지를 우선 고민해야 함- 탐색 대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작 ※ 예) 고길동이라는 사람의 전화번호를 찾을 때, 전화번호부의 인덱스를 보고 'ㄱ'에 해당하는 앞쪽에서 찾기 ■ 그림(보간 탐색) - 보간 탐색은 찾아야 하는 값이 상대적으로 앞에 위치한다고 판단하면 앞쪽에 탐색 - low: 탐색 대상의 '시작' 인덱스 값- high: 탐색 대상의 '끝' 인덱스 값- S: 찾는 데이터가 저장된 위치의 인덱스 값- 보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정 ■ 1차 공식 A..