[Python] DFS, BFS 구현 DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. DFS는 스택 자료구조(또는 재귀함수)를 이용합니다. 탐색 시작 노드를 스택에 삽입하고 방문 처리합니다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼냅니다. 더이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. DFS의 과정 그래프가 다음과 같이 주어졌을 때, 방문 기준은 번호가 낮은 인접노드 순으로 가정합니다. 깊이 우선 탐색이므로 가장 낮은 노드 1번 부터 시작해서 인접 노드 2,3을 확인합니다. 방문 기준에 따라 2번을 골라서 들어가고, 2번.. Python/알고리즘, 자료구조 / 2021. 12. 30. / Yoonkie

[Python] 검색 / 이진 검색(Binary search) 이진 검색 이진 검색이란, 정렬된 배열 내에서 지정된 입력값의 위치(key)를 찾습니다. 이진 검색은 입력값과 배열의 중간요소를 비교해서 입력값과 중간요소가 일치한다면 배열의 위치를 반환하고, 입력값이 중간요소보다 작다면 중간 요소의 왼쪽 하위 배열에서 검색 과정을 반복합니다. (정렬된 배열이므로) 큰 경우에는 요소의 오른쪽 하위 요소가 반복합니다. 이진 검색의 예시 [1, 2, 5, 6, 7, 10, 12, 13, 14, 15]라는 정렬된 리스트에서 13이란 값을 찾아보려고 합니다. 첫번째 실행 시작 인덱스 0, 마지막 인덱스 9의 중간값 (0 + 9)//2 는 4이므로 인덱스 4의 값은 7입니다. 13 > 7이므로 리스트의 오른쪽 요소에서 이진 검색을 실행합니다. 두번째 실행 이전 실행에서 중간 인덱.. Python/알고리즘, 자료구조 / 2021. 12. 14. / Yoonkie

[Python] 정렬 / 병합 정렬(Merge Sort) 병합 정렬 정렬 안되어 있는 리스트의 크기가 각각 1이 될때까지 리스트를 반으로 나눕니다. (분할) 나뉜 리스트를 다시 정렬하면서(정복) 결합하는 방식입니다. 병합 정렬 과정 복사를 위해 추가적인 리스트가 필요합니다. 리스트를 더이상 분해되지 않을 때까지, 재귀호출을 통해 분할합니다. 2개의 부분 리스트의 값들을 서로 비교하며 작은 값들을 먼저 새로운 리스트에 복사합니다. 각 단계를 마치게 되면, 값을 복사한 리스트를 원래의 리스트로 옮깁니다. 반복 2개의 부분리스트를 새로운 리스트에 정복, 결합하는 과정 병합 정렬 # 리스트 분할 def merge_sort(seq, left, right): # 더이상 쪼개지지 않을 경우 if left >= right: return mid = (left + right) .. Python/알고리즘, 자료구조 / 2021. 12. 7. / Yoonkie

[Python] 정렬 / 퀵 정렬(Quick Sort) 퀵 정렬 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와 비교하며 정렬하는 비교정렬입니다. 평균적으로 매우 빠른 속도로 정렬을 수행합니다. 분할 정복 방법을 수행합니다. 분할 정복 방법이란, 각각 두개의 문제로 분리하여 해결한 다음 결과를 모아서 원래의 문제를 해결합니다. 퀵 정렬 수행 방법 임의의 하나의 원소를 선택합니다.(선택된 원소의 위치를 pivot이라 하고, 보통 맨 처음을 pivot으로 지정) pivot보다 작은 원소들을 왼쪽, pivot보다 큰 원소들을 오른쪽으로 배치합니다. pivot을 기준으로 분할하여 순환 호출을 통해 반복 정렬을 하며 마칩니다. 퀵 정렬 코드 def quick_sort(seq, start, end): # 배열의 시작과 끝점을 입력 if start >= end: # 원소가.. Python/알고리즘, 자료구조 / 2021. 11. 30. / Yoonkie

[Python] 정렬 / 계수 정렬(Counting Sort) Counting Sort Counting Sort란 값의 발생 횟수를 계산하는 누적 카운트를 사용하며, 누적 카운트를 갱신해서 순서대로 숫자를 배치하는 방식입니다. Counting Sort는 배열 내의 최댓값 + 1 만큼의 배열 길이가 필요하므로 정수의 범위가 크면 매우 비효율 적입니다. 파이썬에 내장된 collections.defaultdict 모듈의 딕셔너리 타입을 활용하여 구현해보겠습니다. defaultdict를 활용한 Counting Sort from collections import defaultdict def count_sort_dict(seq): result = [] dic = defaultdict(list) # c의 key값(x)에 x를 append -> 각 key에는 x의 갯수만큼 x값이.. Python/알고리즘, 자료구조 / 2021. 11. 30. / Yoonkie

[Python] 정렬 / 삽입 정렬(Insertion sort) 삽입 정렬 삽입정렬(Insertion sort)이란, 리스트의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방법입니다. 배열이 길어질수록 효율이 떨어지지만,선택 정렬이나 거품 정렬에 비교하여 빠르며, 안정적이고 in-place 알고리즘입니다. 삽입 정렬 def insertion_sort(li): length = len(li) for i in range(1, length): # j는 1번째 부터 시작하여 그 앞의 값들과 비교하여 자신의 자리를 찾습니다. for j in range(i, 0, -1): # 자신보다 큰 값들과 자리를 바꾸며 자신보다 작은 값 뒤까지 반복합니다. if li[j] < li[j - 1]: li[j], li[j - 1] = li[j .. Python/알고리즘, 자료구조 / 2021. 11. 24. / Yoonkie

[Python] 정렬 / 버블 정렬(Bubble sort) / 선택 정렬(Selection sort) 버블 정렬 버블 정렬이란, 인접한 두 항목을 비교해서 정렬하는 방식입니다. 항목이 거품처럼 올라오는 듯해서 버블 정렬이라고 합니다. 버블 정렬 def bubbleSort(seq): length = len(seq) for i in range(length - 1): # 0부터 length - 1 까지 for j in range(length - i - 1): # j번째와 j+1번째 요소와 비교해서 스왑합니다. if seq[j] > seq[j + 1]: seq[j], seq[j + 1] = seq[j + 1], seq[j] print("{}번째 : {}".format((i+1), seq)) # 단계별로 출력해보기 return seq 처음부터 탐색하며 현재 원소가 다음 원소보다 크면 서로 위치를 바꾸고, 그렇지 .. Python/알고리즘, 자료구조 / 2021. 11. 24. / Yoonkie

[Python] 스택 활용한 문제(문자열 거꾸로 출력, 괄호의 갯수 판별, 10진수를 n진수로 변환) 1. 문자열 거꾸로 출력 먼저 저번에 올렸던 스택 게시물에서 작성한 스택 class를 간단히 작성해보았습니다. 스택 class Stack(object): def __init__(self): self.head = None self.size = 0 def push(self, value): self.head = Node(value, self.head) self.size += 1 def pop(self): if self.head is None: print("Stack is Empty!") else: node = self.head self.head = self.head.pointer self.size -= 1 return node.value # 스택이 비었다면 True, 아니면 False def isEmpty(s.. Python/알고리즘, 자료구조 / 2021. 11. 19. / Yoonkie