조합
-
백준 6591번 이항 쇼다운 :: 마이구미알고리즘 풀이/수학 2017. 9. 30. 23:50
이 글은 백준 알고리즘 문제 6591번 "이항 쇼다운" 을 풀이한다.조합에 관련된 시리즈 문제 중 하나이다.문제는 쉬워보이나 굉장히 낮은 정답 비율을 통해 만만치 않다는 것을 알 수 있다.6591번 - https://www.acmicpc.net/problem/6591 n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까? 문제의 설명에서 조합의 정의에 대해 그대로 명시했기 때문에, 조합 문제인 것을 알 수 있다.다른 관련 문제들은 단순한 접근 또는 동적계획법을 통해 해결할 수 있다.하지만 이 문제는 다르게 접근해야한다. 우리는 실제로 수학 문제를 풀 때, 1번을 이용해서 조합 문제를 해결한다.다음과 같이 풀 수 있다. 10C4 => (10*9*8*7) / (4*3*2*1)10C3 =>..
-
백준 14717번 앉았다 :: 마이구미알고리즘 풀이/수학 2017. 9. 25. 19:39
이 글은 백준 알고리즘 문제 14717번 "앉았다" 를 풀이한다.수학 과정 중 "조합" 을 활용하여 문제를 해결할 수 있다.최근 충남대에서 열린 "생각하는 프로그래밍 대회" 에 출제되었다.문제 14717번 - https://www.acmicpc.net/problem/14717 섰다는 화투를 이용하여 20장의 카드를 가지고 2명 이상이 경기를 하는 게임이다.이러한 섰다의 규칙을 단순화한 게임이 바로 '앉았다'이다.앉았다의 규칙은 1, 2, 3, ... , 9, 10이 쓰인 카드가 각 2장씩 주어지며 총 20장의 카드가 사용되며, 2명이 참가한다.다음은 앉았다의 경기 방법이다.두 명의 참가자는 순서대로 20장의 카드 중 무작위로 2장의 카드를 가져온다.상대방이 이미 가지고 간 카드를 중복해서 가져올 수는 없..
-
백준 1010번 다리 놓기 [고등수학 조합] :: 마이구미알고리즘 풀이/수학 2016. 7. 27. 17:47
이번 글은 백준 알고리즘 사이트 1010번 다리놓기에 대해 알아볼 것이다.재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다...