Passwd

회문 回文, palindrome 순서대로 읽어도 거꾸로 읽어도, 그 내용이 같은 낱말이나 문장 낱말 사이에 있는 공백이나 문장 기호 등은 무시한다. 역삼역, wow, 다가가다, God's Dog 등을 예로 들 수 있다. 자료 구조 여러 가지 자료와 정보를 컴퓨터 안에 저장하고 보관하는 방식 주어진 자료를 효율적으로 정리하고 보관하는 것은 알고리즘 문제 풀이의 필수이므로 알고리즘과 자료 구조는 밀접한 관계를 가진다. 큐 Queue 사전적으로 줄, 줄을 서서 기다리는 것을 의미한다. 그 뜻처럼 먼저 저장한 자료를 먼저 빼내는 선입선출(FIFO, First In First Out) 방식의 자료구조다. 큐에 자료를 집어넣는 동작을 enqueue, 큐에서 자료를 빼내는 동작을 dequeue라고 한다. 코드 리스트..

이분 탐색(Binary search) 이분(二分)이란 둘로 나눈다는 뜻으로, 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳을 탐색한다. 이미 정렬되어 있는 자료에서 탐색 범위를 줄여가며 찾고자 않는 값을 찾는 탐색 방법이다. 이진 탐색이라고도 부른다. 계산 복잡도는 \(\mbox{O}(\log{n})\) 이분 탐색을 하기 위해서는 자료가 정렬되어 있어야 하지만, 필요한 값을 여러 번 찾아야 한다면 자료를 한 번 정렬한 후 이분 탐색을 이용하는 것이 효율적이다. 코드 def binary_search(val, list): start = 0 end = len(list) - 1 while start

버블 정렬 (Bubble Sort) 인접한 두 개의 자료를 비교하여 정렬하는 방법 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째 자료와 네 번째 자료 순으로 비교해가면서 마지막 자료까지 자료를 정렬하기를 반복한다. 버블 정렬은 한 회전을 마칠 때 자료 하나가 정렬됨을 보장하므로, 자료의 개수보다 한 번 적게 정렬을 반복한 뒤 완료한다. 또는 한 회전을 수행하는 동안 정렬한 횟수가 없으면 완료한다. 일반적인 경우, 계산 복잡도는 $$ \mbox{O}(n^2) $$ 코드 n - 1번 반복 def bubbleSort(x): length = len(x)-1 for i in range(length): for j in range(length-i): if x[j] > x[j+1]: x[..

퀵 정렬(Quick sort) 기준값과 비교하여 그룹을 나눈 후, 각각 재귀 호출하여 결과를 합치는 정렬 방식으로 분할 정복 알고리즘(Divide and conquer algorithm)의 하나이다. 아래 그림과 같은 방식으로 동작한다. 퀵 정렬은 얼마나 적절한 기준을 정하느냐에 따라 성능이 크게 좌우된다. 평균적인 계산 복잡도는 $$ \mbox{O}(n\log{n}) $$ 코드 (캐시 사용) def quick_sort(a): n = len(a) # 종료 조건 if n

병합 정렬 (Merge Sort) 비교 기반 정렬 알고리즘 분할 정복(Divide And Conquer) 알고리즘의 하나 분할 정복 (Divide And Conquer) 큰 문제를 작은 문제로 나눠서(분할하여) 해결하는(정복하는) 방법 입력 크기가 큰 문제도 작게 나누는 것을 반복하면 쉬운 문제, 즉 종료 조건이 되는 원리 이용 정렬 방법 리스트의 길이가 0 또는 1이면 정렬된 상태로 판단한다. 리스트가 정렬되지 않았으면, 반으로 나눠 부분 리스트를 생성한다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 정렬된 리스트를 하나의 리스트로 병합한다. 계산 복잡도는 $$ O(n\log{n}) $$ 코드 def merge_sort(list): n = len(list) # 종료 조건 if n

삽입 정렬 (Insertion Sort) 자료의 모든 요소를 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식의 정렬이다. 두 번째 자료부터 시작하여, 그 앞의 자료와 비교하여 삽입할 위치를 지정한 후, 삽입 위치 이후의 자료는 하나씩 뒤로 옮기고, 삽입 위치에 자료를 삽입하여 정렬한다. 아래의 그립으로 쉽게 이해할 수 있다. 계산 복잡도는 선택 정렬과 동일하게 $$ \mbox{O}(n^2) $$ 코드 코드로 표현하면 아래 함수와 같다. def insertion_sort(list): for i in range(1, len(list)): for j in range(0, i): if list[i] > list[j]: list.insert(j, list.pop(i)) return list 참고 ..

정렬 자료를 크기 순서에 맞춰 일렬로 나열하는 것 가나다 순 또는 알파벳 순으로 나열한 사전이 좋은 예시 중 하나다. 정렬 종류 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 병합 정렬 (Merge Sort) 퀵 정렬 (Quick Sort) 거품 정렬 (Bubble Sort) 선택 정렬 제자리 정렬 알고리즘의 하나 가장 작은 값을 선택하여 자리를 교체하는 방식을 반복하여 진행한다. 코드 def selection_sort(list): for i in range(0, len(list) - 1): for j in range(i + 1, len(list)): if list[i] > list[j]: list[i], list[j] = list[j], list[i] # swap r..

탐색 여러 개의 자료 중에서 원하는 것을 찾아내는 것 정렬 주어진 자료를 순서에 맞춰 나열하는 것 순차 탐색 sequential search 리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색한다. 선형 탐색(linear search)이라고도 부른다. 코드 def sequential(num, list): for i in range(0, len(list)): if num == list[i]: return i return -1 계산 복잡도는 최악의 경우 O(n)이다. 자료를 일일이 비교하지 않고 좀 더 효율적으로 탐색을 하기 위해서는 자료를 정렬할 필요성이 있다. 참고 문서 https://thebook.io/006935/part03/ch07/

하노이의 탑(Tower of Hanoi) 원반 옮기기 퍼즐 크기가 다른 원반 n개와 원반을 끼울 수 있는 기둥 3개가 존재한다. 어떻게 하면 원반 n개를 Start 기둥에서 Goal 기둥으로 옮길 수 있는가? 제약 사항은 아래와 같다. 원반은 한 번에 한 개 씩만 옮길 수 있다. 각 기둥 맨 위의 원반은 다른 기둥의 맨 위로만 움직일 수 있다. 옮기는 과정에서 큰 원반을 작은 원반 위에 올릴 수는 없다. 풀이 방법 - 원반이 한개인 경우 - 원반이 n개인 경우 즉, 원반이 1개일 때가 종료 조건인 재귀 함수로 하노이의 탑 알고리즘을 구현할 수 있다. 코드 구현 def hanoi(n, from_p, to_p, aux_p): # 매개변수 n은 원반 수, from_p는 출발 기둥, to_p는 도착 기둥, au..

최대공약수 최대공약수 Greatest Common Disiver, GCD 두 개 이상의 정수의 공통 약수 중 가장 큰 값 방법 1. 정수 중 작은 값부터 1씩 감소시키면서 약수인 값을 찾는다. 2. 유클리드 알고리즘 a와 b의 최대공약수는 b를 a로 나눈 나머지의 최대공약수와 같다. gcd(a, b) = gcd(b, a%b) 어떤 수와 0의 최대공약수는 자기 자신이다. gcd(n, 0) = n 두 번째 성질이 재귀 호출의 종료조건이 된다. 유클리드 알고리즘 코드 def gcd(a, b): if b == 0: return a return gcd(b, a % b) 피보나치 수열 Fibonacci numbers 제 1항을 0, 제 2항을 1로 두고, 그 이후의 항부터는 바로 앞의 두 수를 더한 수로 정의한다...