전체 글
-
퀵정렬(Quick Sort)Data Structure & Algorithm 2021. 1. 28. 18:06
[아이디어] 정렬할 데이터의 가장 좌측 인덱스를 left, 가장 우측 인덱스를 right라고하고 정렬기준이 될 데이터를 pivot이라 합시다. left를 1씩 증가하고 right를 1씩 감소시켜가며 pivot을 기준으로 pivot이하인 경우는 pivot보다 왼편으로 pivot을 초과하는 경우 pivot보다 오른쪽으로 데이터를 이동하여 일부 정렬된 형태의 데이터로 만들어줍니다. 이렇게 만들어진 일부 정렬 형태의 데이터를 pivot 기준으로 분할하여 다시 퀵정렬 함수의 재귀 호출을 통해 정렬해 갑니다. 정렬과정에서 정렬에 필요한 데이터를 반씩 줄여가는 형태가 됩니다. left >= right이 되면 더이상 정렬할 요소가 없다는 것이니 별도의 로직 실행없이 return 합니다. 정렬할 데이터 가운데 pivot..
-
삽입정렬(Insertion Sort)Data Structure & Algorithm 2021. 1. 24. 19:20
[아이디어] 데이터의 가장 앞에 위치한 원소는 정렬 된 것으로 간주합니다. 아직 정렬되지 않은 데이터 중 첫번째 데이터를 시작으로 정렬된 데이터와 비교해서 정렬되지 않은데이터가 작으면 정렬되지 않은 데이터와 비교된 데이터를 교환(swaping)합니다. 만약 두 데이터가 같거나 정렬되지 않은 데이터가 정렬된 데이터보다 크다면 비교를 중지합니다. 인덱스 1 ~ n-1 까지의 모든 요소들에 대해 2번 로직을 실행합니다. [특징] 평균시간복잡도는 O(n²)입니다. 버블, 선택 정렬에 비해 비교적 뛰어난 성능을 보여줍니다. [구현] data = [3, 4, 1, 0, 2, 0] print('not-sorted:', ' '.join(map(str, data))) for i in range(1, len(data)):..
-
선택정렬(Selection Sort)Data Structure & Algorithm 2021. 1. 22. 20:54
[아이디어] 데이터의 정렬되지 않은 첫번째 원소부터 선형탐색으로 가장 작은 값을 찾아 인덱스를 기록합니다. 1에서 찾은 인덱스를 사용하여 가장 작은 값과 정렬되지 않은 첫번째 원소를 서로 교환합니다. 1 ~ 2를 모든 원소 개수 - 1 만큼 반복합니다. [특징] 평균 시간 복잡도는 O(n²)입니다. 동일한 값이 두개 이상일 때 정렬 후 데이터 간 순서가 보장되지 않습니다. 제자리 정렬 알고리즘으로 swapping을 위한 임시 저장 메모리 외에 추가적인 메모리를 필요로 하지 않아 공간 복잡도는 O(1)입니다. [구현] 1. python def selection_sort(data, reverse_order): for i in range(len(data) - 1): index = i for j in range..
-
DFS, BFS with pythonData Structure & Algorithm 2021. 1. 11. 10:07
Depth Frist Search(DFS)와 Breadth First Search(BFS)는 그래프 탐색 알고리즘이다. 각각 특정 순서에 따라 그래프의 노드를 탐색하게 된다. DFS는 stack 또는 재귀호출을 이용하여 구현하고 BFS는 queue를 이용하여 구현한다. 1. DFS 구현방법 stack에 시작 노드를 넣고 해당 노드를 방문했음을 기록한다. stack의 최상단 노드와 인접한 노드 중 아직 방문하지 않은 노드의 존재 여부에 따라 인접한 노드 A가 있으면 stack에 넣고 노드 A를 방문했음을 기록한다. 인접한 노드가 없으면 stack에 대해 pop연산을 진행한다. stack이 empty 상태가 되면 알고리즘을 종료한다. ★ 노드가 stack에 push될 때마다 push되는 노드를 순서대로 리스..
-
재귀호출 (recursive call)Python 2021. 1. 9. 20:09
순서 1. 재귀의 개념 및 예제 2. 꼬리재귀 1. 재귀의 개념 및 예제 재귀의 사전적 의미는 "본디의 것으로 다시 돌아오는 것"이다. 정의된 함수 func()가 있다고 할 때 해당 함수 내부에서 자기 자신 즉 func()를 호출하는 것이다. 재귀호출의 구조 def func(n): if n == 0:# 재귀 호출을 탈출할 수 있는 조건을 명시해야 한다. return 1: else: return func(n-1))# 함수 내부에서 동일 함수를 호출한다. 재귀호출 예제1 - factorial def factorial(n): if n
-
유용한 표준 라이브러리Python 2020. 12. 24. 09:18
내장함수: 기본 입출력(input(), print(), sorted()), 정렬 기능 등을 제공하는 함수 itertools: iterator를 처리하기 위한 기능을 제공한다. itertools의 순열,조합 라이브러리는 코딩테스트 중 완전탐색 알고리즘에 유용하게 사용된다. heap: heap 자료구조를 제공한다. heap정렬과 우선순위 큐 기능 구현에 사용한다. (다익스트라 최단거리 알고리즘에 활용 된다.) bisect: 이진 탐색 기능을 제공한다. collections: deque, Counter 등의 유용한 자료구조를 제공한다. math: 수학과 관련된 기능을 제공한다. factorial, square, GCD, 삼각함수와 같은 함수와 pi와 같은 상수를 제공 [내장함수] 별도의 모듈을 import할 ..
-
Python 기본 정렬과 커스텀 정렬Python 2020. 12. 24. 08:34
기본 정렬 (오름차순, 내림차순) 커스텀한 정렬 람다식을 사용한 정렬 functools.cmp_to_key를 사용한 정렬 comparator 함수를 직접 사용하여 정렬 1. 기본 정렬 (오름차순, 내림차순) 단순하게 숫자나 문자열의 대소를 따지는 정렬은 python에서 지원하는 sort(), sorted()를 사용하여 처리할 수 있다. 기본 오름차순으로 정렬된다. nums = [4, 2, 5, 3, 1] # num을 정렬한 내용의 새로운 리스트를 생성하려면 sorted_num = sorted(nums) # num을 정렬된 내용으로 변경하려면 nums.sort() 내림차순으로 정렬하려면 reverse 파라미터를 True로 지정한다. nums = [4, 2, 5, 3, 1] # num을 정렬한 내용의 새로운..