알고리즘 공부 정리
1.[알고리즘] 그리디 알고리즘 (Greedy Algorithm)
1. 그리디 알고리즘 그리디 알고리즘은 Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다. 그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이
2.[알고리즘] 깊이 우선 탐색 (DFS)
인접행렬과 인접 리스트의 차이 DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로n\*O(n)이므로 O(n^2)의 시간복잡도를 가지게 된다.DFS가 총 N번 호출되긴 하지만 인접행렬과 달리 인접 리스
3.[알고리즘] 너비 우선 탐색 (BFS)
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.멀리떨어진 노드는 나중에 탐색하는 방식이기 때문!선입선출의 방식을 활용해야 하기 때문에 큐를 활용한다.자료 구조 큐(Queue)를 이용그래프를 인접 행렬(adjacen
4.[알고리즘] 선택 정렬(Selection Sort)
선택 정렬은 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 즉, 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 2번째 데이터와 바꾸는 과
5.[알고리즘] 삽입 정렬(insertion sort)
삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.선택 정렬에 비해 구현 난이도가 높은 편이지만, 선택 정렬에 비해 실행 시간
6.[알고리즘] 버블 정렬 (Bubble Sort)
이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.일단 구현이 쉽다. Bubble정렬은 인접한 값만 계속해서 비교하면 되는 방식으로 굉장히 구현이 쉬운 편이다.코드 자체가 직관적이다.굉장히 비효율적이다. 최
7.[알고리즘] 퀵 정렬(quick sort)
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이며, 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제
8.[알고리즘] 계수 정렬 (Counting Sort)
1. 계수 정렬 >#### 계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘이다. (여기서 특정한 조건이란 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용이 가능.) 일반적으로 가장 큰 데이터
9.[알고리즘] 이진 탐색 (Binary Search)
오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘배열 전체의 중간값을 target 값과 비교중간값이 target 값보다 크면 왼쪽 부분만 선택왼쪽부분의 중간값을 다시 target 과 비교검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속
10.[알고리즘] 다익스트라 (Dijkstra)
최소 비용 중에서도, 주어진 두 노드(시작노드 , 도착노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.방문한 정점들과 연결되어 있는 정점들
11.[알고리즘] 최소 신장 트리 (Minimum Spanning Tree)
그래프 내의 모든 정점들을 포함하는 그래프의 부분집합(subgraph) Tree최소한의 간선들로 그래프 내의 모든 정점을 포함 \- 따라서 Spanning Tree는 cycle을 포함하지 않음 \- 그래프 내의 정점의 수가 n개이면, Spanning Tree는 (n
12.[알고리즘] KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)
KMP 알고리즘은 패턴을 문장안에서 좌에서 우로 비교하는 것인데, Brute-force 알고리즘과 다르게 패턴의 위치를 좀 더 효율적으로 이동시킨다. 패턴과 문장의 불일치가 발생했을 때 중복연산을 최대한 피하면서 패턴을 우측으로 이동시킨다. 이를 위해서는 문장의 불일치
13.[알고리즘] 라빈-카프 알고리즘 (Rabin-Karp)
해시 값이 다르다면 두 문자열은 다르다는 것이 보장된다. 하지만 문자열이 달라도 해시 값이 같을 수 있다.Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요하다. 이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시
14.[알고리즘] 비트 마스크 (Bit Mask)
일반적 표현정수형표현 (비트마스크)
15.[알고리즘] 선택 문제 (Selection)
리스트가 주어질 때 리스트에서 k 번째로 작은 값을 반환하는 함수 selection()을 구현하여야 한다. 함수 selection의 인자로는 2가지가 주어지는데 하나는 숫자들의 리스트이고 또 다른 하나는 k이다. 또 selection()은 함수 partition()을
16.[알고리즘] 기수 정렬(Ridix Sort)
기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.가장 작은 자릿수부터 정렬을 진행 (숫자로 치면 일의 자리수부터)가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이