자료구조와 알고리즘

트라이 우리가 사용하는 스마트폰의 자동 완성같은 기능이 어떻게 동작하는지 예상해보자.

이진 힙(binary heap)은 특수한 종류의 이진 트리다.

이진 탐색 트리

트리(tree)는 노드 기반 자료 구조이다.

연결 리스트의 종류는 다양하다. 그 중 하나가 바로 이중 연결 리스트(doubly linked list)이다.

연결 리스트와 배열은 비슷하게 작동하지만 내부적으로는 크게 다르다.

만약 많은 시험 점수가 있을 때 30번째 백분위수나 중간 점수를 알고 싶을 때 어떤 방법을 사용하면 좋을까?

퀵 정렬

퀵 정렬(Quicksort)은 매우 빠른 정렬 알고리즘으로서 대다수의 컴퓨터 언어가 내부적으로 채택한 알고리즘이다.

선형 검색

버블 정렬 버블 정렬은 단순 정렬 분류에 속한다. 이해하기 쉬워서 이렇게 불리지만, 더 빠르다고 알려진 정렬 알고리즘보다 비효율적이다. 기본적인 정렬 알고리즘인 버블 정렬(bubble sort)는 다음과 같은 단계를 따른다. 배열 하나를 정렬하고 싶다고 가정하자. 배열의 처음 상태는 다음과 같다. [ 5 , 2 , 7 , 1 , 3 ] 1단계 :...

선택 정렬 선택 정렬은 단순 정렬 분류에 속한다.

삽입 정렬은 단순 정렬 분류에 속한다.

해시 테이블 해시 테이블(hash table) 자료 구조는 key/value 데이터 쌍을 저장하는 효율적인 자료구조이며, 빠른 검색이라는 장점을 갖고 있다.

스택 스택(stack)은 임시 데이터를 처리할 때 사용할 수 있는 간결한 도구다.

큐 큐(queue)도 스택과 같이 임시 데이터를 처리할 때 효과적인 데이터 구조다.

그래프(graph)는 관계에 특화된 자료구조이다.

그래프 탐색 그래프 탐색은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 방식이 널리 쓰인다.

가중 그래프(weighted graph)는 간선에 정보를 추가할 수 있는 유용한 그래프 유형이다.