728x90 반응형 재귀33 조합의 모든것 풀어봅시다 조합은 무엇일까요? 재귀를 이용하여 조합을 뽑기 전에 조합은 어떤 모양을 가지고 있는지 알아야 함으로 어떻게 생겼는지 먼저 알아봅시다. 조합은 Combination 으로 nCr n개의 나열된 숫자에서 r개를 뽑는 것을 말합니다. 하지만 앞서있는 블로그에 순열의 모든것 풀어봅시다 에서 순열과 다른 점은 순서가 달라도 내용물이 같다면 같은 집합임으로 그 경우를 빼고 뽑아야 합니다. 그래서 순열보다 반 정도가 적게 나오게 됩니다. 예를 들어 1, 2, 3, 4의 숫자에서 2개의 숫자를 뽑는다면 경우는 노란 블록인 경우와 파란 블록 중 하나인 경우가 조합입니다. 그냥 쉽게 노란 블록이라고 보시면 되고 파란 블록은 노란 블록가 위치만 다를 뿐 같은 내용물을 가지고 있으므로 같은 경우이기 때문에 제외하셔야 합니다... 2019. 8. 20. 순열의 모든것 풀어봅시다 순열은 무엇일까요? 재귀를 이용하여 순열을 뽑기 전에 순열은 어떤 모양을 가지고 있는지 알아야 함으로 어떻게 생겼는지 먼저 알아봅시다. 순열은 Permutation 으로 nPr n개의 나열된 숫자에서 r개를 뽑는 것을 말합니다. 예를 들어 1, 2, 3, 4 의 숫자에서 2개의 숫자를 뽑는다면 경우는 위와 같이 같은 숫자를 가진 집합이 존재하면서 뽑히게 됩니다. 1 2와 2 1이 같은 경우로 치지 않고 뽑히는 경우 달라진다면 순열로 뽑는것이 옳고 1 2와 2 1이 같은 것이라면 조합으로 뽑아야 시간을 줄일 수 있겠죠? 조합은 위에 말한것처럼 순열의 반의 가짓수를 뽑는다고 생각하시면 좀 더 이해하기 쉬울 것 같습니다. ㅇ 조합에 대한 이야기는 다음 블로그 글을 참조하시면 됩니다. https://www.ac.. 2019. 8. 20. 백준 1941 소문난 칠공주 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 www.acmicpc.net 처음에 문제에서 잘못 이해를 했습니다. 파란색으로된 박스랑 초록된 박스를 보면 처음에는 Y를 중심으로 가로세로만 되는줄 알았는데 각각.. 2019. 7. 28. 백준 1182 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분 수열 이문제는 1개부터 N개까지 모든 경우를 뽑아내서 더해서 합이 S와 같은 갯수가 몇개 인지 세면되는데 비트로 생각하면 이렇게 뽑히면 되는겁니다. 이렇게 해서 1인부분의 합이 S가 되는 것을 세면 되는 문제로 엄청 쉬워집니다. 무튼 오늘은 아래 소스가 로또 문제랑 비슷하니 로또 문제도 풀어보시고 이문제도 풀어보시면 좋을것 같습니다. 1 2 3 4 5 6 .. 2019. 7. 24. 이전 1 ··· 3 4 5 6 7 8 9 다음 728x90 반응형
