고양이 두 잔

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..

그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 불린다. 현재 상황에서 당장 눈앞에 보이는 최적의 결과를 선택해 나가는 방식이기 때문인데, 가장 간단한 예는 다음과 같다. 주어진 자료구조에서 가장 큰 합을 찾아내는 과정인데, 그리디 알고리즘은 그때그때 눈앞의 숫자 중 큰 쪽을 선택하는 것을 볼 수 있다. 구체적으로는 다음과 같이 단계를 셋으로 나눌 수 있다. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택 적절성 검사(Feasibility Check): 선택된 해답이 문제의 조건을 만족하는지 검사 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복 또한 위의 트리구조의 예에서..

목차 효율적인 알고리즘이란 입력값의 증가에 따른 시간의 비율을 최소화한 것이다. 따라서 효율적인 알고리즘을 고민한다는 것과 시간 복잡도를 낮춘다는 건 같은 말이 된다. 시간 복잡도란 '입력값과 연산 수행 시간의 상관관계를 나타내는 척도'이며, 쉽게 말하면 아래와 같다. 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 시간 복잡도를 표기하는 방법은 다음의 세 가지가 있으며, Big-O(빅-오) - 최악의 경우 고려 Big-Ω(빅-오메가) - 최선의 경우 고려 Bid-θ(빅-세타) - 중간(평균)의 경우 고려 언제나 최악의 경우를 고려하는 것이 바람직하기 때문에 빅-오 표기법이 많이 쓰인다. O(f(n))과 같이 표시하며, 이는 입력값 n이 증가할 때 연산 횟수가 f(n..

그래프의 탐색은 모든 정점을 한 번씩 방문하는데 그 목적이 있다. 지도 애플리케이션에서 두 지점 사이의 경로를 검색할 경우를 생각 해보면, 최소 시간이나 최소 환승 등 여러 가지 검색 기준이 있다. 이와 비슷하게 그래프의 모든 정점을 방문하는 방법에도 크게 두 종류가 있는데, BFS(Breadth-First Search) - 너비 우선 탐색과 DFS(Depth-First Search) - 깊이 우선 탐색이 그것이다. BFS(Breadth First Search) 너비 우선 탐색(BFS)은 시작 정점부터 가장 가까운 순서대로 정점을 방문하는 방법이다. 최초 시작 정점과 인접한 정점을 모두 방문한 뒤, 각 순회된 정점부터 시작하여 인접한 정점을 방문하는 방식을 반복한다. 출처: https://minhamin..

Graph(그래프)는 노드 사이의 연결 관계를 표현할 수 있는 자료구조이다. 앞서 보았던 트리구조 역시 사실은 그래프의 일종인데, 두 구조의 차이는 아래와 같다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 단방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능 순환 불가능 자기 자신을 연결하는 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 루트의 개념이 있거나 없을 수 있음 하나의 루트 노드 존재 모델 네트워크 모델 계층 ..

Tree 자료구조 Tree(트리)는 주로 계층적인 구조를 표현하기 위해 사용한다. /Users/username 토너먼트 경기의 대진표 조직도 트리구조는 루트(Root)라는 최상위 노드에서 시작해 각 데이터를 간선(Edge, Link, Branch)으로 연결한다. 두 개의 노드가 상하관계를 가질 때 위의 노드를 부모 노드(Parent Node), 아래의 노드를 자식 노드(Child Node)라 부른다. 자식 노드가 없는 노드를 리프 노드(Leaf Node)라고 하며, 리프 노드를 제외한 노드를 인터널 노드(Internal Node)라 부른다. 또한 트리구조는 깊이와 레벨, 높이를 측정할 수 있는데 그 정의는 아래와 같다. 깊이(Depth) - 루트로부터 특정 노드까지의 간선 개수. 위 Animal의 경우 ..

Queue는 (대기)줄이라는 의미를 가지고 있다. 위 그림에서 보는 것처럼 데이터의 입력과 출력 방향이 따로 정해져 있으며, 먼저 들어간 데이터가 먼저 나오는 선입 선출(FIFO - First In First Out) 구조를 가지고 있다. 또한 스택의 경우와 마찬가지로 데이터의 입출력을 하나씩만 할 수 있다는 특징도 가지고 있다. 추가로 큐에 데이터를 집어넣는 동작을 'enqueue'라고 하며, 데이터를 빼는 동작을 'dequeue'라고 부른다. 주로 프린터의 출력 순서 알고리즘과 같이 이벤트의 실행 순서를 규칙적으로 만들기 위해 사용되는 큐는 태생적으로 LinkedList와 함께 사용된다. import java.util.LinkedList;//import import java.util.Queue;//i..

Stack은 더미, 퇴적, 쌓다 등의 의미를 지니고 있다. 하노이의 탑 퍼즐에서 기둥에 원판을 꽂듯이 데이터를 쌓는 구조라고 할 수 있는데, Stack(스택)의 가장 큰 특징은 바로 이 퍼즐과 같이 후입 선출(LIFO - Last In First Out)로 동작한다는 것이다. 설명을 추가로 덧붙이자면 스택 자료구조는 반드시 데이터를 하나씩만 넣고 뺄 수 있고, 그림에서 보이는 것과 같이 단 하나의 입출력 방향을 가지고 있다. 브라우저의 앞으로 가기나 뒤로 가기 기능을 구현할 때 사용되는 스택 자료구조는 간단하게 사용 가능하다. import java.util.Stack; // import Stack stack = new Stack(); // Integer형 스택 선언 위와 같이 먼저 Stack 클래스를 i..