Algorithm/theory

종류시간 복잡도설명버블O(n2)두 인접한 데이터의 크기를 비교하여 크기가 작/크면 swap 정렬하는 방식선택O(n2)전체 데이터 중에서 가장 작은/큰 값을 찾아 첫 번째 위치부터 순서대로 정렬하는 방식삽입O(n2)앞의 이미 정렬된 부분에서 데이터의 알맞은 위치를 찾아 삽입하여 정렬하는 방식퀵평균O(nlogn)pivot을 선정하고 이를 기준으로 크기가 작은 값, 큰 값을 나누어 정렬하는 방식pivot 선정이 잘못될 경우 최악의 경우 O(n2)까지 성능이 떨어질 수 있음.병합O(nlogn)데이터를 가장 작은 단위로 나눈 후, 다시 병합하면서 정렬하는 방식안정적인 성능을 보장하지만, 추가 메모리 사용이 필요함 1. 버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 ..

그래프(G)는 정점(vertex)들의 집합 V와 이들을 연결하는 간성(edge)들의 집합 E로 구성된 자료구조입니다. 그래프의 종류 1. 무방향 그래프(undirected graph) vs 방향 그래프(directed graph) 무방향 그래프는 A→B B→A로도 갈 수 있는 방향이 정해져 있지 않은 그래프입니다. 반대로 방향 그래프는 방향이 정해져 있습니다. 이 때 들어오는 간선을 indegree라 하며, 나가는 간선을 outdegree라 합니다. 정점 B를 살펴보면 A와 C로 부터 들어오는 indegree 2개, E로 나가는 outdegree 1개가 있는 것을 알 수 있습니다. 코딩테스트는 주로 무방향 그래프(undirected graph) 문제를 다룹니다. 2. 다중 그래프 vs 단순 그래프 인접해..

트리(Tree)는 서로 연결된 Node의 계층형 자료구조로, root와 부모-자식 관계의 subtree로 구성되어 있습니다. 트리 순회 트리는 비선형 자료구조이기 때문에 순회하는 방법이 여러 가지 존재합니다. 대표적으로 level order traversal, preorder traversal, inorder traversal, postorder traversal가 있습니다. Level-order Traversal 이 방법은 말 그대로 level 별로 순회하는 것을 말합니다. (A) ► (B, C, D) ► (E, F, G, H, I) ► (J, K, L) 구현 level order는 가장 기본적인 코드이므로, 추후 참고없이 직접 구현할 수 있어야 합니다. queue = 방문할 노드를 순서대로 입력 vi..

Hash table은 빠른 탐색을 위해 key-value 형태로 데이터를 입력받는 자료 구조입니다. 저장, 탐색, 검색의 시간 복잡도는 모두 O(1)입니다. Direct-address Table 직접 주소화 테이블이란, key k를 index k 위치에 저장하는 방식입니다. 이러한 저장 방식은 많은 문제가 발생합니다. 불필요한 공간 낭비 key값으로 문자열이 올 수 없다. 이러한 문제를 해결하기 위해 Hash table을 이용합니다. 이는 hash function h를 이용해서 (key, value)를 저장합니다. “h(k)는 키 k의 해시값이다” 모든 데이터에 key값은 존재하며, 중복되는 key값이 있어서는 안된다. (key, value)데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucke..

큐 Queue 먼저 저장된 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조입니다. queue의 뒤(rear)에 데이터를 추가하는 것을 enqueue라고 하고, queue의 앞(front)에서 데이터를 꺼내는 것을 dequeue라고 합니다. List 기반 구현 enqueue → append 메소드 사용 dequeue → pop 메소드 사용 # queue 선언 q = [] # enqueue O(1) q.append(1) # [1] q.append(2) # [1, 2] q.append(3) # [1, 2, 3] # dequeue O(n) q.pop(0) # [2, 3] q.pop(0) # [3] Linked list 기반 구현 enqueue → a..

리스트는 순서를 가지는 자료구조로, sequence라고도 부릅니다. 구현 방법은 두 가지가 있습니다. Array List Linked List 1. Array List 배열을 기반으로 구성된 List 자료구조이다. 메모리 할당 방식에 따라 다음 두 가지로 나눌 수 있습니다. 정적 배열 static array 배열 선언시 미리 저장 공간을 할당받는다. (fixed-size) 데이터를 순차적으로 저장한다. (order) 동적 배열 dynamic array static array 문제점, 초기 할당된 배열의 크기보다 더 많은 데이터를 저장해야 하는 경우 메모리 공간이 없어 발생하는 문제를 보안하고자 나온 할당 방식이다. 기존에 할당된 메모리 공간을 초과했을 때, 배열의 크기를 변경 resizing 할 수 있다..