버블 정렬 버블 정렬(Bubble Sort)은 바로 옆의 원소와 크기 비교를 하여 위치를 바꾸는 방법이다. 바로 옆의 원소와 크기 비교를 하고 스왑을 하면 되기 때문에 구현하기 쉬운 알고리즘이다. 코딩 아래 코드는 unittest 기반으로 작성되었다. # -*- coding: utf-8 -*- import unittest class Exam12(unittest.TestCase): @classmethod def setUp(cls): pass def test_bubble_sort(self): data = [2, 6, 3, 4, 8, 9, 1, 10] n = len(data) for _ in range(n-1): for i in range(n-1): if data[i] > data[i+1]: data[i], ..

퀵 정렬 퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)과 비슷하게 재귀 호출을 하여 정렬을 한다. 다만 퀵 정렬은 기준점과 미리 비교를 한다는 차이점이 있다. 코딩 아래 코드는 unittest 기반으로 작성되었다. 일반적인 퀵 정렬 # -*- coding: utf-8 -*- import unittest class Exam11(unittest.TestCase): @classmethod def setUp(cls): pass def test_quick_sort(self): """일반적인 퀵 정렬""" def _quick_sort(data, start, end): # 종료 조건: 정렬을 할 원소가 1개 이하인 경우 if start >= end: return # 피봇 설정 (편의상 맨 마지막 원..

병합 정렬 병합 정렬(Merge sort)은 그룹을 반으로 나눈다음 합칠때 크기에 맞게 합친다. 이 과정을 재귀적으로 수행한다. (그림 참고) 코딩 아래 코드는 unittest 기반으로 작성되었다. 일반적인 병합 정렬 # -*- coding: utf-8 -*- import unittest class Exam10(unittest.TestCase): @classmethod def setUp(cls): pass def test_merge_sort(self): """일반적인 병합 정렬""" def _merge_sort(group): # 재귀 종료 조건: 그룹이 없을때 n = len(group) if n

삽입 정렬 삽입 정렬(Insertion Sort)은 첫번째 원소부터 하나하나 차례대로 비교해가면서, 자신보다 큰 값이 나타나면 그 큰 값 앞에 놓는 방식이다. 예를들어, [2, 4, 5, 1, 3] 이 있을때, 비교 대상 2 / 정렬 후 [2, 4, 5, 1, 3] 비교 대상 4 / 정렬 후 [2, 4, 5, 1, 3] 비교 대상 5 / 정렬 후 [2, 4, 5, 1, 3] 비교 대상 1 / 정렬 후 [1, 2, 4, 5, 3] 비교 대상 3 / 정렬 후 [1, 2, 3, 4, 5] 코딩 일반적인 삽입 정렬 unittest 기반으로 작성되었다. test_insertion_sort() 를 참고한다. # -*- coding: utf-8 -*- import unittest class Exam09(unittes..

정렬 정렬(sort)은 자료의 크기를 순서대로 나열하는 것을 뜻한다. 예를들어 아래와 같은 경우를 말한다. • 입력: 정렬할 리스트(예: [35, 9, 2, 85, 17]) • 출력: 순서대로 정렬된 리스트(예: [2, 9, 17, 35, 85]) 선택 정렬 정렬에는 여러가지 방법이 있는데, 본 글은 선택 정렬(Selection Sort)에 대한 내용이다. 다른 방법의 정렬 알고리즘은 아래 글을 참고한다. 2020/03/21 - [Algorithm] - 삽입 정렬 (Insertion Sort) 알고리즘 (with Python3) 2020/03/25 - [Algorithm] - 병합 정렬 (Merge Sort) 알고리즘 (with Python3) 2020/03/25 - [Algorithm] - 퀵 정렬 (..

대학교 과제로 교수님들이 하노이탑 알고리즘을 많이 내준다. (하지만 난 비전공자라 해본적이 없음. 글 쓰면서 오늘 처음 구현해봤다.) 하노이탑 알고리즘 하노이탑은 총 3개의 기둥이 존재한다. (그림 참조) 왼쪽부터 1번째, 2번째, 3번째 기둥이라 할때, 1번째 기둥에서 3번째 기둥까지 원반들을 모두 옮겼을때, 최소 걸린 횟수를 구하는 것이 이번 알고리즘의 목표이다. (단, 그림 아래와 같은 조건이 존재) 목표 첫번째 기둥에서 세번째 기둥으로 원반을 모두 (동일한 순서로) 옮긴다. 제약 조건 원반은 한번에 하나씩만 옮길 수 있다. 옮기는 과정에서 밑에 원반보다 큰 원반이와서는 안된다. (그래서 두번째 기둥을 활용해야 함) 문제 풀이 원반이 1개 일때 첫번째 기둥에서 세번째 기둥으로 옮긴다. 원반이 2개 ..

피보나치 알고리즘 피보나치(Fibonacci) 수열은 첫번째와 두번째 원소가 0 과 1이고, 세번째 원소부터는 이전 원소 두 개의 합인 수열을 말한다. 예를들어, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Python3 코드 아래 코드는 unittest 기반으로 작성했다. 전체 로직은 fibo() 메소드를 참고한다. # -*- coding: utf-8 -*- import unittest class Exam06(unittest.TestCase): @classmethod def setUp(cls): pass def fibo(self, k): if k == 1: return 0 elif k == 2: return 1 return self.fibo(k-1) + self.fibo(k-2) def ..

최대공약수 구하기 1을 제외한 공통 약수 중 최댓값을 최대 공약수(Greater common factor)라고 한다. 예를들어, 4 와 6 의 최대공약수는 2 이다. 15와 40의 최대 공약수는 5 이다. 최대 공약수는 두 수 중 작은 수보다 클 수 없다. 따라서 초기값을 두 수중 작은 값으로 하여 1씩 감소하면서 두 수를 나눴을때 나머지가 없는지 확인한다. 예를들어, 4와 6 중 4가 작다. 4와 6을 4로 나눈다. (4는 나누어 떨어지지만, 6은 나누어 떨어지지 않는다) 3으로 나눈다. (4는 나누어 떨어지지 않는다, 6은 나누어 떨어진다) 2로 나눈다. (둘 다 나누어 떨어진다) 따라서 2가 최대 공약수이다. Python 코드 아래 코드는 unittest 기반으로 작성했다. 주요 로직은 gcd() ..

팩토리얼 문제 1부터 n 까지의 곱, 팩토리얼(factorial)을 구하기 1! = 1 2! = 1 * 2 3! = 1 * 2 * 3 예제. 팩토리얼 구하기 아래 예제는 unittest 기반으로 작성했습니다. 그렇다고 알고리즘을 파악하는데 어려움은 없을것 같습니다. 팩토리얼을 구하는 방법에는 2가지 방법이 있다. test1(): 단순히 for 문을 이용하여 팩토리얼을 구한다. test2(): 재귀함수(recursive)를 이용하여 팩토리얼을 구한다. n! = n * (n-1)! 라는 점화식을 이용하여 재귀함수로 풀 수 있다. # -*- coding: utf-8 -*- import unittest class Exam04(unittest.TestCase): @classmethod def setUp(cls):..

중복을 제거할때는 set 집합을 이용한다. 집합의 특징 중복이 없다. (집합 내의 원소들은 서로 다른 원소를 가진다) 순서가 없다. (원소간의 순서를 가지지 않는다) 중복된 원소를 제거할때, 집합(set)을 이용하면 효율적이다. 예제. 동명이인 찾기 n 명의 주어진 이름들이 있을때, 동명이인인 이름을 찾는다. 예제 입력: Tom Mike Jerry Tom 예제 출력: Tom 코드 2가지 방법으로 풀어볼 수 있다. test1() 메소드와 같이 집합을 이용하는 방법. test2() 메소드와 같이 하나 하나 모두다 비교해서 답을 찾는 방법. # -*- coding: utf-8 -*- import unittest class Exam03(unittest.TestCase): """n 명의 주어진 이름들이 있을때, ..