c++ 썸네일형 리스트형 Next Permutation Permutation(순열)은 프로그래밍에서 흔하게 사용되는 개념이다. 나무 위키에는 다음과 같이 정의되어 있다. 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다. 위의 순열의 개념에서 "순서에 상관있게"를 "순서에 상관없게"로 바꾼 개념이 바로 조합(Combination)이다. n과 r이 일정한 수로 주어졌을 때, 어느쪽이 경우의 수가 더 많이 도출될까? 당연하게도, 순열이 그 경우의 수가 훨씬 많다. $_nP_r = n \times(n-1) \times (n-2) \times ... (n-r+1) =$ $n!\over(n-r)!$ $_nC_r = $ $_nP_r\over r! $ = $1\over r!$ $n!\over(n.. 더보기 [DP] BJ_2775, 부녀회장이 될테야 [문제의 접근] 이 문제에서의 핵심은 바로 다음 글귀이다. "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다." 이 것을 읽고 어떤 생각을 해야할까? 특이한 조건이네 이렇게? 특이한 조건인건 맞다. ㅎㅎ. 많은 알고리즘 문제에서는 스토리를 만들어내기 위해 사실 별로 필요없는 문구들도 많이 넣기는 하는데, 위의 문구를 보면 아래와 같은 수식을 떠올려야 한다. 우리는 알고리즘 문제를 풀고 있고 알고리즘은 수식으로 이루어지니 말이다. arr[a][b] = arr[a-1][1] + arr[a-1][2] + ... arr[a-1][b] 그럼 이 문제를 위의 수식 그대로 풀어내면 될까? test case의 T의 숫자가 주어지지 않아서 명확하진 않지만.. 더보기 [Two-Pointer] BJ_2230, 수 고르기 [문제의 접근] 두 수를 선택하고, 두수의 차이가 M이상이면서 가장 작은 차이를 구해야 한다. 어떻게 접근해야 할까? Bruteforce로 접근하면 가장 쉽게 접근법을 생각할 수 있다. 즉 모든 경우의 수를 비교해 보는 것이다. N개의 수 중에서 2개의 수를 임의로 선택해야 하기 때문에, $O(N^2)$ 시간 복잡도가 나온다. For 문을 계층적으로 2번 돌린다고 생각하면 쉽다. 첫번째 수를 정하고 N-1개 비교, 2번째 수를 정하고 N-2개 비교,.... 현재 N이 1,000이하라면 충분하겠지만, 주어진 값은 N이 100,000 으로 주어져 있다. 연산량은 $10^{10}$으로 대략적인 1초의 연산량 $10^8$을 초과하므로 시간초과다. 그럼 어떻게? $O(n\log_{2}{n})$의 접근이나, $O(.. 더보기 [DFS] BJ_13023, ABCDE [문제의 접근] 어떻게 이 문제에 접근할 수 있을까? 일단, 친구 관계로 주어지는 입력이 graph로 표시될 수 있다는 것을 알아야 한다. 또한 graph의 깊이가 4단계 까지만 진행할 수 있다면 문제의 답으로 도출할 수 있는 것으로 보아 그렇게 깊게 탐색할 필요가 없다는 사실도 알 수 있다. 모든 경우를 다 탐색해 봐야 하는 문제일까? 아니다. 5명이 친구가 되는 케이스가 하나만 있다면 탐색을 종료하고 답을 도출하면 된다. 그렇다면 어떤 알고리즘을 사용해야 할까? 바로 DFS이다. [DFS의 특징] 탐색 가능한 경로의 모든 방향의 Graph를 탐색하여 답을 도출하는 BFS와는 다르게 DFS는 모든 경로를 체크하는 대신 한 경로 우선하여 마지막 깊이까지 진행하여 조건을 만족할 수 있다면 다른 경로를 탐색.. 더보기 이전 1 다음
