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. 인덱스를 가운데로 옮길 때마다 용기의 너비가 줄어든다. 즉, 담을 수 있는 ..