파이썬 정렬 메소드 파이썬에서는 정렬을 할때 sort() 와 sorted() 메소드를 사용한다. sort() sort() 메소드는 리스트를 오른차순으로 정렬해준다. >>> data = [3, 6, 12, 7, 10, 99, 23, 5, 9] >>> data.sort() >>> data [3, 5, 6, 7, 9, 10, 12, 23, 99] sorted() sorted() 메소드는 오름차순으로 정렬 후 새로운 리스트를 반환해준다. >>> data = [3, 6, 12, 7, 10, 99, 23, 5, 9] >>> sorted(data) [3, 5, 6, 7, 9, 10, 12, 23, 99] 파이썬에서는 어떤 정렬 알고리즘을 사용할까? 흔히 알고리즘을 배우면 아래 5가지 정렬 알고리즘을 배운다. 선택 정..

버블 정렬 버블 정렬(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] - 퀵 정렬 (..

피보나치 알고리즘 피보나치(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 명의 주어진 이름들이 있을때, ..

순열 [1, 2, 3]의 순열은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 이다. 이처럼 같은 원소가 중복되지 않고, 조합하여 나올 수 있는 모든 경우의 집합을 뜻한다. 재귀와 스택을 이용해서 순열을 생성하는 코드를 작성한다. 코드 아래 2가지 자료구조를 사용한다. Stack stack: 원소를 담을 스택 boolean[] chosen: 이미 포함한 원소를 구분하기 위한 불리안 배열 private static void search(Stack stack) { if (stack.size() >= n) { System.out.println(stack.toString()); } else { for(int i=1; i= n) { System..

멱집합 구하기 Stack과 Recursive를 이용하여, 멱집합 (Power Set) 을 구한다. {1, 2, 3} 집합의 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다. (공집합 포함) Java 코드 재귀함수 search() search() 메소드를 생성한다. private static void search(Stack stack, int k) { if(k >= n + 1) { System.out.println(stack.toString()); // 부분 집합을 출력한다. } else { // k를 부분집합에 포함한다. stack.add(k); search(stack, k + 1); // k를 부분집합에 포함하지 않는다. stack.pop..

최댓값 찾기 최댓값을 찾는 알고리즘 상당히 간단한 알고리즘이다. (하나하나 비교하면 됨) 하나씩 비교를 하다보니 시간복잡도는 O(n)이 된다. 코드 본 글에서는 unittest를 이용하여 알고리즘을 풀이합니다. 로직이 달라지는것은 아닙니다. 사실 파이썬에는 max() 라는 내장함수를 제공해주는데, max([5, 3, 2]) 안에 숫자로 구성된 리스트를 넣어주면 알아서 최댓값을 반환해준다. # -*- coding: utf-8 -*- import unittest class Exam02(unittest.TestCase): @classmethod def setUpClass(cls) -> None: cls.items = [10, 92, 4, 7, 44, 80, 98, 50, 74, 32] ...생략... def ..