방배동 고구마

순열은 조합과는 다르다. 순열은 순서가 중요시 되는 수열이다. 예를들어 5개의 숫자 중 3개를 순서에 상관없이 고르는 것은 조합이다. 즉, 조합에서 (1,2,3)과 (3,2,1)는 같은 경우로 판단된다. 그러나 순열은 다르다. 순서가 중요하기 때문에 순열에서 (1,2,3)과 (3,2,1)은 다르다. 중고등학교에서 배웠던 공식이 기억날 것이다. 사실 기억나지 않는다. 0!은 1이다. 기억을 더듬어 5개의 숫자중에 3가지를 뽑아내는 조합의 경우의 수는 10이며, 순열은 60가지가 되겠다. 이를 코드로 어떻게 구현할 수 있을까? 순열 보통의 경우 DFS 알고리즘으로 순열을 구현할 수 있다. 5가지의 수 중에 3가지를 뽑아내는 순열의 경우는 아래와 같다. void Dfs_permutation(int level)..

문제 N개의 샘플이 있고 각각의 샘플에는 정수가 주어진다. 연구를 위해 N개중 2개의 샘플을 채취한다. 이때 샘플이 가진 정수의 합이 0에 가까운 2개의 샘플을 채취하고자 한다. N(2~100000), 정수A(-1000000 ~ +1000000) 이며 샘플의 정수 값으 오름차순으로 입력된다고 한다. 0에 가까운 값이 여러 경우일 경우 가장 빠른 번호의 샘플을 답으로 한다. 위 조건에 맞는 2개의 샘플 번호를 구하라 입력 5 -102 -58 59 78 101 출력 0 4 문제해결 조합 문제이다. N개의 샘플중 2개의 샘플을 고른다. 순서는 상관이 없다. 트리를 구성하는 DFS로 모든 경우의 수를 수행할 수도 있지만 N이 10만개이므로 시간복잡도 N제곱으로 timeout일 경우가 생긴다. 따라서 DFS는 적..