고양이 두 잔

스프링 부트는 스프링의 문제점이던 복잡한 세팅 문제를 해결하며 탄생한 스프링 프로젝트 중 하나다. 지난번 글에서 스프링 부트를 사용하면 코드가 얼마나 간결해지는지 알아봤었는데, https://gnidinger.tistory.com/450 [Spring]Spring Framework, Spring Triangle Spring Framework, 혹은 Spring은 Java/Kotlin을 기반으로 한 오픈소스 웹 프레임워크이다. 특히나 엔터프라이즈급 애플리케이션 개발에 필요한 기능이 종합적으로 포함되어 있는데, 대한민국 전자정부 gnidinger.tistory.com 이번 글에선 다른 예를 들어서 간결함을 보기로 하자. 스프링 부트의 핵심 철학은 "구성은 Spring에게 맡겨버리고 비즈니스 로직에만 집중하자..

Spring Framework, 혹은 Spring은 Java/Kotlin을 기반으로 한 오픈소스 웹 프레임워크이다. 특히나 엔터프라이즈급 애플리케이션 개발에 필요한 기능이 종합적으로 포함되어 있는데, 대한민국 전자정부 표준프레임워크의 기반 기술로도 쓰이도 있다. 엔터프라이즈급 애플리케이션 - 기업을 대상으로 하는, 대규모 데이터와 트랜잭션 처리가 이루어지는 앱 Framework(프레임워크) 특정 목적을 위해 설계된 구조 혹은 뼈대 소프트웨어의 설계와 구현을 위해 재사용이 가능한 일련의 클래스와 라이브러리를 제공하는 것 앱 개발을 위한 기초 프로그램이자 반제품 Framework = Design Pattern(재사용 가능한 솔루션) + Library, 즉 라이브러리를 포함한 개념 Library와 Framew..

멱집합은 주어진 집합의 모든 부분집합들로 이루어진 집합이다. 예를 들어 A = {1, 2}라고 하면 A의 부분집합은 ∅(공집합), {1}, {2}, {1, 2}의 네 개다. 이때 A의 멱집합은 {∅, {1}, {2}, {1, 2}}가 된다. n개의 원소를 가진 집합의 부분집합은 2^n 개이므로, 멱집합의 원소의 개수도 2^n개가 된다. 자바에서 멱집합을 구현할 때는 Stack과 재귀 함수를 이용하면 간단하게 작성할 수 있다. import java.util.Stack; public class PowerSet2 { public static void main(String[] args) { char[] characters = {'a', 'b', 'c'}; // 멱집합을 구할 집합 Stack stack = new..

중복 조합은 조합과 비슷하게 n개의 요소 중 r개를 순서에 상관없이 뽑는데, 중복을 허용하여 뽑는 경우의 수이다. 유도 과정은 생략하고, 실제로 어떻게 동작하는지는 아래 그림을 보면 쉽다. 5개의 요소 중 중복 조합으로 2개를 뽑는 경우의 수를 나타내고 있다. 중복 순열을 구현할 때와 비슷하게 isVisited 배열을 제거하고, 재귀 함수를 호출할 때 i + 1이 아닌 i부터 대입해 중복을 허용하면 된다. public class CombinationWithRepetition { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; // 중복 조합을 만들 배열 int n = arr.length; int r = 2; comb(arr, n..

중복 순열은 순열과 비슷하게 n개의 요소 중 r개를 순서에 상관있게 뽑는데, 중복을 허용하여 뽑는 경우의 수이다. 순서가 중요하되 중복을 허락한다는 말은 다음 그림을 보면 명확하다. {A, B, C}세 개의 원소중 중복순열을 이용해 3개를 뽑는 경우의 수를 나타낸 그림이다. 자바로 구현하는 경우에도 중복을 허용한다는 부분만 반영을 해주면 된다. 이전 글에서 사용했던 코드의 경우, 중복을 피하기 위해 넣었던 isVisitied 배열을 제거하면 간단하다. public class PermutationWithRepetition { public static void main(String[] args) { int[] arr = {1, 2, 3}; // 순열을 만들 배열 int n = arr.length; // 배열..

유클리드 호제법은 두 양의 정수, 혹은 다항식의 최대공약수를 구하는 알고리즘이다. 기원전 300년에 그리스의 수학자 유클리드에 의해 기술된 이 알고리즘은 인류 최초의 알고리즘이라는 호칭도 가지고 있다. 그 내용은 다음과 같다. 유클리드 호제법 두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)이다. 이때 r = 0이라면, a, b의 최대공약수는 b가 된다. 쉽게 말하면 큰 숫자를 작은 숫자로 나누고, 그 나머지로 작은 숫자를 나누는 계산을 나머지가 0이 될 때까지 반복하는 것이다. 예를 들어 1096과 411의 최대공약수를 구한다고 해보자. 첫 계산은 다음과 같다..

Java+Python으로 더 간결하게 순열/조합/중복순열/중복조합 구현하기 [Java+Python]15649번, N과 M(1), 순열 [Java+Python]15650번, N과 M(2), 조합 [Java+Python]15651번, N과 M(3), 중복순열 [Java+Python]15652번, N과 M(4), 중복조합 순열(Permutation) 순열은 서로 다른 n개의 원소에서 r개를 중복 없이, 순서에 상관있게 뽑아 나열하는 것이다. nPr의 형태로 자주 표현되며, 그 경우의 수는 아래와 같다. 순열을 탐색할 땐 재귀 함수로 표현하는 것이 편한데, 이 경우 해당 인덱스의 숫자가 사용 중인지 판단하는 배열이 따로 필요하다. 이미 뽑은 숫자라면 넘어가야 하기 때문이다. import java.util.Arr..

동적 계획법이란 미리 구해뒀던 답을 이용해 하나의 연산은 한 번만 하도록 하는 프로그래밍 패러다임이다. 지난 글에서 알아본 그리디 알고리즘이 그때그때 최적의 값을 찾아가는 방법이라면, 동적 계획법은 문제를 쪼개 모든 경우의 수를 살펴본 뒤 답을 구한다. 다만 연산 속도의 향상을 위해 이미 계산한 값을 저장해두는데, 이때 사용되는 메모리를 캐시(Cache)라고 한다. 동적 계획법이 적용될 수 있는 조건은 두 가지가 있는데, Overlapping Subproblem - 큰 문제를 중복되는 작은 문제로 나눌 수 있다. Optimal Substructure - 나눠진 작은 문제에서 구한 답을 이용해 전체 문제의 답을 구할 수 있다. 가 그것이다. 가장 쉬운 예로 피보나치수열을 들 수 있는데, 재귀 함수만을 이용..

자바에서 정렬을 하려면 Arrays 클래스가 import 되어야 한다. import java.util.Arrays; 오름차순 정렬의 경우 문자열이나 정수형이나 같은 방법을 이용한다. int[] arr = {3, 7, 4, 1, 0, 6}; String[] arr2 = {"AD", "GA", "ET", "BX", "GY"}; Arrays.sort(arr); Arrays.sort(arr2); System.out.println(Arrays.toString(arr)); System.out.println(Arrays.toString(arr2)); // 출력 결과 [0, 1, 3, 4, 6, 7] [AD, BX, ET, GA, GY] 내림차순 정렬의 경우엔 문자열과 정수형의 방법이 다르다. 정수형의 경우 Integ..

완전 탐색이란 컴퓨터의 성능을 믿고 모든 경우의 수를 다 체크하는 방법이다. 상대적으로 구현이 간단하고, 해가 존재한다면 반드시 찾을 수 있는 방법이기도 하다. 예를 들어 숫자 4자리로 구성된 자물쇠의 암호를 푼다면, '0000'부터 '9999'까지 다 넣어보는 방식이다. 당연하게도 최적의 솔루션을 제공해주지 않으며, 때문에 다음 두 상황에 주로 쓰인다. 적용 가능한 다른 알고리즘이 없을 때 복수의 솔루션을 확인해야 할 때 예를 들어 책 한 권이 주어지고 그 책에서 '고양이'라는 단어를 찾아야 한다고 가정해보자. 책은 당연하게도 단어들이 정렬되어 있지 않으므로 처음부터 끝까지 단어를 비교하는 수밖에 없다. 이럴 때 사용되는 것이 완전 탐색 알고리즘이며, 이 경우 시간 복잡도는 O(n)이다. 계속해서 완전..