etc/자료구조와 알고리즘 (5) 썸네일형 리스트형 정렬 정렬(Sorting)은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 여러 정렬 알고리즘이 있지만 선택 정렬, 삽입 정렬, 퀵 정렬, 그리고 계수 정렬 4가지를 알아보자. 1. 선택 정렬 배열의 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는것이다. 선택 정렬은 이중 반복문으로 구성되어 있어 시간 복잡도가 $O(N^2)$이다. 선택 정렬은 다음과 같이 구현할 수 있다. import random import time random.seed(42) N = 10000 array = list(range(N)) random.shuffle(array) start = time.time() for i in range(.. BFS BFS(Breadth First Search) 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다. 이는 가까운 노드부터 탐색하는 알고리즘이다. BFS는 스택 자료구조를 사용하는 DFS와 달리 큐 자료구조를 이용한다. 이를 이용하면 먼저 들어온 것이 먼저 나가게 되어, 가까운 노트부터 탐색을 진행하게 된다. BFS의 동작 과정은 다음과 같다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. (즉, 큐가 빌때 까지) bfs 구현 예시 from collections import deque def bfs(graph, current_node, v.. DFS DFS(Depth First Search)는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리를한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다. DFS는 스택을 사용하는 알고리즘이기 때문에 재귀 함수를 이용했을 때 간결하게 구현할 수 있다. def dfs(graph, current_node, visited): # 현재 노드를 방문 처리 visited[current_node] = True.. 재귀 함수 재귀 함수(Recursive funtion)은 자기 자신을 다시 호출하는 함수를 의미한다. 재귀 함수를 사용할 때는 종료 조건을 꼭 명시해야 한다. 그렇지 않으면 재귀의 깊이를 초과했다는 RecursionError가 발생한다. 종료 조건을 명시하는 예시는 다음과 같다. 자신을 호출하기 전에 종료 조건을 명시해야한다. def recursive_function(i): # 10번째 출력했을 때 종료되도록 종료 조건 명시 if i == 5: return print(f"{i}번째 재귀 함수에서 {i + 1}번째 재귀 함수 호출") recursive_function(i + 1) ######################################## print(f"{i}번째 재귀 함수 종료") recursive_f.. 스택/큐 스택 스택(Stack) 자료구조는 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 위로 차곡차곡 쌓으며, 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야한다. 이러한 구조를 선입후출(First In Last Out) 또는 후입선출(Last In First Out) 구조라고 한다. 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요 없다. 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다. 큐 큐(Queue)는 놀이공원 대기 줄에 비유할 수 있다. 먼저 온 사람이 먼저 들어가게 된다. 이러한 구조를 선입선출(First In First Out) 구조라고 한다. 파이썬에서는 collections 모듈의 deque 클래스를 사용하면 .. 이전 1 다음