언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 T(1≤T≤20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
출력
각 테스트 케이스에 대해서 진영 주식회사가가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.
길이가 N인 수열이 주어졋을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 어떤 인접한 원소끼리를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때, 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
출력
수를 적절히 묶어 그 합이 최대값을 출력한다. 정답은 항상 231보다 작다.
예제 입력
4
-1
2
1
3
예제 출력
6
1. 접근
그리디 알고리즘. 여러 수들을 묶거나 더해서 가장 큰 수를 만들려면 가장 큰 두 수(양수) 나 가장 작은 수 (음수)들을 묶어야 한다.
2. 풀이
0 < a < b < c < d 인 수 네 개를 규칙에 따라 가장 큰 합을 만들려면 어떻게 해야 할까?
1) a * b + c * d
2) a * c + b * d
3) a * d + b * c
직관적으로 1번이 가장 큰걸 알고 있다.
1번과 2번을 빼면 a * (b - c) > d * (b - c) 이므로 1번이 더 크다.
1번과 3번을 빼면 a * (b - d) > c * (b - d) 이므로 1번이 더 크다.
음수에 양수를 곱해봤자 전체 합은 작아만지므로 음수는 가능한 음수와만 곱해야함이 자명하다.
따라서 음수와 양수를 따로 생각해서 가장 큰 수 두 개씩 묶어나가면 되겠다.
다만 1과 0은 예외적인 수인데, 0은 음수를 묶어나가고 남은 짜투리에 곱해서 0으로 만드는데 사용하고,
방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것(d[B]=10)으로 선택된다. B를 방문하여 S에 추가하고 Q에서 제거한다.
B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. d[E] 값이 무한에서 d[B]+(B와 E 사이의 값 = 20) = 30 으로 업데이트된다.
4. 세 번째 루프 : 더 작은 d[x]를 발견한다면?
Q의 원소 중에서 제일 낮은 d[N] 값을 가지고 있기 때문에 방문되는 노드는 D이다.
D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트해야 하는데, d[C]의 값이 A를 방문할 때 이미 계산되어 30으로 정해져 있었다. 하지만, D를 방문하여 C와의 거리를 확인해 보니 20으로더 짧은 최단 경로가 발견되었다! 따라서 d[C]의 값을 30에서 20으로 갱신한다.
d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 갱신한다.
5. Q가 공집합이 될 때 까지 루프를 반복한다.
S = {A, B, D, C, F, E} (방문한 순서대로 정렬)
d[A] = 0
d[B] = 10
d[C] = 20
d[D] = 15
d[E] = 30
d[F] = 25
Q = ∅
알고리즘의 흐름을 보면, 계속 가중치가 작은 간선을 골라 인접한 노드들의 데이터를 갱신해나가는 과정이란 것을 알 수 있다.
따라서 이 알고리즘은, 한 정점에서 다른 정점까지의 최단경로는, 중간에 방문하는 노드들도 최단경로로 방문해야 한다고 주장하는 것이다.
생각해보면 당연하다. A에서 C로 가는 최단경로가 A-(10)->B-(20)->C = 30라고 해보자.
만약 중간 노드인 B까지의 최단경로가 사실은 A-(3)->D-(4)->B = 7라고 한다면, 왜 A에서 C까지 가는데 D를 거치지 않겠는가?
당연히 거치는게 더 짧은 경로다. A-(3)->D-(4)->B->-(20)->C = 27
따라서 최단경로는 최단경로들로 이뤄져있다는 주장은 타당하다.
구현에서의 문제는 없을까? 초창기 이 알고리즘의 시간복잡도는 O(V^2) 였다고 한다.
문제는 Q집합 중에서 d[x]가 가장 작은 원소를 찾아 내는게 공짜가 아닌데 있었다.
지금은 최소-힙으로 Q집합을 유지하면서 O(E * logV)로 줄었다.
최소-힙에 정점은 최대 V^2번 들어가고, (힙의 삽입은 O(logN)) 간선은 E번 봐야 하므로 O(E * log(V^2)) = O(E * logV) 이다.
2. 풀이
최소 힙은 친절히도 <queue> 라이브러리에 priority_queue 를 이용해 쉽게 구현 가능하다.
우선순위 큐의 디폴트는 가장 큰 수를 top에 유지하므로 가중치를 음수화시켜 저장하거나, 큐의 선언에 greater를 쓰면 된다.
문제는 대놓고 다익스트라 알고리즘을 쓰라는 문제로, 시작점은 하나 주어지고 나머지 노드들 까지의 최단경로를 구해야 한다.
이중 벡터로 그래프를 구현하고, 집합 Q는 우선순위 큐로, d[x]는 거리를 저장하는 시퀀스를 선언해 구현해보자.
알고리즘의 구현에 대해 더 깊게 생각해보면, 꼭 INF의 초기화와 계산값을 비교하여 갱신하는 과정이 항상 필요할까?
BFS에서 편했던 점은 방문 노드를 표시하여, 다음 번엔 방문하지 않는 꼼수가 있었는데, 다익스트라는 불가능 할까?
실은 최소 힙을 쓰면서 해결된 의문점이다. 이미 INF에서 갱신된(방문한) 노드는 나중에 다시 경로값을 계산하지 않아도 된다.
무슨 소리냐, 앞에서 노드 C는 갱신하지 않았냐고 의문이 들겠지만,
이는 A의 이웃인 C를 큐에 넣으면서 갱신한데서 비롯되는 문제다. 따라서 큐에서 꺼낼 때만 d[x]를 갱신한다면,
최단경로는 최단경로의 합이란 논리하에 나중에 갱신된 값이 다시 갱신될 일은 없다.
4. 후기
최단경로 문제는 널리고 널렸다. 네이게이셔등의 현실과도 밀접한 알고리즘이기도 하다. 숙지하도록 하자.
1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
입력
입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n < 1000000)
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이 때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.
예제 입력
8
20
42
0
예제 출력
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
1. 접근
골드바흐의 추측이란 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표현할 수 있다는 추측이다.
또한 하나의 소수를 반복하여 사용하는 것을 허용한다.
예를 들어, 22는 3+19로, 또는 5+17로도 표현할 수 있다. 10^18 까지 골드바흐의 추측이 참임을 확인했다고 한다.
따라서 모든 소수들의 조합들을 확인하는 과정을 거치고자 한다.
2. 풀이
모든 소수를 빠르게 찾는 방법이 중요할 것이다.
여러 테스트케이스들이 소수인지 판별하는 유명한 소수판별 알고리즘은 에라토스테네스의 체라는 방법이다.
2부터 오름차순으로 모든 수(x)를 확인하는데, x가 체크되어 있지 않다면 소수고, 나머지 x의 배수는 모두 비소수로 체크한다.
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.
예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이 때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이 때 필요한 총 비용은 70+80+150=300 이다.
소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
입력
프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.
출력
프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되 버렸다. 결국 민식이는 모두 잠든 새벽 네시 반 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되있다.
빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
벽 : 절대 이동할 수 없다. (‘#’)
열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가게 되면 열쇠를 집는다. (소문자 a - f)
문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (대문자 a - f)
민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)
달이 차오르는 기회를 놓치지 않기 위해서, 되도록 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (N,M <= 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
예제 입력
1 7
f0.F..1
예제 출력
7
1. 접근
행렬을 순회하면서 최소 이동 횟수를 찾아야 하기 때문에 BFS를 채용.
2. 세부사항
열쇠를 습득했는지 여부에 따라 이동방식이 바뀌기 때문에 매번 방문시 열쇠 보유 상태를 갱신하고 기억해야한다.
따라서 삼차원 행렬을 BFS로 순회하면서 탐색한다. X, Y 축이 미로이고, Z축이 열쇠 보유 상태인 셈.
시작점이 주어지고 지도에서 1을 찾으면 종료되므로,
최악의 경우 모든 지점을 방문하는 N*M*(가능한 열쇠보유 상태의 경우)에 비례.
3. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<stdio.h>
#include<queue>
#include<algorithm>
usingnamespacestd;
char map[50][51];
int visit[50][50][1<<7]; //6자리 2진수를 만들기 위해 7번 시프트
int d[4][2] = { {-1, 0},{1, 0},{0, -1},{0, 1} };
int n, m, stx, sty;
int bfs() {
visit[stx][sty][0] =1;
queue<pair<pair<int, int>, int>> q;
q.push({ {stx, sty}, 0 });
while (!q.empty()) {
int qs = q.size();
while (qs--) {
int x = q.front().first.first;
int y = q.front().first.second;
int k = q.front().second;
q.pop();
if (map[x][y] =='1')
return visit[x][y][k] -1;
for (int i =0; i <4; ++i) {
int xx = x + d[i][0];
int yy = y + d[i][1];
if (xx <0|| yy <0|| xx >= n || yy >= m || map[xx][yy] =='#'|| visit[xx][yy][k] !=0)
continue;
if ('a'<= map[xx][yy] && map[xx][yy] <='f') {
int kk = k | (1<< (map[xx][yy] -'a')); // OR연산으로 열쇠보유상태를 갱신
if (visit[xx][yy][kk] ==0) {
visit[xx][yy][k] = visit[x][y][k] +1;
visit[xx][yy][kk] = visit[x][y][k] +1;
q.push({ {xx, yy}, kk });
}
}
elseif ('A'<= map[xx][yy] && map[xx][yy] <='F') {
int kk = k & (1<< (map[xx][yy] -'A')); // AND연산으로 해당 열쇠를 보유 중인지 확인
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
