hong_mok

버블 정렬(Bubble Sort) - 시간 복잡도 : O(n^2) - 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식이다. 알고리즘 - 첫 번째 인덱스 요소부터 인접한 원소랑 비교하여 자료를 바꾸면서 마지막 인덱스 요소 까지 반복한다. - 한 단계가 끝날 시 가장 큰 원소가 마지막에 정렬된다. - 정렬된 부분을 제외하고 나머지 부분에 대하여 정렬을 반복한다. 정렬과정을 그림으로 나타내면 다음과 같다. 코드 def bubble_sort(arr): # 버블 정렬(오름차순) n = len(arr) # 배열의 길이 저장 # 한 스텝마다 정렬된 자료가 뒤부터 쌓이므로 # 정렬범위 n-1부터 0까지 1씩 줄여주기 for i in range(n-1, 0, -1): for j in range(i): # 인접..

백트래킹(Backtracking) 이란? 비선형 구조의 자료를 탐색할 때 깊이 우선 탐색(DFS) 방식으로 경로를 따라가다가, 조건을 확인하였을 때 그 경로가 해결책으로 이어질 것 같지 않다면 더이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄이는 방식이다. 이를 가지치기(Prunning) 라고 한다. 깊이 우선 탐색(DFS) 방식과 유사하지만 DFS는 가능한 모든 경로를 추적하는데 비해서 백트래킹은 가지치키를 통해 불필요한 경로를 차단한다. 일반적으로는 경우의 수가 줄어들지만 최악의 경우에는 여전히 많은 탐색을 요하므로 처리가 불가능하다. 절차 트리의 깊이 우선 탐색을 실시한다. 조건을 확인하여 각 노드가 유망한지(Promising) 점검한다. 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가..

스택(Stack) - 스택이란 물건을 쌓아 올린 것 처럼 자료를 쌓아 올린 형태의 자료구조 이다. - 스택에 저장된 자료는 자료간의 관계가 1대1의 관계를 갖는 선형 구조이다. (반대의 경우는 1대N 구조인 트리가 있다.) - 가장 마지막에 들어간 자료가, 가장 처음에 나온다. (후입선출 LIFO(Last-in-First-out)) - 위와 같은 특징 떄문에, 가장 위에서만 데이터의 삽입 & 삭제가 일어난다. 프링글스 통을 생각하면 된다. 스택의 데이터 구조 - top : 스택의 가장 위에 있는 위치를 저장하고 있는 데이터 - size : 스택의 크기를 저장하고 있는 데이터 - items : 스택에 담길 데이터를 저장할 데이터 구조 스택의 연산 - CreateStack : 스택을 생성하는 연산. size..

이진 검색(Binary Search) 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법이다. 원하는 값을 찾을 때 까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가며 검색한다. 이때, 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다. 알고리즘 - 자료의 중앙에 있는 원소를 고른다. - 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다. - 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다. - 찾고자 하는 값을 찾을 때 까지 위의 과정을 반복한다. 위의 알고리즘을 그림으로 나타내면 다음과 같다. 파이썬 코드 def binary_sear..

합병 정렬(Merge Sort) - 시간 복잡도 : O(n log n) - 분할 정복 알고리즘 이다. 알고리즘 - 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 - 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. - 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. - 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병(merge) 한다. - 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 과정 합병 정렬 과정을 그림으로 나타내면 다음과 같다. - 상단의 붉은색 부분은 정렬되지 않은 리스트들을 나누는 분할(devide) 과정이다. 길이가 1이..