알고리즘 정리

1. 그리디 알고리즘 - 현재 상황에서 지금 당장 좋은 것만 고르는법 -> 나중에 미칠 영향을 생각하지 않는 것

사실 나중에 미칠 영향도 생각해야 하는 것 같다

정렬, 플로이드 워셜, 다익스트라 알고리즘과 같은 알고리즘을 어느 정도 알아야 하고 또한 창의력이 필요하기에 문제경험이 필요한 것 같다

 

2. 구현

완전탐색, 시뮬레이션으로 나눌 수 있다.

특히 시간복잡도를 확인하고 완전탐색으로도 해결할 수 있는지 파악하는게 중요하다

 

3. 자료구조 활용

- 배열

- 연결 리스트

배열의 추가/삭제 연산에 대해 비효율성을 극복하고자 등장한 데이터 구조, 다음 노드 연결에 대한 정보를 담은 포인터와 함께 노드에 저장

특징

1. 새로운 요소가 추가될 때 런타임에 메모리를 할당한다. (동적 메모리 할당)
2. Sequential Access를 지원한다. 요소에 접근할 때 순차적으로 접근해야 하는 특징이 있다. 
3. 인덱스나 위치와 같은 물리적 배치를 사용하지 않고 참조 시스템(다음 노드 연결에 대한 포인터 또는 주소)을 사용한다. 

시간복잡도

1. 검색 (Search) : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다. 
2. 추가/삭제 (Insert/Delete) : 동적인 메모리 크기를 갖기 때문에, 새로운 요소를 추가하거나 삭제할 경우에 해당되는 부분만 변경하면 되기 때문에 O(1)의 시간 복잡도를 갖는다.

ex)이중연결, 단중연결리스트

 

 

- 스택

FILO(FIrst In Last Out)

1. 검색 (Search) : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다. 
2. 추가/삭제 (Insert/Delete) : 가장 위에 데이터를 추가하거나 삭제하기 때문에 O(1)의 시간 복잡도를 갖는다.

- 큐

FIFO(First In First Out)

1. 검색 (Search) : 처음부터 순차적으로 접근해야 하기 때문에 O(n)의 시간 복잡도를 갖는다. 
2. 추가/삭제 (Insert/Delete) : 가장 위에 데이터를 추가하거나 삭제하기 때문에 O(1)의 시간 복잡도를 갖는다.

- 우선순위 큐 & 힙

최대최소의 값을 찾을 때 O(log2n)의 시간 복잡도를 가져서 매우 빠르다

- 트리

 트리는 비선형 자료구조로, 노드로 구성된 계층적 자료구조이다. 최상위 노드(Root)를 만들고, 부모(Parent) 노드에 자식(Child) 노드를 추가하고 그리고 그 자식 노드가 부모 노드로써 또 다른 자식 노드를 추가하는 구조를 가지고 있다. 트리에 또 다른 트리가 있는 재귀적 자료구조이다.

1. 트리에 또 다른 트리가 있는 재귀적 자료구조이다.
2. 데이터를 순차적으로 저장하지 않는, 비선형 자료구조이다.
3. 이진트리(Binary Tree), 이진탐색트리(BST, Binary Search Tree), 균형트리(B-Tree, Balanced Tree), 힙트리(Heap Tree) 등 다양한 종류가 존재한다. 

 

 

- 그래프

 그래프는 비선형 자료구조로, 노드(Node)/정점(Vertice)과 이들 사이를 연결하는 엣지(Edge)로 구성된 자료구조를 의미한다.

1. 그래프는 방향이 있을 수도(Directed) 없을 수도(Undirected) 있다.
2. 다양한 구조로 설계된다. 구조에 따라서 시간 복잡도가 달라지고 다양하게 응용이 가능하다. 
3. 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
4. 시간 복잡도/공간 복잡도를 이야기할때 노드(N)/정점(V)과 엣지(E)의 수를 사용하여 표현한다.

 

 

- 해시 테이블

키와 값으로 데이터를 저장하는 자료구조 -> 빠른 검색이 필요할 때 용이하다. 해시함수+연결 리스트

1. 키 값을 배열의 인덱스로 사용하기 때문에, 값을 직접 접근할 수 있다. 따라서, 해시 테이블의 평균 시간 복잡도는 O(1)이다.(운이 없어, 충돌(Collision)이 일어나는 경우 O(n))
2. 충돌이 발생할 수 있다. 이 경우 분리 연결법(Separate Chainging) 혹은 개방 주소법(Open Address)을 사용하여 해결한다.
3. 데이터가 저장되기 이전에 미리 공간을 만들어야한다. 공간 복잡도가 크다.
4. 해시 함수를 통해서 배열 인덱스의 범위를 조절할 수 있다. 이를 리사이징(Resizing)이라고 한다. 
5. 키와 해시의 연관성이 없어 보안에도 자주 사용된다. 

해결방법:

1. Separate Chaining

2. Open Address

 

 

4. 재귀함수 활용

- 항상 종료조건을 확인하자

5. 그래프 탐색 알고리즘 DFS/BFS

 

6. 정렬

- 선택 정렬

- 삽입 정렬

- 퀵 정렬

- 버블 정렬

 

7. 이진 탐색

 

8. 다이나믹 프로그래밍

 

9. 최단경로

 

10. union-find 알고리즘, 크루스칼 알고리즘, 위상 정렬 알고리즘