Algorithm
-
[알고리즘/Algorithm] 최대 공약수, 최소 공배수 공식 유클리드 호제법 알아보기Algorithm/ETC 2021. 8. 9. 15:51
파이썬으로 백준 2609번 최대공약수와 최소공배수 문제(아래 링크)를 풀던 중, 많은 사람들이 최대 공약수와 최소 공배수를 특정한 공식으로 풀고 있던 것을 발견했다. https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 찾아본 결과 그 공식은 '유클리드 호제법' 이라는 공식이였고, 아주 멋진 공식 같아서 좀 더 알아보기로 했다. 네이버 백과사전에 의하면 아래와 같이 정의되어 있다. 솔직히 뭔 소린지 하나도 모르겠다.. 그래서 우선 공식을 외우기로 했다! 때로는.. 처음부터 모든 것을 이해하려고 노력하기 보다는 일단 ..
-
[알고리즘/Algorithm] 파이썬으로 깊이 우선 탐색 DFS / 너비 우선 탐색 BFS 알아보기Algorithm/Exhaustive Search 2021. 7. 15. 21:26
그래프를 탐색하는 방법은 대표적으로 DFS (깊이 우선 탐색)와 BFS (너비 우선 탐색)가 있다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) 임의의 노드에서 시작해서 다음 브랜치로 넘어가기 전에 해당 브랜치를 완벽하게 탐색하며 모든 노드를 탐색하는 방법 위와 같은 그래프를 깊이 우선 탐색으로 탐색한다고 하면 아래와 같은 탐색 순서가 나타난다. 깊이 우선 탐색은 위 그림과 같이 임의의 노드부터 시작하여 해당 노드의 브랜치를 전부 탐색한 이후에 다른 브랜치로 넘어가 탐색하며 모든 노드를 탐색할 때까지 반복한다. 1-1. 깊이 우선 탐색 구현 파이썬 코드로 나타낸 그래프 graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'G', 'H'..
-
[알고리즘/Algorithm] 파이썬으로 퀵 정렬(Quick Sort) 알아보기Algorithm/Sort 2021. 7. 13. 22:49
Quick Sort (퀵 정렬) 기준점 (pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 기준점보다 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽, 오른쪽 데이터를 재귀 함수를 활용해서 다시 동일 함수를 호출하여 위 작업을 반복 함수는 왼쪽, 오른쪽 데이터를 리턴 퀵 정렬 흐름 퀵 정렬은 위 그림과 같이 기준점(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하고, 또 나뉘어진 값에서 왼쪽과 오른쪽으로 정렬하며 정렬될 때까지 반복하며 정렬하는 알고리즘이다. 파이썬으로 구현한 퀵 정렬 def quick_sort(data): if len(data) item] right = [item for item in data[1:] if pivot
-
[알고리즘/Algorithm] 파이썬으로 병합/합병 정렬(Merge Sort) 알아보기Algorithm/Sort 2021. 7. 13. 22:27
Merge Sort (병합 정렬) 리스트를 절반으로 잘라 비슷한 크기의 리스트 2개로 나눈다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬되 리스트로 병합한다. 병합 정렬 흐름 그림 병합 정렬은 그림과 같이 리스트를 분할(split)한 후에 병합(merge)를 반복하며 정렬한다. 파이썬으로 구현한 병합 정렬 def merge_sort(data): return split(data) def split(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_poi..
-
[알고리즘/Algorithm] 파이썬으로 선택 정렬(Selection Sort) 알아보기Algorithm/Sort 2021. 7. 6. 21:41
Selection Sort (선택 정렬) 다음과 같은 순서를 반복하며 정렬하는 알고리즘 주어진 데이터 중, 최소값을 찾는다. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다. 선택 정렬 흐름 그림과 같이 한 루프마다 제일 작은 값을 찾아 왼쪽부터 차례차례 스왑하며 정렬해준다. 개인적으로 기본 정렬 3개(버블 정렬, 선택 정렬, 삽입 정렬)중 제일 직관적인 정렬 알고리즘이라고 생각이 들었다. 선택 정렬을 파이썬으로 구현하며 아래와 같이 구현할 수 있다. def selection_sort(target): # 10개의 데이터가 있는 리스트는 최대 9번의 정렬이면 정렬됨 # 따라서 i는 range는 len - 1 for i in range(len..
-
[알고리즘/Algorithm] 파이썬으로 이진 탐색 (Binary Search) 알아보기Algorithm/Binary Search 2021. 7. 6. 17:07
이진 탐색(Binary Search)이란 정렬된(중요!!) 자료(리스트)를 반으로 나누어 가며 데이터를 탐색하는 방법 이진 탐색 흐름 ex) 위 그림과 같이 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 리스트에서 숫자 8을 찾는다! 리스트의 중간에 위치한 데이터(이하 피벗/pivot)를 확인한다. 여기서는 6 해당 피벗에 데이터(6)를 확인하고, 3가지 경우로 나뉜다. 해당 피벗 데이터가 찾는 데이터면 True를 리턴 찾는 데이터가 피벗 보다 작으면 피벗 기준 왼쪽 값들을 기준으로 재 탐색 찾는 데이터가 피벗 보다 크면 피벗 기준 오른쪽 값들을 기준으로 재 탐색 데이터를 찾을 때까지, 혹은 데이터의 개수가 1이 될 때까지 1번과 2번을 반복한다. 파이썬을 통해 구현한 이진 탐색 def..
-
[알고리즘/Algorithm] 파이썬으로 삽입 정렬(Insertion Sort) 알아보기Algorithm/Sort 2021. 7. 5. 23:21
Insertion Sort (삽입 정렬) : 다음과 같은 순서를 반복하며 정렬하는 알고리즘 삽입 정렬은 두 번째 인덱스부터 시작 해당 인덱스 앞에 있는 데이터(B)부터 비교해서 Key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 Key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 Key 값을 이동 삽입 정렬 흐름 삽입 정렬은 그림과 같이 해당 인덱스의 요소에서 그 앞의 요소와 비교를 해서 앞의 요소가 크다면 서로 스왑을 해서 위치를 바꿔준다. 스왑을 한 번 해줬다고 바로 해당 인덱스의 다음 요소부터 또 비교를 시작하는 것이 아니라, 그림에서 4 ~ 6번과 같이 스왑된 요소가 자기 자리를 찾을 때까지 최대 0번째 인덱스까지 비교해서 자기 자리를 찾아간다. 위 그림에서..
-
[알고리즘/Algorithm] 파이썬으로 버블 정렬(Bubble Sort) 알아보기Algorithm/Sort 2021. 7. 1. 22:37
Bubble Sort (버블 정렬) : 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 버블 정렬 흐름 버블 정렬은 위 그림과 같이 리스트에서 한 칸씩 전진해가며 바로 앞에 있는 값과 비교해서 크면 스왑하고 아니면 지나간다. 그렇기 때문에 만약 리스트의 첫 번째 공간에있는 데이터가 리스트내에 제일 큰 값이라면 계속 그 값을 스왑해가면서 한 번의 루프에 그 값이 제일 마지막으로 이동해 있을 것이다. 만약 위 그림에서 리스트의 첫번째 공간의 데이터 5가 만약 11이었다고 한다면 첫 번째 루프에 11이 뒤에 있는 모든 값과 비교하면서 스왑해서 제일 마지막 공간에 위치하게 됐을 것이다. 아이디어 1. : 그렇다면 루프가 한 번씩 지날 때마다 비교하는 횟..
-
[알고리즘/Algorithm] 파이썬으로 재귀함수 알아보기Algorithm/Recursion 2021. 6. 6. 21:30
재귀함수란 함수 안에서 자기 자신(함수)을 다시 호출하는 함수를 말한다. 함수 안에서 함수를 쓴다는 것이 처음에는 잘 와닿지 않았고 딱히 왜 써야 하는지도 모르겠고 이해가 쉽지 않았다. 그래서 공부를 살짝 해봤고 그것을 쉽게 풀어쓰기 위해서 코드를 가지고 왔다. def recrusive(data): if data < 0: print("ended") else: print(data) recrusive(data-1) print("returned", data) 위에 파이썬 코드를 보면 recrusive 함수 선언문 안에서 recrusive 함수를 호출하고 있다. 이것이 함수 안에서 함수를 다시 호출하는 것을 말하는데.. 코드만 보면 이 코드가 어떻게 동작할까를 이해하는 것이 처음보는 사람한테는 쉽지가 않다.. ..