고양이 두 잔

문제 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. A와 B는 공백 한 칸으로 구분되어져 있다. 출력 첫째 줄에 다음 세 가지 중 하나를 출력한다. A가 B보다 큰 경우에는 '>'를 출력한다. A가 B보다 작은 경우에는 '

중복 조합은 조합과 비슷하게 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; // 배열..

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 - 나눠진 작은 문제에서 구한 답을 이용해 전체 문제의 답을 구할 수 있다. 가 그것이다. 가장 쉬운 예로 피보나치수열을 들 수 있는데, 재귀 함수만을 이용..

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

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