— basic — N개의 숫자를 입력받아 이 중 임의의 3개의 수를 골랐을 때, 세 수의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N과 S가 주어진다. (3 ≤ N ≤ 20, lSl
≤ 1,000,000) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초)Brute Force
- 이 경우 만약 입력이 아래와 같이 주어졌다면, N=10, S=0이고 3개를 골라 합이 S가 되는 경우는 [1, 2, -3], [3, -2, -1], [10, 11. -21]의 3가지가 있으므로 '3'을 출력해주면 됩니다.
- 이 문제를 어떻게 풀 수 있을까요? 복잡하게 생각할 것 없이 모든 경우의 수를 살펴보는 방법을 생각해보겠습니다. 우선 모든 경우를 판단했을 때 적당한 시간 내에 프로그램이 돌아갈지 확인하겠습니다. n개의 숫자 중 3개를 순서와 상관없이 고르면 되므로, 순열(permutation) nPr에서 r이 3인 경우를 구하면 됩니다. 위의 경우 괄호안에 제시된 조건 내에서 최악의 경우는 N=20인 경우입니다. 이 때, 20개 중 3개를 구하면 되므로 20x19x18 = 6840가지 입니다. 컴퓨터는 물론 사양마다 다르지만 보통 대강 시간을 따질 때 1억번의 단순 연산(덧셈, 뺄셈 곱셈 같은..)을 1초정도로 잡으므로 6840번은 사람에겐 모든 경우를 보자면 몇일 걸리겠지만, 컴퓨터는 0.1초도 안걸리는 쉬운 연산입니다.
- 그럼 구현을 해보겠습니다. N과 S를 입력받는건 숫자니까 int로 받으면 되겠고.. 미리 정해지지 않은 N개의 숫자를 받아둬야 하니 하나하나 변수를 두고 입력받는 것 보다는 그때그때 크기를 조정할 수 있는 배열이나 리스트로 받으면 좋겠습니다. 위의 경우 데이터를 삭제할 일이 없고 대신 임의의 위치의 숫자를 계속 살펴봐야 하니 리스트보다는 배열이 좋겠네요. 3개의 수를 고를 수 있는 모든 경우를 봐야하니 반복문 3개를 중첩해서 사용하면 되겠습니다. 그럼 자바로 짜보면 아래와 같습니다.
- 위와 같이 최악의 경우라도 모든 경우를 컴퓨터로 살펴보기에 문제가 없다면 단순히 모든 경우를 살펴보면 됩니다. 단순히 모든 경우를 보는것도 하나의 알고리즘이라 할 수 있습니다. 결국 알고리즘으로 치자면 가장 쉬운 알고리즘이나, 활용 방법에 따라 최고의 효율을 보여줄 수 있는게 brute force 입니다. 컴퓨터로 어차피 적정한 시간내에 처리될 만한 수준의 데이터라면, 복잡하게 시간들여 생각할 것 없이 그냥 다 보면 되니까요!
— hard —
- 위 문제를 조금만 변형하여 좀 더 생각해보겠습니다.
N개의 숫자를 입력받아 이 중 임의의 R개의 수를 골랐을 때, 고른
R개의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N, R, S가 주어진다. (R ≤ N ≤ 20, lSl ≤ 1,000,000. 2 ≤ R ≤ 7) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초)
- 이번엔 3개를 고르는게 아니고, R개를 고르는 것으로 변경되었습니다. 최악의 경우 nPr에서 n은 20, r은 7일 때이므로 27,907,200개의 경우만 보면 되므로 사람이 직접 모든 경우를 본다면 몇달이 걸리겠지만, 역시 컴퓨터로써는 1초도 걸리지 않는 쉬운 연산입니다. 그런데 짜려고 보니 3개에서 R개를 고르는 것으로만 변경되었는데 난이도가 엄청나게 올라갔습니다. 어쨌든 한번 짜보겠습니다.
- 나머지는 basic에 제시된 문제와 같고.. K개를 살펴보는데 27이 되야하고 그러려면 for문이 2개7개가 중첩이 되야하니깐... 어.. 노가다지만 한번 해보죠!
- ..... case 5부터 이건 사람이 할짓이 아니란걸 깨달았습니다. 이젠 i, j, k 말고 무슨 소문자로 할지도 고민됩니다. 6개일때랑 7개일때도 해야됩니다! 심지어 R이 이문제에선 7까지였지만 100까지 가능하면 어쩔껍니까!
- 위와 같은 이유와, 반복문이 여러개면 코드를 보는것도 힘들다는 이유 등이 합쳐져서, 보통 모든 경우를 볼 때는 재귀함수를 사용합니다. 물론 재귀함수를 현업 일에 쓸 일 자체가 거의 없고, 일반적으로 이후 유지보수를 할 경우 유지보수를 다른사람이 한다면 그 사람이 재귀함수를 이해할 수 있을지 없을지도 모르며, 설계를 잘못하면 메모리 누수로 이어지기 때문에 현업 코드에서는 재귀함수를 잘 쓰지 않습니다. 하지만 안쓰는것과 못쓰는건 다릅니다.
- 재귀함수(=recursive function =재귀호출 =recursion)는 특히 동일한 코드를 반복하는 위와 같은 반복문을 (재귀에 대해 이해만 할 수 있다면) 아주 간단하게 구현할 때 유용합니다. 재귀함수는 일반적으로는 큰 덩어리를 비슷한 형태의 좀 더 작은 조각으로 나누어서 동작시키고, 그걸 더 작은 동작으로 나누고.. 가장 작은 덩어리에서 결과를 내서 다시 큰 덩어리쪽으로 결과를 리턴하며 결과를 합쳐 최종적으로 큰 덩어리를 해결하는 겁니다. 또는 아래 짜둘 코드와 같이 마치 Stack(스택)처럼 굳이 결과를 리턴하지 않고 원하는 깊이까지 들어가는 형태로도 쓰입니다(따라서 스택 자료구조를 사용해서도 똑같이 짤 수 있습니다).
- 사실 재귀함수는 일반적으로 코드를 쭉~따라서 읽기 같은 방법으로 따라가며 살펴보기 어려워서, 이해하는것 자체가 어렵습니다. 따라서 글로는 암만봐도 이해가 안됩니다. 자세하게는 구글링을 통해 찾아보시면 됩니다.
- 그럼 재귀함수를 활용해서 hard에 제시된 문제를 풀어보겠습니다.
- 이전 복잡했던 반복문의 중첩이 간단하게 재귀함수로 합쳐졌습니다. 위의 경우 단순히 보기엔 로직을 이해하기 힘들 수 있으나, 직접 그려보면서 이해해보시면 이해가 되실껍니다. solve 함수를 말로 풀어보면 다음과 같이 동작합니다.
- 우선 base case를 살펴봅니다. 처음 cnt는 0이고, r은 최소 2이니 base case에 들어가지 않습니다.
- 맨 처음 main함수에서 solve 함수를 호출할 때 idx가 -1로 들어오고, i는 idx+1에서 시작하니 0부터 시작합니다.
- 0이었던 sum에 input배열의 0번 idx 값을 더합니다.
- solve함수에 현재 idx인 i를 넣고, '2'에서 합친 sum을 넣고, cnt를 1 증가시켜줍니다.
- 다시 solve 함수가 실행되고 현재 cnt는 1 입니다. 역시 base case에 충족되지 않으니 다음으로 넘어갑니다.
- 이번엔 i가 1부터 시작됩니다. (이전 복잡했던 반복문에서 i=0, j=i+1, ...로 진행한것과 마찬가지 동작) sum에 input[1]을 더해주고 다시 solve 함수로 들어갑니다.
- ...... 진행하다보니 base case를 충족하는 경우가 발생했습니다. 즉, 문제에서 제시된 R번만큼 숫자를 더했습니다. 그렇다면 이제 현재까지의 sum을 보고 S와 비교합니다. 같다면 resultCnt를 1 증가하고 종료합니다. 같지 않더라도 종료합니다. (이와 같이 재귀 함수에는 어떠한 경우에도 재귀함수가 무한으로 호출되지 않도록 종료시켜주는 base case가 반드시 필요합니다. 이걸 제대로 설정하지 못하면 메모리 누수. 스택 오버플로우 등의 문제가 발생하게 됩니다.)
- '7'에 해당하는 solve 함수를 호출했던 solve함수의 for문으로 다시 돌아옵니다. 그럼 '7'에 해당하는 solve함수로 들어가기 전 더해뒀던 input[어딘가]의 값을 다시 빼줍니다. for문의 다음 loop에 영향을 끼치면 안되니까요.
- ... 반복
- 이상입니다.