beepbeep

알고리즘 문제를 풀던 중 다음 순열을 구하는 문제가 나왔습니다. 그래서 관련 내용을 공부한 후, 정리해 보았습니다. 다음 순열(Next Permutation)이란? 일단 다음 순열을 구하기 위해선, 다음 순열이 무엇인지부터 살펴보아야 할 것 같습니다. 1, 2, 3 예를 들어서 1부터 3까지 적힌 카드가 주어지고, 이 카드를 나열해서 백의 자리 수를 만들어본다고 하면 세 카드를 이용해서 만들어낼 수 있는 백의 자리 수 중 가장 작은 숫자는 123입니다. 그 다음으로 작은 숫자는 132이고, 또 그 다음번 숫자는 213이 됩니다. 만들어낼 수 있는 백의 자리 수를 전부 찾아 오름차순으로 나열하면 다음과 같습니다. 123 132 213 231 312 321 만들어진 백의 자리 숫자를 다시 세 개의 카드로 분..

문제 int 자료형 배열이 주어집니다. 배열에서 두 값을 꺼내서 용기를 만들어보려고 합니다. 이 때 두 값은 용기의 양쪽 높이가 되고, 두 값의 인덱스의 차이는 너비가 됩니다. 예를 들어 [1, 3, 7, 4, 5] 라는 배열이 있고 이 배열에서 3과 5를 꺼냈을 때, 상자의 한쪽 높이는 3, 반대쪽 높이는 5가 되고 상자의 너비는 두 값의 인덱스의 차이인 3(4 - 1)이 됩니다. 이렇게 만든 2차원 모양의 용기에 물을 담으려고 합니다. 가장 많은 양의 물을 담을 수 있는 용기를 찾아서, 그 용기에 담을 수 있는 물의 양을 계산하세요. 살펴보기 생각을 정리하다보니 내용이 길어졌는데... 요약하면 다음과 같다. 문제 핵심) 1. 인덱스를 가운데로 옮길 때마다 용기의 너비가 줄어든다. 즉, 담을 수 있는 ..

문제 살펴보기 일명 Happy Number를 찾는 문제이다. Happy Number를 찾는 방법은 다음과 같다. 1. 주어진 숫자에서 모든 자릿수의 제곱의 합을 구한다. 2. 제곱의 합이 1이 나올때까지 반복 수행한다. 3. 제곱의 합이 1이 나오면 Happy Number이다. 4. 제곱의 1이 나오지 않으면 1번이 무한히 반복된다. 예시) 주어진 숫자가 23인 경우 2^2 + 3^2 = 13 1^2 + 3^2 = 10 1^2 + 0^2 = 1 23은 Happy Number 생각해보기 숫자가 Happy Number가 아니라면, Happy Number를 찾는 연산이 무한히 반복된다고 한다. 즉, 연산 과정에서 특정한 숫자가 반복해서 얻어지게 된다. 예를 들어, 주어진 숫자가 4인 경우 4^2 = 16 1^..

문제 살펴보기 int 자료형 배열이 주어진다. 배열의 인덱스는 일차에 해당하고, 각 숫자는 해당 일차의 주식 매매가를 의미한다. 예를 들어 [3, 5, 9]와 같은 배열이 주어진 경우 다음과 같은 의미를 가진다. 인덱스 0, 숫자 3 -> 0일차, 주식 가격 3 인덱스 1, 숫자 5 -> 1일차, 주식 가격 5 인덱스 2, 숫자 9 -> 2일차, 주식 가격 9 주어진 배열을 바탕으로, 주식을 구매하고 다시 팔아서 수익을 남기려고 한다. 최대 얼마의 수익을 낼 수 있을까? 생각의 흐름 1. 구매하는 일자(인덱스)는 판매하는 일자(인덱스)보다 빨라야 한다. 2. 이중 반복문을 사용할 경우 계산 시간이 너무 길어져 시간 초과가 된다. 이 문제의 핵심! 2번 이유로 인해 이중 반복문을 사용할 수 없다. 최저값과..