방구석프로의 이야기

https://www.acmicpc.net/problem/1010

문제 해결을 위한 과정

이 문제는 순서를 중요하게 생각하지 않는 '조합'의 방식으로 해결할 수 있는 문제였습니다. 동시에 팩토리얼 연산을 해야 하므로 Dynamic Programming의 방식 역시 문제 풀이의 한 요소였습니다.

팩토리얼을 우리가 흔히 아는 방식 즉 재귀적으로 구현하게 되면 한번 구한 연산을 지속적으로 반복하기 때문에 필요 없는 수많은 연산을 하게 되어 많은 컴퓨팅 리소스를 잡아먹게 됩니다. 또한 당연하게도 시간제한에 걸리게 됩니다. 따라서 이를 시간 내에 구현할 수 있게 하기 위해 피보나치수열 혹은 팩토리얼의 경우 탑다운 또는 보텀업 방식을 이용하여 해결합니다. 

문제에서 N <= M이라는 조건으로 생각해보면 결국 M개의 사이트 중에서 순서에 상관없이 N개를 뽑는 경우입니다. 가령 N이 2개이고 M이 3개일 시, 3개의 M 중에서 2개를 순서에 상관없이 뽑는 경우입니다. (예를 들면 AB, AC, BA, BC, CA, CB) 이를 염두에 두고 소스코드를 작성하면 다음과 같습니다.

소스코드

위 소스코드에서 b//a는 mPn이고 이 결과를 c로 나눠야 mCn입니다.

https://programmers.co.kr/learn/courses/30/lessons/68644

문제

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예

numbersresult

입출력 예 설명

입출력 예 #1

• 2 = 1 + 1입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3입니다.
• 5 = 1 + 4 = 2 + 3입니다.
• 6 = 2 + 4입니다.
• 7 = 3 + 4입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

• 2 = 0 + 2입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

문제 해결을 위한 과정

이 문제의 경우 Level 1 문제로 어렵지 않은 문제였습니다. 리스트로 주어진 숫자 중에서 2개의 숫자를 골라서 그 합을 출력을 하는 문제입니다. 입출력 예 #1을 보면 2, 1, 3, 1, 4인데 3 + 4 = 7, 4 + 3 = 7로 순서가 상관이 없으므로 순열이 아닌 조합의 방법을 사용해야 한다는 것을 알 수 있습니다. 따라서 해당 리스트에서 2개의 숫자를 골라서 그 합을 answer리스트에 넣어주면 됩니다.

문제 해결을 위한 팁

조합을 하여 계산을 하면 중복되는 것들이 문제가 됩니다. 입출력 예제 #2를 보면 5, 2를 뽑아서 5 + 2 = 7과 0 , 7을 뽑이서 합한 값인 0 + 7 = 7이 중복이 되는 것을 확인할 수 있습니다. 이 경우는 집합의 정리를 활용하면 쉽게 해결할 수 있습니다. 집합은 중복을 허용하지 않기 때문입니다. 따라서 set()을 이용하면 아주 손쉽게 중복을 제거할 수 있습니다. 그 후 출력방식에 맞게 다시 리스트로 변경을 해주면 됩니다.

소스코드