브루트 포스법 패턴을 한칸씩 움직여서 텍스트와 일치할때 까지 움직인다. 텍스트 인덱스 2 3 4 의 원소와 일치하여 검색에 성공한다. def bf_match(txt: str, pat: str) -> int: """브루트 포스법으로 문자열 검색""" pt = 0 # txt(텍스트)를 따라가는 커서 pp = 0 # pat(패턴)를 따라가는 커서 while pt != len(txt) and pp != len(pat): #패턴커서가 텍스트 끝까지 도착하지 않을때 if txt[pt] == pat[pp]: #텍스트의 문자와 패턴의 문자가 일치한다면 두 커서 모두 다음 위치로 이동 pt += 1 pp += 1 else: pt = pt - pp + 1 #문자가 일치하지 않는 경우, 텍스트의 탐색 위치를 하나 뒤로 옮기..
출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 병합 정렬 두개의 배열을 합쳐 순서대로 정렬한다. 다음과 같이 sorted 함수로 나타낼수도 있다. c= list(sorted(a+b)) from typing import Sequence, MutableSequence def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None: """정렬을 마친 배열 a와 b를 병합하여 c에 저장""" pa, pb, pc = 0, 0, 0 # 각 배열의 커서 na, nb, nc = len(a), len(b), len(c) # 각 배열의 원소수 while pa < na and pb < nb: # pa와 pb를 비교하여 작은 값을 pc에 저장..
셸 정렬 셸 정렬은 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. h=4일때 4칸씩 떨어진 원소를 비교하여 바꿔준다. 8 1 4 2 7 6 3 5 h = 2일때, 2칸씩 떨어진 원소를 그룹으로 나눠 정렬한다. 7 1 3 2 8 6 4 5 3 1 4 2 7 5 8 6 두 그룹으로 나누어 두번 정렬 한다 h=1 로 하여 전체 그룹으로 한번 정렬을 수행한다. 1 2 3 4 5 6 7 8 이렇게 하여 총 7번 정렬을 하게 되고, 4그룹, 2그룹, 1그룹씩 나누어 정렬을 수행한다. def shell_sort(a: MutableSequence) -> None: """셸 정렬""" n = len(a) h = n // 2 while h > 0: for i in range(h, n): j = i - h tm..
출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 버블정렬 버블정렬은 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복한다. 7개의 원소 6,4,3,7,1,9,8를 대입했다. 패스는 비교 교환하는 과정을 말하는데 패스 1은 첫바퀴 정렬을 의미한다. 첫번째 패스 시 , 정렬 완료 전까지 n-1번의 정렬과정을 거친다. 가장 작은 원소 1이 맨 앞으로 이동한다. 두번째 패스 시 정렬 완료 전까지 n-2의 정렬과정을 거치고, 두번째로 작은 원소 3이 두번째 위치로 이동한다. 버블정렬 구조는 다음과 같다. def bubble_sort(a: MutableSequence) -> None: """버블 정렬""" n = len(a) for i in range(n - 1): for j in range(..
하노이의 탑 출처: Do it!자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편 재귀함수를 이용해 하노이의 탑을 구현해본다. 기둥이 세개 있고, 원반이 3개 있을때, 1번 2번 원반을 중간기둥으로 옮기고, 3번 원반을 목표기둥으로 옮긴후 1&2번 원반을 3번 원반이 있는 목표 기둥 위에 쌓아 올린다. def move(no:int,x:int,y:int)->None: #원반 no개를 x기둥에서 y기둥으로 옮김 if no >1: move(no-1,x,6-x-y) print(f'원반[{no}]를 {x}기둥에서 {y}기둥을 옮깁니다') if no > 1: move(no-1,6-x-y,y) print('하노이의 탑을 구현합니다') n = int(input('원반의 개수를 입력하세요 : ')) move(n,1,3)..
출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 재귀 알고리즘의 개념 팩토리얼 n! 팩토리얼 n! 정의(n은 양의 정수) 0! = 1 n>0이면, n!= n x (n-1)! def factorial(n:int) -> int: #양의 정수 n 팩토리얼값을 재귀적으로 구함 if n>0: return n* factorial(n-1) else: return 1 if __name__ == '__main__': n = int(input('출력할 팩토리얼값을 입력하세요: ')) print(f'{n}의 팩토리얼은 {factorial(n)} 입니다. ') 출력할 팩토리얼값을 입력하세요: 4 4의 팩토리얼은 24 입니다. factorial함수의 기전은 다음과 같다. factorial() 함수로 3!값을 구한다면,..
출처: Do it! 자료구조와 함께 배우는 알고리즘 입문- 파이썬편 큐는 스택과 같이 데이터를 임시 저장하는 자료구조이지만, 스택처럼 가장 나중에 넣은 데이터를 가장 먼저 꺼내지 않는다. 선입선출(가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조)이다. 인큐(enqueue) : 큐에 데이터 추가 디큐(dequeue): 데이터를 꺼냄 프런트(front): 데이터를 꺼내는 쪽 리어(rear): 데이터를 넣는 쪽 링 버퍼로 큐 구현하기 링 버퍼 ring buffer는 디큐할 때 배열의 원소를 옮기지 않는 큐이다. front 값은 5, rear 값은 2이다. 여기서 82를 인큐하면 맨끝의 다음에 위치한 que[rear]= que[2]에 82를 저장하고 rear 값을 2에서 3으로 움직인다. 24를 디큐 하면 맨 ..
출처: Do it! 자료구조와 함께 배우는 알고리즘 입문- 파이썬편 스택 stack 스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력순서는 후입선출(가장 나중에 넣은 데이터를 가장 먼저 꺼내는) 방식이다. 데이터를 넣는 작업을 푸시push, 데이터를 꺼내는 작업을 팝pop 이라고 한다. 푸시하고 합하는 윗부분을 top, 아랫부분을 bottom이라고 한다. 스택 구현 스택 배열: stk -> 푸시한 데이터를 저장하는 list형 배열, 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0] 스택 크기: capacity -> 스택의 최대 크기를 나타내는 int형 정수, len(stk)로 나타냄 스택 포인터 : ptr -> 스택에 쌓여있는 데이터의 갯수를 나타내는 정수값, 스택이 비어있..
