버블 정렬 버블 정렬(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 명의 주어진 이름들이 있을때, ..

zipfile 모듈은 Python 3.3 이상부터 지원해준다. 파일 압축 본 예제에서는 디렉토리와 그 하위 모든 파일들을 압축하고 있다. src_path = r"압축하고 싶은 디렉토리 경로" base_path, dir_name = os.path.split(src_path) trg_zip_name = dir_name + ".zip" cur_path = os.getcwd() # 현재 디렉토리 경로 변경 os.chdir(base_path) try: with zipfile.ZipFile(trg_zip_name, "w", zipfile.ZIP_DEFLATED) as f: for base_dir, dirs, files in os.walk(src_path): for file in files: # 상대 경로를 구한다...

메이븐 프로젝트에 적용하는 방법은 아래 글 참고 2020/10/31 - [Spring/Spring Boot] - Spring Boot, Maven 프로젝트에 롬복 적용하기 Spring Boot, Maven 프로젝트에 롬복 적용하기 Gradle 프로젝트에 롬복 적용하는 방법은 아래 글 참고 2020/03/07 - [Spring/Spring Boot] - Spring Boot 롬복(Lombok) 적용 / Gradle과 IntelliJ 사용 Spring Boot 롬복(Lombok) 적용 / Gradle과 IntelliJ 사용.. memostack.tistory.com 롬복(Lombok) 이란? 롬복(lombok)을 이용하면 getter, setter, constructor 를 매번 생성할 필요가 없다. 롬복은..

1. Dependency 적용 build.gradle에 swagger2 를 추가한다. (https://mvnrepository.com/artifact/io.springfox/springfox-swagger2/2.9.2) dependencies { ... // Swagger 2 compile group: 'io.springfox', name: 'springfox-swagger2', version: '2.9.2' compile group: 'io.springfox', name: 'springfox-swagger-ui', version: '2.9.2' ... } 웹 UI 화면을 보려면, springfox-swagger-ui 를 추가해야 한다. 2. Swagger2 Enable @EnableSwagger2 어노..

Git 을 사용하는 개발자마다 Commit 형식을 다르게 사용하다보니, 통일성이 없고 가독성이 떨어진다. 효율적인 의사소통을 위하여 커밋 메세지를 작성하는 방법도 통일할 필요가 있다. 좋은 메시지 작성하기 동명사(~ing)보단 명사를 사용한다. 부정문을 사용한다. 관사(a, an, the)는 사용하지 않는다. 자주 사용하는 영문구 Fix 수정, 고치다 버그 등 기능상에 문제가 있거나 수정해야하는 부분이 있을때 주로 사용한다. Fix A A 를 수정한다. Fix A in B B 안의 A 를 수정한다. Fix A witch B 또는 Fix A that B B 절의 A를 수정한다. Fix incorrect type which makes animated gifs not loop forever on device ..

순열 [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..

Scala의 열거형 스칼라에는 경로 의존 타입 (path-dependent type)을 활용한 열거형(enumeration type)이 있다. 경로 의존 타입과 관련된 추상 타입의 상세 내용 > 2020/02/23 - [Language/Scala] - Scala 추상 타입 (type T) 스칼라의 Enumeration 을 이용한다. (패키지: scala.Enumeration) object Color extends Enumeration { // scala.Enumeration val Red = Value val Blue = Value val Green = Value } 짧게 작성하는 것도 가능하다. object Color extends Enumeration { val Red, Blue, Green = Va..

추상 타입 추상 타입을 이용하면 선언 시점에서 어떤 타입인지 알려지지 않은 타입을 참조할 수 있다. 추상타입을 사용하지 않는 아래 예제를 보면 class Food abstract class Animal { def eat(food: Food) } class Grass extends Food class Cow extends Animal { // override def eat(food: Grass) {} // 파라미터 타입이 다르기 때문에 오버라이드 할 수 없다. override def eat(food: Food) {} } 동물(Animal)은 음식(Food)을 먹는다. 소(Cow)는 풀(Grass)을 먹는다. (소는 동물을 상속받고, 풀은 음식을 상속받는다) 하지만, 파라미터가 다르기 때문에 Animal을 ..

추상 val 초기화시 문제점 아래와 같이 (추상 val을 가진) 트레이트를 인스턴스화하여면, 추상 val의 정의를 구현해야 한다. trait RationalTrait { val numerArg: Int val denomArg: Int require(denomArg != 0) } 위 예제(트레이트)는 분수를 표현하는 트레이트이다. (numerArg: 분자, denomArg: 분모) 따라서, denomArg 는 0이 될 수 없다. 만약 위 Rational 이 트레이트(Trait) 가 아닌 클래스였다면, new Rational(expr1, expr2) 와 같이 구현할 수 있다. new Rational(expr1, expr2) 실행 순서 expr1, expr2 식을 계산한다. Ratinal()을 초기화 한다. ..

트레이트에 추상 멤버를 정의한다. trait Abstract { type T def transform(x: T): T val initial: T var current: T } 타입멤버 (T), 메소드 (transform), val(initial), var(current) class Concrete extends Abstract { type T = String override def transform(x: String): String = x + x override val initial: T = "hi" override var current: String = initial } 타입 멤버 (T) 스칼라에서 추상 타입은(abstract type) 클래스나 트레이트의 멤버로 정의없이 선언만된 타입이다. type ..