티스토리 뷰
목차
삼성 대학생 프로그래밍 대회(SCPC) 2016 1차 예선에서 제가 푼 방법들입니다.
고수분들의 구현보다 많이 부족하지만 열심히 정리했습니다!
문제1. 3N+1
문제 요약
짝수는 절반으로 나누고 홀수는 3배하고 1을 더하는 규칙을 K번 적용해서 1을 만들 수 있는 수들 중에서 가장 큰 수와 가장 작은 수를 구하는 문제입니다.
풀이
아래 그림1처럼 숫자 1에서 시작해서 규칙을 역으로 K번 적용해서 만들 수 있는 수를 모두 구하고 그 중 가장 큰 수와 가장 작은 수를 선택했습니다.
구현
재귀 함수로 위 과정을 구현했습니다. 코드는 주석으로 설명했습니다. 주의할 점 : 문제에서 1을 두 배로 만드는 것을 최대 63회해서 
까지 값이 커질 수 있지만 long long의 표현 범위 최댓값은 
이기 때문에 unsigned long long 자료형을 사용해야 합니다.
문제2. 징검다리
문제 요약
징검 다리를 건너는데 1~K 거리 만큼 점프할 수 있습니다. 현재 위치한 징검다리에 a거리 만큼 점프해서 들어왔으면 다음에 점프할 때 a거리로 점프하면 안됩니다. 이 때 개울을 건너는 방법의 수를 구하는 문제입니다.
풀이
N이 매우 큰데 경우의 수를 구해야해서 dp문제라고 생각했습니다. dp[i][j] : i번째 징검다리로 j 거리 점프에서 진입 했을 때 개울을 건너는 방법의 수로 정의하고 다음과 같이 점화식을 세웠습니다.
를 빼는 이유는 현재 징검다리에 j 거리 만큼 점프해서 진입했기 때문에 문제의 조건에 따라 다음에 j 거리 만큼 점프하면 안되서 그 경우의 수를 빼준 것입니다.
주의할 점) 이 점화식 그대로 반복문을 작성하면 만점을 받지 못합니다. 그대로 반복문으로 구현하면 아래와 같은 3중 for문이 작성되는데
첫번째 for문 : 50000번 반복 (징검 다리 수 N : 50000)
두번째 for문 : 100번 반복 (점프거리 K : 100)
세번째 for문 : 100번 반복 (시그마 계산)연산횟수가 50000*100*100회로 너무 많기 때문입니다.
여기서 시그마 계산은 각 (i, j) 에 대해 처음 한 번만 하도록 하고 다음 부터는 이용하는 방식으로 고쳐서 2중 for문으로 줄일 수 있습니다.
구현
위 점화식을 그대로 반복문으로 구현하되 시그마는 한 번만 계산하도록 했습니다. 코드는 주석으로 설명했습니다.
코드에서 주의할 점은 숫자가 엄청나게 커져서 MOD(1000000009)로 계속 나머지 연산을 하게 하기 때문에 점화식에서 합(
)이 dp[i+j][j] 보다 작은 경우가 발생하여 값이 음수가 될 수도 있습니다. 따라서 dp[i][j] = (sum+MOD-dp[i+j][j])%MOD; 와 같이 연산하도록 합니다.
문제3. 바이러스
문제 요약
문제의 설명이 복잡한데 간단하게 정리하면 주어진 그래프에서 모든 정점이 차수 
가 조건 
, ( 
는 정점의 개수 )을 만족하기 위해서 최소 몇 개의 정점을 없애야 하는가 입니다.
풀이
N이 100이기 때문에 모든 경우의 수를 시도하는 단순 백트래킹으로 구현할 수 없습니다. 따라서 그리디 방식으로 접근했습니다.
그리디(Greedy) 방식이란 욕심쟁이처럼 지금 상황에서 제일 좋은 것만을 선택하는 것입니다. 다익스트라 최단경로 알고리즘에서 대표적으로 그리디 방식이 사용됩니다. 그러나 대부분의 상황에서 그리디 방식은 눈앞의 이득에 눈이 멀어 미래에 얻게 되는 전체 이득이 최댓값을 갖지 못합니다. 당장 행복하기 위해 매일 사탕을 10개씩 먹는 어린이가 이가 썩어 결국 치과에 가서 불행해지는 상황을 예로 들 수 있습니다.
그리디 방식으로 풀기 위해 주어진 상황에서 할 수 있는 최선의 행동을 아래처럼 정했습니다.
- 차수가 K 미만인 정점을 지운다.
- 차수가 |V|-L 이상인 정점을 지운다.
- 지울 대상이 여러 개이면 번호가 작은 것을 먼저 지운다.
이 행동을 반복하면 놀랍게도 정답을 구할 수 있습니다. 이 그리디 방법의 정당성을 증명하기 위해 이 방법이 눈앞의 이득에 눈이 멀어 미래에 얻게 되는 전체 이득을 놓치지 않는다는 것을 보여야합니다. 즉 이 행동이 미래에 손해를 가져오지 않는다는 것을 보여야합니다.
1번 : 정점을 지우는 행동만 할 수 있기 떄문에 미래에 차수가 늘지 않습니다. 따라서 현재 지워야할 정점은 순서에 상관없이 어짜피 나중에 지워야합니다. 그래서 지금 지워도 미래에 손해보지 않습니다.
2번, 3번 : 차수가 |V|-L 이상인 정점의 경우 연결된 다른 한 정점이 지워져서 차수가 1 낮아져도 전체 정점 수도 1감소해서 기준도 낮아지기 때문에 지워야 할 정점은 지우는 순서에 상관없이 무조건 지워야합니다. 따라서 지금 지워도 미래에 손해보지 않습니다.
구현
위 그리디 규칙을 그대로 코드로 옮겼습니다. 코드는 주석으로 설명했습니다.
문제4. 대피소
문제 요약
주어진 그래프에서 각 정점에서 가장 가까운 대피소와의 거리와 번호를 구하는 문제입니다.
풀이
정점 10만 개 모두에 대해서 가장 가까운 대피소와의 거리와 번호를 구해야하기 때문에 각 정점을 출발점으로 두고 다익스트라 최단거리 알고리즘을 10만 번 돌리면 답을 구할 수 있습니다. 그러나 이렇게 하면 시간초과가 발생해서 만점을 받지 못합니다.
놀랍게도 다익스트라 알고리즘을 딱 한번 만 돌리고도 정점 10만 개 모두에 대해서 가장 가까운 대피소와의 거리와 번호를 구할 수 있습니다. 방법은 출발 점을 여러 개(모든 대피소)로 설정하고 다익스트라 알고리즘을 수행하는 것입니다.
이 문제는 알고리즘 문제 해결전략 책 2권 935p 소방차 문제와 동일한 문제입니다. 잘 이해가 안되면 책을 참고하세요.
구현
출발 점을 여러 개로 두고 다익스트라 알고리즘을 수행하도록 코드를 작성했습니다. 코드는 주석으로 설명했습니다.
문제5. 구두제작
문제 요약
장인들이 구두를 주어진 조건하에 모두 만들 수 있는지 여부를 판별하는 문제입니다.
각 구두 마다 의뢰 기간(
)과 제작하는데 걸리는 시간(
)이 주어지고 장인은 의뢰 기간 안에만 해당 구두에 대한 생산 작업을 할 수 있으며 제작 시간 이상만큼 작업해야 구두가 완성됩니다.
또 장인의 근무 시간(
)이 주어지는데 근무 시간 동안만 구두를 만들 수 있으며 한 구두는 한 시간 동안 한 명의 장인만 작업할 수 있습니다.
풀이
여러 조건을 만족하면서 장인을 특정 시간에 구두를 작업하도록 매칭시켜야 하기 때문에 매칭 문제(네트워크 플로우 문제)풀이법으로 접근했습니다. 아래 그림2과 같이 플로우 네트워크를 구성하고 최대 유량 알고리즘을 수행한 뒤 최대 유량이 구두 제작 시간의 합과 같으면 장인들이 구두를 모두 만드는게 가능하다고 판단했습니다.
(그림2 입력 요약)
문제의 첫번 째 입력 예시를 플로우 네트워크로 구성한 것입니다.
구두 수 N : 3, 장인 수 K : 2
구두1 : 의뢰기간 [0, 4], 제작 시간 3
구두2 : 의뢰기간 [1, 3], 제작 시간 2
구두3 : 의뢰기간 [2, 7], 제작 시간 4
장인1 : 근무시간 [0, 7]
장인2 : 근무시간 [2, 4]
구현
위 그림대로 플로우 네트워크를 구성한 뒤 dfs를 이용해서 증가경로를 하나 씩 찾아 최대 유량을 구하는 방법으로 구현했습니다. 코드는 주석으로 설명했습니다.
- Total
- Today
- Yesterday