CS/Algorithm Theory

머릿말 알고리즘 공부를 하면서, 어딘가 부족하다는 느낌을 받는 지점이 많은데, 이 때 주로 느끼는 감정은 " 뭘 모르는지 모르겠다" 이다. 실제로 알고리즘을 수업과 여러 자료를 통해 배웠지만, 당시에는 문제를 많이 접하면서 체득을 하는 단계가 아니라 오로지 "이해"하는 것에만 초점을 두고 암기를 하였기에 각 알고리즘이 가진 장/단점을 온전히 느꼈다는 감정은 들지 않았다. 고로, 알고리즘 기본에 해당되는 [ 재귀, 정렬, 탐색, Hash, Graph, 분할정복, DP, 탐욕, 백트래킹 ] 순서로 관련된 이론 및 코드를 정리하며 내가 부족한 부분을 찾고 채워 나가는 시간을 가져 보려고 한다. 버블 정렬 버블 정렬은 명명된 이름과 같이 "버블" 즉, 비눗방울이 가지는 특징을 바탕으로 알고리즘을 설계하였다. 알..

2021. 5. 22.

CS/Algorithm Theory

1. Graph란? 그래프란 노드와 그 노드를 연결하는 간선으로 이루어진 자료구조를 의마한다 * 그래프에서 사용되는 용어들 1. 정점(=vertex) : 노드와 같은 뜻을 가지고 있다. 2. 간선(=edge) : 정점 또는 노드를 이어주는 선을 의미한다. 3. 정점의 차수(degree) : 하나의 정점에 인접한 정점의 수 2. Grpah의 종류 1. 무방향 그래프 정점을 이어주는 간선을 통해 "양방향"으로 이동이 가능하다. 2. 방향 그래프 정점을 이어주는 간선을 통해 "단방향"으로 이동이 가능하다. 3.Grpah의 표현방식 1 인접 행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. - 장점 1. 구현이 쉽다 2. 연결 여부를 쉽게 파악 할 수 있다. ( 행렬 내부에서 0 | 1 ..

2021. 3. 14.

CS/Algorithm Theory

퀵정렬이란? 정렬할 리스트를 두개로 분할하고 정렬하는 방법이다. 퀵정렬 수행 방법 1) 배열의 값 중에서 임의의 수를 피봇을 설정한다. 2) 피봇(=Pivot) 의 좌측은 피봇보다 작거나 같은 값 들, 오른쪽 큰 값들의 구성을 "목표"로한다. 3. 좌측에서 피봇보다 큰 숫자, 우측에서 작은 숫자가 나오면 교환하고 그 둘의 자리를 바꾸고 이를 반복한다. 4. 좌, 우측의 값을 포인팅 해주는 L,R이 피봇을 지나서 엇갈리는 상황이 오면 L과 피봇을 교체해주고 재귀 호출로 분할 정복을 수행한다. 왼쪽에서는 자신보다 큰 8을 찾아서 고정, 오른쪽에서 자신보다 작은 1을 찾아서 고정 => 둘이 교환 위의 작업을 반복하다보니, 피봇을 지나서 L,R과 엇갈리게 되었다. 엇갈리게 됬을 때는, 피봇을 기준으로 왼쪽과 오..

2021. 1. 27.

CS/Algorithm Theory

선택정렬이란? - 주어진 배열에서 최소 값을 찾는다 - 첫 번째 자리의 값과 최소 값의 위치를 변경한다 - 인덱스를 뒤로 이동시키며, 위의 작업을 반복한다. 선택정렬 파이썬코드 import random def SelectionSort(arr): for i in range(len(arr)-1): min_idx = i # 최소 값을 위한 변수 for j in range(i+1, len(arr)): if arr[j] < arr[min_idx]: # 최소값 발견 시 min_idx = j # 값을 변경해준다. arr[i], arr[min_idx] = arr[min_idx], arr[i] # 궁극적으로 발견된 최초값과 위치 변경 return arr arr = random.sample(range(100), 10) p..

2021. 1. 27.

CS/Algorithm Theory

삽입 정렬이 뭔가요? 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 예시 6(Key 4) 에 대한 삽입 정렬을 진행 하는 경우 삽입 정렬의 시간복잡도 -Best Case [ O(n) ] 이미 정렬이 되어 있는 경우, 2번째 자리부터 문자열의 길이인 N까지만 이동을 하는 동안 교환 없이 비교만 이루어 지기 때문에 n-1 번의 비교가 이루어 진다. 그렇기 때문에 시간 복잡도는 O(n) 이라고 할 수 있다. # Best Case # Key index = 2 arr = [ 1, 2, 3, 4, 5 ] # 2 뒤에는 자신보다 작은 수(1) 만 있기 때문에 순서 변경 X # Key index = 3 arr ..

2021. 1. 27.

CS/Algorithm Theory

버블 소트란? 인접한 원소 간의 비교를 통해 정렬하는 알고리즘으로써, 시간복잡도는 O(n2)이다. 시간복잡도가 왜 O(n2) 인가요? 버블소트는 인접한 값과의 숫자 비교를 반복해나가며 정렬을 진행합니다. 궁극적으로 우리가 원하는 오름차순의 배열을 얻기 위해서는 N개의 값들을 비교하는 과정을 N번 반복 했을 때, 정렬이 완료 되기 때문에 O(n2)라고 칭할 수 있다. 인접한 수끼리의 비교가 이루어 지는 경우, 자연스럽게 가장 큰 수가 배열의 맨 뒤로 향하는 현상을 확인 할 수 있을 것인데, 그러한 이유로 위와 같은 작업을 배열의 길이인 N번 반복이 완료 됬을 때 비로소 정렬이 완료 되었음을 알 수 있는 것이다. 버블 소트 예제 # 최초 문자열 arr = [ 7, 6, 5, 4, 3 ] # task 1 [ ..

2021. 1. 27.