이 문제는 알고리즘 공부하는 커리큘럼의 예제 문제같은 문제로, 딱 이거 쓰면 됩니다~ 이런 문제이죠.
방향 그래프에서, 시작점 하나의 점에서 모든 점으로 가는 최단경로를 모조리 구하는 그러한 문제입니다.
가중치가 10이하 자연수라는 제약 조건이 있고, 최대 2만개의 정점과 30만개의 간선이 있을 수 있습니다.
정점이 모두 양수이고, 한 점에서 시작하는 모든 최단경로를 구하는 문제는 다익스트라의 최단경로 알고리즘을 이용해서 풀이를 할 수 있습니다.
따라서 다익스트라 최단경로 알고리즘을 정확하게 구현하면 됩니다.
물론 실수가 있게 구현하면 시간초과가 나던지 오답이 나던지 할 수 있지요.
다익스트라 최단경로 알고리즘
다익스트라 알고리즘은 BFS와 유사한점이 꽤 있습니다.
코드 형태도 비슷한 점이 꽤 있지요.
간단하게 생각하면 BFS는 큐를 쓰고, 다익스트라는 우선순위 큐를 씁니다.
BFS는 모든 간선의 가중치가 같은 경우 사용할 수 있고, 다익스트라는 모든 간선의 가중치가 양수인 경우 사용할 수 있지요.
그리고 다익스트라는 조금 다른 점이 그리디한 알고리즘이라는 것입니다.
그리고 우선순위 큐에는 지금까지 방문한 모든 정점에 이웃한 정점의 정보가 들어있습니다.
이 우선순위 큐는 바로 다음 Step에 방문할수 있는 정점들이 모여잇는데, 그 중에서 Total 합쳐서 이동 거리가 가장 짧은 녀석 먼저 방문하는 방식입니다.
따라서 최소값이 우선순위가 높은 우선순위 큐를 만들어야 하지요.
그래서 큐에 있는 일부 값들은 세상의 빛을 보기 전에, 모든 연결된 정점을 다 방문하게 되어 영영 나오지 못하게 되는 경우도 있습니다. 그런녀석들은 최단 경로를 만드는데 도움이 되지 않는 녀석들이죠.
그래서 특정 정점을 가장 먼저 방문한 경우, 큐에 있는 녀석들은 그 이미 방문한 값 보다 더 짧은 거리에 방문할 일은 없습니다.
그래서 한번만 방문하면 되지요.
구현전략
여기서 Vertex수가 2만이므로, 인접 행렬을 구성할 수는 없습니다. 메모리가 너무 많이 들기 때문이지요.
인접 행렬은 노드수의 제곱만큼의 메모리를 사용하는데 그러면 메모리 초과가 납니다.
따라서 인접 리스트를 이용해서 구현합니다.
C++ STL에 있는 Pair를 사용할 것이고, Pair는 비교 연산이 first를 먼저 비교하고, first가 같은 경우 second의 대소 비교를 합니다.
C++ STL에 있는 Priority_queue는 기본적으로 MAX_HEAP 형태이므로, -를 넣어서 음수 값을 넣는 방식으로 최소값이 먼저 나오게 만들어서 구현하도록 합니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define INF 2000000000
#define MAXN 20004
vector<pii> edges[MAXN]; //dest, weight
bool visit[MAXN];
int dist[MAXN];
int main() {
int discovered = 0;
int V, E, K;
scanf("%d%d%d", &V, &E, &K);
for (int i = 0; i <= V; i++) {
dist[i] = INF;
}
for (int i = 0; i < E; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edges[u].push_back({ v, w });
}
priority_queue<pii> pq; // -dist, index
pq.push({ 0, K });
while (pq.size()) {
pii cur = pq.top(); pq.pop();
int distance = -cur.first;
int current = cur.second;
if (visit[current]) continue;
if (dist[current] == INF) discovered++;
visit[current] = true;
dist[current] = distance;
if (discovered == V) break;
for (pii nx : edges[current]) {
int next = nx.first;
int weight = nx.second;
pq.push({ -dist[current] - weight, next });
}
}
for (int i = 1; i <= V; i++) {
if (dist[i] == INF) {
puts("INF");
}
else {
printf("%d\n", dist[i]);
}
}
return 0;
}
백준 1014번 문제 컨닝에 대한 풀이 포스팅입니다. 사실 이 문제는 컨닝2 라는 문제도 있고, 컨닝2의 경우 컨닝1과 문제는 동일하나 N,M값이 다릅니다.
컨닝1은 N,M이 최대 10이고, 컨닝2는 N,M이 최대 80입니다.
일단 이 포스팅에서는 컨닝1을 풀이하기 위한 내용을 소개합니다.
사실 저는 이 문제에 대한 풀이 방법(카테고리 정도)를 알고 문제를 접근했습니다.
약간 스포일러를 하자면 다이나믹 프로그래밍으로 풀 수 있고 거기에 추가적인 기법이 하나 들어가게 됩니다.
다이나믹 프로그래밍 + 비트마스킹
일반적인 다이나믹 프로그래밍은 많이 들어보셨을 것이지만, 비트마스킹을 조합해서 쓰는 것은 잘 모르시는 분들도 있을 것입니다.
일단 문제를 분석해보면, 다이나믹 프로그래밍으로 풀만한 최적 부분구조(Optimal substructure)와 또 하나 특성이 있는데 그것이 성립하는 것 같습니다.
최적 부분구조라 함은, 부분문제의 최적값이 전체 문제의 최적값을 구하는데 사용이 된다는 것이고, 다른 하나의 특성은 부분문제의 풀이가 다른 나머지 문제를 풀 때 영향을 주지 않는다는 것이지요.
사실 영향을 주긴 하는데, 컨닝 문제 조건 상 앞에 줄에 사람을 어떻게 배치했느냐가 바로 뒷 줄에 사람을 배치하는 것에만 영향을 줍니다. 따라서 바로 앞줄에 사람을 어떻게 배치했는지를 저장을 할 필요가 있습니다.
그리고 앞에서 부터 사람을 채운다고 하면 앞에서 사람을 많이 채워놓아야지 뒤에서도 전체 사람 수를 채우는 데 도움이 되므로 최적 부분구조가 성립한다고 할 수 있겠지요.
그런데 사람을 배치하는 것은 한 줄(row)단위로 생각하면 사람이 있다, 없다의 2진수로 표현이 가능하게 됩니다.
컴퓨터에서는 정수를 2진수로 표현하기 때문에 이를 이용해서 앞 줄의 사람이 앉아있는 상태를 정수 하나로 쉽게 표현할 수 있을 것 같습니다.
이러한 방식을 bitmasking이라고 합니다.
점화식 정의
일단 사람을 앞에서 부터 채워야지, 이전에 앞에 채운 사람의 형태에 따라 뒤에서 valid한 사람 배치, invalid한 사람 배치를 알 수 있으므로 for-loop를 이용한 동적계획법으로 풀이를 하려고 설계를 해 보겠습니다.
그러면 점화식을 정의를 해 보아야 하는데 다음과 같습니다.
//(dp[i][j]//)
여기서 i는 i번째 열까지 채웠을때의 상태를 나타내고, j는 해당 i번째 열에 사람을 어떻게 배치했느냐를 나타냅니다.
즉 점화식의 정의는 i번째 열까지 사람을 다 채우고, i번째 열에는 사람을 j의 비트 모양으로 배치했을 때 가장 많이 배치할 수 있는 사람의 수라고 보시면 됩니다.
그러면 //(j//)모양으로 사람을 배치한다는 것은 무슨 말이 될까요?
간단하게 //(j=5//)라고 한다면 5는 2진수로 표현하면 101이 됩니다. 그러면 1이 있는 자리에는 사람이 있는 것이고, 0이 있는 자리에는 사람이 없는 것입니다. 이러한 방식으로 사람을 앉힌다는 것이지요.
구현전략
그러면 이러한 알고리즘으로 풀이 코드를 구현해보도록 하겠습니다.
그런데 보면 학생은 양 옆의 자리를 컨닝할 수 있으므로, 바로 인접하여 2명의 학생이 옆으로 배열되는 경우는 없습니다.
따라서 bit 들 중에서 인접한 2개의 bit가 같이 1로 되어있는 경우는 제거를 합니다. 그리고 이 bit 집합들은 자주 쓰일 것 같으므로 한번 만든 뒤 계속 사용하도록 하겠습니다.
그리고 비트마스킹의 장점 중 하나가, 모든 비트 경우를 확인하는 것은 단지 for-loop하나를 돌리면 다 확인이 가능합니다.
이러한 전략들을 적용하여 코드를 작성해보도록 하겠습니다.
풀이 코드
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
string field[15];
int dp[15][1025]; // dp[i][j]=> i번째 줄에 j비트 모양으로 학생을 배치할때, i번째까지 사람을 앉힐 수 있는 최대수
bool seat_check(string& seats, int bit) {
for (size_t i = 0; i < seats.length(); i++) {
if (seats[i] == 'x' && (bit & (1 << i))) return false;
}
return true;
}
bool adj_check(int bit, int width) {
for (int i = 0; i < width - 1; i++) {
int val = (3 << i);
if ((bit & val) == val) return false;
}
return true;
}
bool bits_check(int bit, int fbit, int width) {
//앞자리랑 뒷자리 관계가 제대로 성립하는지 확인
for (int i = 0; i < width; i++) {
if ((1 << i) & fbit) { //앞자리에 앉는 녀석이 있을 때
if (i > 0 && ((1 << (i - 1)) & bit)) return false; //왼쪽에 뒤에 앉는 경우
if ((1 << (i + 1) & bit)) return false; //오른쪽 뒤에 앉는 경우
}
}
return true;
}
void solve() {
int ans = 0;
memset(dp, 0, sizeof(dp));
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> field[i];
}
vector<pii> bits_set; //인접한 자리가 아닌 비트 마스크들을 미리 만들어놓음.
for (int bit = 0; bit < (1 << m); bit++) {
if (adj_check(bit, m)) {
int cnt = 0;
for (int i = 0; i < m; i++) {
if ((1 << i) & bit) cnt++;
}
bits_set.push_back(make_pair(bit, cnt));
}
}
for (int i = 1; i <= n; i++) {
//i 번째 줄을 채울 예정
for (pii bit : bits_set) {
if (!seat_check(field[i], bit.first)) continue; //부서진 자리에 앉으려고 하는 경우
for (pii fbit : bits_set) { //앞자리 앉는 녀석
if (bits_check(bit.first, fbit.first, m)) {
dp[i][bit.first] = max(dp[i][bit.first], dp[i - 1][fbit.first] + bit.second);
ans = max(ans, dp[i][bit.first]);
}
}
}
}
cout << ans << endl;
return;
}
int main() {
int tc; cin >> tc;
while (tc--) solve();
}
일단 Longest Increasing Subsequence가 무엇인지를 좀 알고 넘어가면 좋을 듯 합니다.
사실 부분수열이면 subsequence이지요. 그렇다면 수열은 sequence라고 보시면 됩니다.
subsequence라고 하는 녀석은 연속되지 않아도 됩니다. 이 부분이 간단하지만 핵심적인 내용인데, (반면 substring은 연속되어야 합니다.)
위 문제에서 예시를 보면, 10 20 30 50이 최장 증가수열입니다.
하지만 원본 배열에서는 20과 30 사이에 10이 들어있어서 20과 30은 연속되지 않습니다. 그래도 subsequence가 맞다는 것이지요.
그러면 길이가 N인 배열의 subsequence의 개수는 //(2^N//)개가 되겠네요. 각각의 원소가 부분 수열에 포함되거나, 그렇지 않거나 하니깐요.
그러므로 Brute force로 문제를 풀려고 한다면 당연히 시간 복잡도는 //(O(2^N)//)가 나오게 됩니다.
문제에서 주어진 //(N=1000//)이므로 완전탐색으로는 풀 수 없겠지요.
그렇다면 어떻게 풀 수 있을까요?
동적 계획법 풀이 (Dynamic Programming)
LIS는 유명한 동적계획법 문제 중 하나이기도 합니다. 1차원 다이나믹 프로그래밍으로 //(O(N^2)//)의 시간복잡도로 문제를 해결할 수 있습니다.
간단하게 점화식을 새운 뒤 부분 문제들을 풀면 됩니다.
헌데 문제 특성 상, 부분 문제인 이미 만든 Subsequence들을 저장을 해야 하는데, 리스트 형태로 되어 있으면 다루기가 힘들지요.
그래서 subsequence의 마지막 값만을 이용해서 점화식을 정합니다.
//(dp[i]//)는 //(i//)번째 원소를 부분 수열의 마지막으로 하는 수열 중 가장 긴 수열의 길이
로 정의합니다.
#include <bits/stdc++.h>
using namespace std;
int dp[1001]; //dp[i] -> i번째 값을 마지막으로 하는 subsequence중 가장 긴 녀석의 길이
int arr[1001];
int main() {
int n;
cin >> n;
for (int i=0; i< n; i++) {
cin >> arr[i];
dp[i] = 1; //길이가 1인 경우로 초기화
}
for (int i=0; i < n; i++) {
int& last_val = arr[i];
for (int j=0; j < i; j++) {
int& target_val = arr[j];
if (last_val > target_val) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int ans = 0;
for (int i=0; i<n; i++) {
ans = max(ans, dp[i]);
}
cout << ans << '\n';
return 0;
}
이전 문제와 달라진 점은 N의 크기 뿐입니다. N이 100만이 되었으니, 기존의 //(O(N^2)//)의 알고리즘으로는 시간 내에 풀이가 힘들게 되었습니다.
좀 더 효율적인 알고리즘이 있을까요?
NlgN 풀이 - 바이너리 서치
//(O(NlgN)//)의 시간복잡도를 갖는 LIS 풀이로 2가지가 있는 것으로 알고 있는데, 하나는 세그먼트 트리를 이용한 방법이고 다른 하나는 이번에 다루어볼 바이너리 서치를 활용한 방법입니다.
아이디어
일단 배열 A = {2, 5, 3}이라고 가정해봅시다.
그러면 LIS가 2개가 나옵니다.
{2, 5}와 {2, 3}이지요.
그러면 여기서 A배열 뒤에 7과 11이 추가된다고 생각해보겠습니다. 그러면 A = {2, 5, 3, 7, 11}이 됩니다.
그리고 이렇게 새로 추가된 7과 11 덕에 기존의 LIS도 더 길어지게 됩니다.
{2, 5} => {2, 5, 7, 11}
{2, 3} => {2, 3, 7, 11}
이러한 식으로 알고리즘이 전개됩니다. 여기에 A 배열 마지막에 8이 추가된다면 어떻게 될까요?
A = {2, 5, 3, 7, 11, 8}이 되는데, 요 8녀석이 기존에 알려진 LIS들 사이에 끼일 수 있을까요?
7과 11은 기존 LIS의 마지막 값 보다 명백히 큰 값이라서 그냥 뒤에다가 붙이면 된다는게 확실한데, 8은 마지막 값인 11보다 작습니다.
그러면 이 8이라는 녀석을 버려야할까요?
LIS에서 그리디한 성질
사실 이런 경우 11을 8로 바꾸는 경우가 무조건 더 좋습니다.
일단 수열이 여기서 끝난다고 하면, {2,3,7,11}이나 {2,3,7,8}이나 Increasing subsequence의 길이는 둘 다 같습니다.
이후 뒤에 어떤 수가 더 온다고 한 들, 8로 끝난 경우가 11로 끝난 경우보다 더 긴 수열을 만드는데 있어서 유리하거나 같습니다.
일단 당장 뒤에 오는 숫자의 범위를 3가지로 나누어 보겠습니다.
1) 11보다 큰 수가 오는경우,
2) 9이상 11이하의 수가 오는 경우
3) 8이하의 수가 오는 경우.
1번 11보다 큰 수가 오는 경우, 8로 끝난 수열이나 11로 끝난 수열이나 둘 다 취할 수 있습니다.
예를 들어 이후 13이 온 경우
{2,3,7,11,13}과 {2,3,7,8,13}이 가능한데, 둘 다 같은 길이에 마지막 수가 13으로 끝나는 수열이 됩니다.
2번 9이상 11이하의 수가 오는 경우 8로 끝난 수열은 길이가 1추가되는데, 11로 끝난 수열은 길이를 추가할 수가 없습니다. 또한 마지막 수가 11이하의 수 이므로 기존 11로 끝난 수 보다 무조건 유리합니다.
3번 8이하의 수의 경우는 둘 다 수열을 연장할 수 없으니 두개의 수열 모두 추가 수를 취할 수 없으니, 상관이 없지요.
따라서 같은 길이라면 마지막 수가 작을 수록, 이후에 더 긴 수열을 만들기 위해서는 더 유리하다고 볼 수 있습니다. 이러한 점에선 LIS가 그리디한 성질을 만족한다고 할 수 있겠습니다.
"수열의 마지막 수가 작을수록 더 긴 LIS를 만드는데 유리하다" 고 볼 수 있겠습니다.
이러한 점으로 다음과 같은 알고리즘을 한번 만들어 볼 수 있습니다.
알고리즘 설계
가장 긴 증가부분수열이 될 수 있는 녀석들을 Active list라고 부르도록 하겠습니다.
Increasing subsequence들 몇개들을 가지고 있으면서, longest가 될 수 있는 녀석을 알아내는 것인데,
위에서 알아낸 Greedy한 성질로 전체를 다 만들지 않고 추려낼 수가 있습니다.
같은 길이의 Increasing subsequence라면, 마지막 수가 가장 작은 녀석 하나만 알고 있어도 Longest IS를 구할 수 있다는 점입니다.
물론 i값을 0부터 N-1까지 증가시켜가면서 만드는 것이기 때문에 위치에 따른 dependency도 체크를 할 수있습니다.
알고리즘은 다음과 같습니다.
1. 만약 //(A[i]//)가 모든 Active list의 마지막 수 보다 작다면, 길이 1짜리 Active list를 하나 만든다.
2. 만약 //(A[i]//)가 모든 Active list의 마지막 수 보다 크다면, 가장 긴 Active list를 하나 복붙을 한 뒤, 마지막에 //(A[i]//)를 붙인다.
3. 만약 //(A[i]//)가 Active list 마지막 수들 중 가장 작은녀석 보다는 크고, 가장 큰 녀석 보다는 작다면, Active list 마지막 수 들 중에서 //(A[i]//)보다는 작은 녀석 중 가장 큰 리스트를 골라서, 그 리스트의 복사본 뒤에 //(A[i]//)를 붙인다.
끝까지 진행한 뒤, Active list중 가장 긴 녀석의 길이가 LIS의 길이가 됩니다.
위에 있는 수열로 위 알고리즘을 진행해보면, 아래와 같이 나옵니다. geeksforgeeks 블로그의 값을 그대로 긁어왔습니다.
위와 같이 진행이 됩니다.
그러면 이 Active List들을 잘 가지고 있어야 하는데 어떤식으로 구현을 하면 좋을까요?
구현 전략
NlgN 풀이를 하려는 이유는 배열의 길이가 꽤 길기 때문에 시간복잡도를 줄이기 위해서입니다.
그런데 저러한 Active List를 다 가지고 있게 되면, //(O(N^2)//)의 공간 복잡도를 갖게 되는데 NlgN으로 푸는 시간복잡도를 갖는 경우 대충 N이 10만 ~ 100만 정도 될 터인데, 이러한 N값의 N 제곱의 공간 복잡도는
필요 메모리 양이 꽤 많아서 보통 모두 할당할 수 없습니다.
그래서 저 Active list 전체를 다 저장하는 것 외의 방법을 찾아야 합니다.
그런데 Active list들의 데이터 특징을 좀 살펴보면, 같은 길이의 active list는 앞서 알게 된 그리디한 성질 때문에 하나만 가지고 있습니다. 그리고 모든 active list의 길이는 1,2,3,4 와 같은 식으로 같은 길이의 리스트는 하나만 나오고
점진적으로 1만큼 차이가 나는 것을 알 수 있습니다.
따라서 Active list의 마지막 숫자만 가지고 있어도 될 것 같은 느낌이 듭니다.
그렇게 저장할 경우 //(O(N)//)의 공간복잡도를 갖는 배열 하나만 가지고 있어도 됩니다.
따라서 Active list의 마지막 숫자의 값만 가지고 있는 배열을 따로 만들도록 하겠습니다.
이 배열을 list라는 벡터로 저장하고 구현을 한 소스코드 내용입니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 1000006
int arr[MAXN];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
}
vector<int> list;
for (int i = 0; i < n; i++) {
auto& a = arr[i];
if (list.size() == 0) list.push_back(a);
else if (a < list[0]) list[0] = a;
else if (a > list.back()) list.push_back(a);
else {
auto it = upper_bound(list.begin(), list.end(), a - 1);
*it = a;
}
}
printf("%u\n", list.size());
return 0;
}
이렇게해서 백준 12015번 문제인 가장 긴 증가하는 부분 수열 2 문제를 풀 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 50020
// disjoint set (DSU)
int parent[MAXN * 3];
int depth[MAXN * 3];
int root(int a) {
int p = a;
while (p != parent[p])
p = parent[p];
parent[a] = p;
return p;
}
bool same(int a, int b) {
return root(a) == root(b);
}
void unite(int a, int b) {
a = root(a);
b = root(b);
if (a == b) return;
if (depth[a] < depth[b]) {
parent[a] = b;
}
else {
parent[b] = a;
if (depth[a] == depth[b])
depth[b]++;
}
}
int main() {
int N, K;
scanf("%d%d", &N, &K);
//init
for (int i = 0; i <= N * 3 + 10; i++) {
parent[i] = i;
depth[i] = 0;
}
// i => i는 A이다.
// i + N => i는 B이다.
// i + N*2 => i는 C이다.
int ans = 0;
while (K--) {
int t, a, b;
scanf("%d%d%d", &t, &a, &b);
a--;
b--;
if (a < 0 || b < 0 || a >= N || b >= N) {
ans++;
continue;
}
if (t == 1) {
//a랑 b랑 같은 종류이다.
if (same(a, b + N) || same(b, a+N) || same(a+N, b+N+N) || same(b+N, a+N+N) ||
same(a, b + N + N) || same(b, a + N + N)) {
ans++;
}
else {
unite(a, b);
unite(a + N, b + N);
unite(a + N + N, b + N + N);
}
}
else {
//a는 b를 잡아먹는다.
if (same(a, b) || same(a + N, b + N) || same(a + N + N, b + N + N) ||
same(a, b + N + N) || same(a + N, b) || same(a + N + N, b + N)) {
ans++;
}
else {
unite(a, b + N);
unite(a + N, b + N + N);
unite(a + N + N, b);
}
}
}
printf("%d\n", ans);
return 0;
}
노란책의 솔루션 코드를 보면, 조건을 6개를 다 명시하지 않아도 정답이 된다고 하는데 왜 그런지는 아직 이해가 안된다;;
if (t == 1) {
//a랑 b랑 같은 종류이다.
//if (same(a, b + N) || same(b, a + N) || same(a + N, b + N + N) || same(b + N, a + N + N) || same(a, b + N + N) || same(b, a + N + N)) {
if (same(a, b+N) || same(a, b+N+N)) {
//다른걸로 분류하면 모순
ans++;
}
else {
unite(a, b);
unite(a + N, b + N);
unite(a + N + N, b + N + N);
}
}
else {
//a는 b를 잡아먹는다.
//if (same(a, b) || same(a + N, b + N) || same(a + N + N, b + N + N) || same(a, b + N + N) || same(a + N, b) || same(a + N + N, b + N)) {
if (same(a,b) || same(a, b+N+N)) {
ans++;
}
else {
unite(a, b + N);
unite(a + N, b + N + N);
unite(a + N + N, b);
}
}
요즘은 여러모로 경기가 좋지 않아서 왠만한 명문대 졸업자들도 취직을 하는게 하늘에 별따기 같습니다.
4차산업혁명 이야기를 막 하면서도, SW계열로 직업을 구하고자 하면, 이것 저것 능력을 많이 따져서 신입사원으로 지원하는 것임에도 불구하고 지원자에게 요구하는 능력 수준이 생각보다 꽤나 높습니다.
이름만 들으면 알만한 IT회사나 대기업들의 경우 신입사원 공채나 상시채용 프로세스에서 알고리즘 문제해결능력을 확인하는 과정들이 이제는 거의 필수처럼 되어가고 있는데, 왜 그런걸까요?
왜 IT SW계열 회사에서 알고리즘 능력을 강조할까?
Problem Solving(PS) vs Competitive Programming(CP)
일단 간단하게 용어를 조금 정하고 넘어가자면, 알고리즘 문제해결 분야를 보통 PS라고 줄여서 말합니다. Problem Solving의 약자로, 문제해결이라는 뜻이지요. 소프트웨어쪽에서 PS라는 단어를 쓰면 보통 이 용어를 뜻하는 것입니다.
비슷한 단어로 CP라는 단어가 있는데 이는 Competitive Programming의 약자로, 쉽게 말해서 코딩대회 같은 것을 생각하시면 됩니다. PS와 CP는 둘다 코딩할 수 있는 알고리즘 문제를 푼다는 공통점이 있는데, 조금 차이점이라고 하면 CP(Competitive Programming)의 경우 대회에서 경쟁하는 방식이므로 보통 수 시간(2~3시간)동안 문제를 빠르고 정확하게 풀면서 서로 점수와 푼 문제수로 경쟁한다고 한다면, PS(Problem Solving)는 문제를 푸는 것 그 자체에 포커스가 맞추어져 있습니다.
즉 대회에서 문제를 푸는게 아니라, 하나의 문제를 잡고 일주일이건 몇달이건 계속 풀고, 더 나은 해법을 찾고 하는 그런 행위들을 PS라고 하는 것이지요. PS를 평소에 즐겨해서 훈련이 되어 있다면 CP에도 도움이 될 것입니다. 다만 CP에서 좋은 성적을 얻기 위해서는 문제를 빨리 풀고 구현하는 능력도 훈련이 되어있어야겠지요?
IT회사에서 채용할때 PS능력을 얼마나 보는데?
일단, 국내 IT회사라고 하면 딱 떠오르는 네이버, 카카오, 라인플러스, NHN 등등이 있는데 이 회사들은 채용시 다 코딩테스트를 봅니다.
네이버의 경우는 공채를 자주 하지는 않지만, 최근에 한번 했엇지요? 그때도 서류(자기소개서) 제출 이후 온라인 코딩테스트를 통해서 지원자를 걸렀습니다.
라인플러스와 NHN도 신입사원 공채시 코딩테스트가 들어있었고, 일정 이상 점수를 받지 못한 사람들은 면접으로 가지 못했습니다.
카카오의 경우는 2017년 부터 매년 블라인드 코딩테스트라는 제도를 만들어서, 서류심사 없이 1차 2차 코딩테스트의 결과만으로 지원자들을 면접전형까지 보게 해주는 식으로 채용을 진행하였습니다. 그만큼 PS능력을 매우 중요시 한다는 것이지요. 수 많은 스펙보다 코딩 잘하는게 더 잘 증명되어있다 라고 생각하는 그런 부분이 보이는 현상이라고 생각합니다.
이 외에도 대부분의 IT회사들은 코딩테스트를 보거나, 상시채용을 실시하는 경우는 대규모로 같이 보는 것이 아니므로, 면접에서 이러한 알고리즘 문제해결능력을 알아볼 수 있는 질문들을 하곤 합니다.
이러다 보니, 코딩테스트 환경을 대행해주는 서비스 영역도 생기게 되었지요.
대기업의 경우에는 공채 프로세스에서 대부분 인적성이라고 하는 NCS와 비슷한 필기 문제를 통해서 사람들을 거르게 되는데, 삼성전자의 경우는 소프트웨어 직군의 엔지니어를 채용할 때에는 삼성계열사 인적성인 GSAT대신 SW역량테스트라는 알고리즘 문제를 냅니다.
그리고 채용 이후에도 신입사원 교육때 알고리즘과 같은 기초 부분은 중점적으로 다시 교육시킵니다.
그리고 세계적인 IT회사인 구글의 경우도 알고리즘 문제해결능력을 매우 Intensive하게 체크한다는 것도 널리 알려져 있습니다.
형태는 다들 다르긴 하지만, SW엔지니어를 채용할 때 알고리즘 문제해결 능력을 중요시 하다는 점은 자명해졌습니다.
그러면 PS를 잘하면 뭐가 좋을까요?
알고리즘 문제 해결(PS)능력이 뛰어나면 잘하는 것들
하지만 사실 알고리즘 문제 해결능력이 뛰어나면 부수적으로 딸려오는 능력들이 있습니다.
구현 능력
어떤 비즈니스 로직이나 알고리즘을 구현하는 능력이 꽤 많이 능숙해집니다. 빠르고 정확하게 구현할 수 있는 능력이 생기는데, 이는 SW엔지니어에게는 기초체력과 같은 능력이지요. 그리고 이런 능력은 은근히 기르기에 어렵고 시간도 많이 걸리는데, PS와 CP를 즐겨하는 사람들에게는 기본적으로 같이 있는 능력입니다.
시간복잡도와 공간복잡도에 대한 이해
물론 이 복잡도들은 학부 1~2학년때 배우는 내용이므로, 기초적인 내용이긴 하지만 실제로 구현을 하고 잘못 짜서 TLE(Time Limit Exceed) 판정을 보면서 문제를 풀어온 사람들에게는 매우 직관적으로 잘 이해되게 됩니다.
유명한 알고리즘과 자료구조들에 대한 이해
마찬가지로 자주쓰이는 balanced tree나 hash table과 같은 자료구조들, 그리고 유명한 알고리즘 dfs, bfs, dijkstra's shortest path 등에 대한 이해도가 남다릅니다. 직접 구현까지 해보고 시간복잡도 공간복잡도도 다 분석해본 사람들이니 말입니다.
남의 코드를 읽는 능력
PS를 하다보면, 남이 작성한 정답코드를 확인해 볼 일이 꽤 있는데, 이 과정에서 남이 작성한 코드를 이해하는 능력이 많이 길러지게 됩니다. 이 능력 역시 매우 기르기 어려운 능력인데, 자연스럽게 길러지는 것이지요.
알고리즘 문제를 잘 풀면 실무(개발)를 잘하나?
실무 != 알고리즘
사실 어플리케이션단의 개발을 하려면 알고리즘 문제를 매우 Intensive하게 잘 할 필요는 없습니다. 그리고 보통 알고리즘 문제해결능력이 좋으면 다 장땡이다 라는 생각을 비판하는 분들도, 알고리즘 잘 풀어도 일 잘하는거랑은 관계없다, 알고리즘 못해도 일 잘하는 사람 있다 라는 의견들을 많이들 내십니다.
물론 맞는말입니다. 요즘은 라이브러리나 오픈소스들이 잘 되어 있어서 그러한 Low-level 부분들을 하나하나 다 구현하지 않아도 잘 사용할 수 있습니다. //(O(NlgN)//)의 정렬을 구현하지 못해도, Java나 C등의 기본 라이브러리에 있는 sort라는 함수를 한번만 호출해주면 알아서 정렬을 해 주고, HashMap같은 것을 직접 구현하지 않아도, 라이브러리에 있는 녀석들을 사용하면 간단하게 개발을 할 수 있습니다.
그리고 요즘 핫한 딥 러닝이나 블록체인 개발/구현 등을 한다고 할 때, 이러한 알고리즘 문제 풀이 능력은 크게 도움이 안되는 것 처럼 보입니다. 알고리즘 문제 풀 시간에, 최신 딥 러닝 논문을 한 편 더 보는게 도움이 더 될 것이다, 이런 생각들이 들겠지요
알고리즘 < 실무
실무라고 하는 범위가 매우 다양할 수 있기 때문에, PS능력이 절대적으로 모든 실무능력을 다 커버해주진 않습니다. 하지만 실무를 하면서 맞닥드릴 수 있는 상황들을 쉽게 해쳐나갈 수 있는 능력을 줍니다.
PS에 능숙한 사람이라면 다음과 같은 상황은 생각보다 쉽게 해쳐나갈 수 있습니다.
1. 내가 원하는 기능을 정확히 수행하는 라이브러리나 오픈소스가 없을 경우 직접 구현하거나, 기존 것을 변경해서 사용해야하는 경우
2. 남이 작성한 코드를 빠르게 이해해야 하는 경우
3. 직접 구현할 때 실수 없이 빠르게 구현해야 하는 경우
특히나 어플리케이션 단이 아닌 임베디드와 같이 물리적 제약조건이 많은 환경이나, OS/커널과 같이 Low-level에서 구현해야 하는경우, 그리고 코어한 엔진부분 구현이라던지 하는 부분은 직접 작성해야하는 경우가 많습니다.
라이브러리에 잦은 의존을 하던 사람은 이러한 코어개발자가 될 기회를 PS를 즐겨하는 사람에게 뺏길 가능성이 높습니다.
언젠가는 주니어 SW엔지니어 중에서도 대부분이 어려워하는 분야도 해낼 수 있는 시니어 엔지니어로 거듭나야하는데, 이 과정에서 PS역량이 많은 도움이 된다고 볼 수 있습니다.
계속 변하는 기술트랜드
요즘은 기술을 배우는 시간보다 새로운 기술이 나타나는 시간이 더 빠르다는 이야기도 있습니다. PS능력은 새로운 기술이 나왔을 때 빠르게 배울 수 있는 기초체력과 같은 능력이 됩니다.
사실 요즘 핫한 딥 러닝이 유행을 탄 지도 5년 정도도 채 안되었다고 볼 수 있습니다. 만약에 곧 딥러닝의 인기가 시들해지고, 새로운 기술이 각광받는다면 또 그 기술을 배워야 하는데, 어차피 이렇게 계속 기술을 배워야 한다면, 몇년만에 유행을 타는 기술들이 아닌, 한번 제대로 배워놓으면 수십년은 가는 컴퓨터공학의 근간을 이루는 시스템, 네트워크, 자료구조, 알고리즘 등의 실력을 탄탄히 길러놓는 것이 현명한 방법 아닐까요?
끝으로 구사과님이 알고리즘 대회 열심히하는게 무용하다'라는 의견의 코드포스 블로그에 남긴 댓글 링크를 걸면서 이만 글을 줄이겠습니다.
위 사이트 자체가 삼성전자에서 SW역량이 뛰어난 사람들을 뽑기 위해 만든, 사이트이며 공부를 하라고 제공해주는 사이트입니다.
그리고 백준에서 SW역량테스트 기출문제라고 검색을 하시면 복원 문제들이 많이 나타납니다.
(시험을 칠 때에는 문제를 유출하지 말라고 아마 경고문이 있을 것인데, 알게 모르게 많이 유출이 되었죠 ㅠ)
그래서 기출문제를 보고 공부를 하라~ 라는 말을 하실줄 아셨겠지만, 저는 조금 다릅니다.
잠시 비유를 들어 보자면, 저희는 초/중/고등학교 교육을 받고 수능을 보게 됩니다.
그렇다고 초등학생이 처음 수능 기출문제를 풀어보면서 공부를 하지는 않지요. 고등학생이라면 기출문제를 열심히 돌릴때가 맞기는 하지만요.
이미 알고리즘 문제를 풀거나 코딩을 예전부터 즐겨 하시거나, 어렸을때 정보올림피아드를 해보셨거나, 코딩대회에서 상을 타시고 하시는 이런 이미 내공이 출중하신 분들은 이미 고등학생이나 대학생 이상의 수준이라서, 기출문제를 심심풀이로 몇개 풀어보시고 시험을 치시면 간단하게 합격 하실 수 있으실 겁니다.
하지만 아마 이 글을 보고 계신 분들은 다양한 실력의 스펙트럼을 가지고 계시겠지만, 방금 언급한 능력자분들일 가능성은 조금 낮다고 생각합니다. (팩트폭행 죄송합니다)
따라서 요점은, 자신의 수준에 맞는 난이도의 공부 자료로 공부를 해야지 의욕을 잃지 않으면서 꾸준히 공부하기에 좋을 것이라고 생각합니다.
저자의 추천 공부 커리큘럼
그래서 제가 추천하는 커리큘럼은 다음과 같습니다. 그리고 이 글에서는 2~3단계에 대하여 공부하는 분들에게 필요한 추천 리소스와 방법들을 제공합니다.
1-1. 프로그래밍 언어에 익숙해지는 단계
- 만약 본인이 이 단계에 해당한다면, 아마 컴퓨터공학과 1학년 학부생이거나, 코딩 공부를 막 시작한 비전공자에 해당할 것입니다. 이 단계에서 공부하는 부분은 안타깝게도 이 글에서는 설명하지 않습니다.
1-2. 기초적인 자료구조와 알고리즘을 배우는 단계
대학교 컴퓨터공학부 2학년쯤에 배우는 자료구조 및 알고리즘 수업에서 배우는 것들을 한번 배워보는 단계에 해당합니다. 기본적인 자료구조로 스택, 큐, 링크드 리스트 등은 기본적으로 알아야 하며, 시간 및 공간 복잡도 개념과 점근적 표기법에 대하여 알아야 합니다. 그리고 그래프 탐색 알고리즘인 DFS, BFS에 대하여 알아야 하고, 완전탐색 및 백트래킹에 대하여 알면 좋습니다.
또한 비트연산자와 컴퓨터에서 정수 및 실수를 어떻게 표현하는지, 등의 개념도 숙지하고 있으면 좋습니다.
라이브러리 - C++ STL(Standard Template Library) 중 vector, queue, sort, priority_queue 등
자료구조 - 우선순위 큐
알고리즘 - 이진 탐색(Binary search)
2-1단계 "초급 난이도에 해당하는 다양한 문제들을 풀어보는 단계" 공부법
우선은 2-1에 해당하는 "초급 난이도에 해당하는 다양한 문제들을 풀어보는 단계"를 진행하시기를 추천드립니다.
"다양한 문제들 + A형 문제와 출제 유형 등이 비슷한 문제들" 등을 풀면서 공부를 하면 됩니다.
출제 유형이 비슷한 문제들만 푸는 것이 아닌, 다른 다양한 문제들도 많이 풀으라고 권장을 드리는 이유는
크게 두가지가 있습니다.
1. 다른곳에서도 통하는 실력
- 다양한 문제를 풀이하면서 쌓은 실력은, 삼성전자 입사를 위한 SW역량테스트/상시테스트 뿐만 아니라 다른 회사를 입사하기 위한 알고리즘 테스트/코딩테스트 및 각종 알고리즘 대회 등에도 도움되는 역량입니다. 물론 원하는 회사에 입사하는 것도 중요하지만, 다른 회사로 가는 가능성도 열어두면 나쁠것은 없겠죠?
-> 특히나 삼성 SW역량테스트의 문제 유형은 고정된 것 같지만, 시간이 지날 수록 유형이 조금씩 변화하는 모습도 보이기도 합니다. 따라서 기출문제 풀이에만 안주하기 보다는 꾸준히 공부하는 것이 더 안정적입니다.
2. SW 문제풀이 실력의 안정성 향상
- 출제 유형에만 맞는 문제를 풀이하다 보면, 해당 유형에 맞지 않는 문제를 보았을 때 맞출 확률이 현저히 떨어지게 됩니다. 또한 풀줄 아는 것 만 풀다 보면 문제를 조금만 꼬아서 내도 크게 당황하게 되지요. 따라서 같은 A형 문제를 보더라도 언제는 맞추고 언제는 틀리는 실력을 갖기 보다는, 항상 문제를 풀어낼 수 있는 실력을 갖추는 것이 중요합니다. 이러한 안정적인 실력을 갖추기 위해서는 다양한 문제들을 풀어보는 것이 도움이 많이 됩니다.
또한 이러한 실력이 쌓이게 되면, 자신감도 같이 붙게 되기 때문에 시험장에서 긴장도 덜 하게 됩니다.
저는 이러한 문제들 중 일단은 "다양한 문제들"에 해당하는 문제 풀을 추천드리려고 합니다.
96년도부터 2018년도까지만 다 풀어도 23개년어치입니다. 매년 3~4문제 정도가 있으니, 대충 100문제가 안되는 수의 문제들입니다.
이제 정올 초등부 문제를 추천하는 이유들을 나열해보겠습니다.
난이도가 단계적이다
각각의 기출들은 3~4문제로 이루어져있는데 문제가 1,2,3,4 번이 있다면 난이도는 1 < 2 < 3 < 4 식이고, 4번 문제 쯤 되면, 솔직히 SW역량테스트보다 난이도가 어려운 경우도 있다고 생각합니다.
처음 풀다보면 1번 문제만 풀 수 있다가, 공부를 함에 따라서 2번도 풀었다 못풀었다 하기도 하고, 나중에는 1~2번 문제는 껌으로 풀고 3번문제를 풀었다 못풀었다 하고 하는 식으로 실력이 느는 것을 체감하기에도 쉽지요.
SW역량 테스트를 쉽게 통과하려면 3번문제까지는 쉽게 풀고 4번 문제는 가끔 풀 수 있는 실력정도는 되어야 한다는 개인적인 의견이 있습니다.
문제 출제 범위가 SW역량 테스트와 비슷하다.
정보올림피아드 초등부의 경우는 간단한 수학문제, 구현(시뮬레이션), 완전탐색(DFS, BFS), 간단한 DP 및 그리디 정도가 출제 범위입니다. 중고등부로 넘어가게되면 세그먼트 트리와 같은 고급 자료구조와, 유량 문제 등이 등장하게 되는데 이는 SW역량 테스트의 출제 범위와 한참 벗어나 있습니다. 절대 안나온다는 뜻이죠.
SW역량 테스트의 경우는 완전탐색과 구현(시뮬레이션) 문제에서 99% 나온다고 보실 수 있습니다. 출제 범위가 참 비슷하지요?
SW역량테스트에 비해 문제 푸는 피로도가 덜하다
A형에서는 조금 체감이 덜 될 수도 있는데, 정보올림피아드 문제들은 SW역량테스트에 비해서 사람을 귀찮게하는 요소들이 좀 덜한 편입니다. 문제 하나하나 풀 때 마다 체력 소모가 크다면, 계속해서 공부해야하는 입장에서 빨리 지치겠지요? 정보올림피아드 문제가 좀 더 가벼운 느낌으로 재미있게 풀면서 코딩 스킬 / 알고리즘 스킬 / 컴퓨팅 사고 능력을 기르기에 적합합니다.
공인된 문제 + 적절한 퀄리티 + 쉽게 구할 수 있는 풀이 + 공개된 TestCase
공인된 문제므로 일정 이상의 퀄리티는 나올것이며, 유명한 문제이니 만큼 풀이도 쉽게 구할 수 있는 것은 자명합니다.
그리고 정올 사이트 (http://www.jungol.co.kr/)에서 기출문제 탭에서 문제를 풀게 되면, 틀린 TestCase도 직접 눈으로 확인해볼 수 있습니다. 백준에서 공개되지 않는 TestCase를 보고 맞왜틀(맞은것 같은데 왜 틀리죠?) 맞왜틀 노래를 부르는 것 보단 훨씬 도움이 될만한 자료가 많다는 것을 알 수 있습니다.
정공법 공부에 가깝다
이 이야기는 무슨 이야기냐 하면, 사실 코딩 / 알고리즘 문제 풀이를 잘 하려면 문제를 많이 풀어봐야 합니다. 기출문제만 푸는 식으로 공부를 하면 조금 꼬아서 내는 구현형 문제가 나왔을때 당황을 하거나 하는 경우가 많죠. 즉 비슷한 난이도의 문제인데, 어떨때는 풀 수 있고 어떨때는 못 푸는 경우, 사실은 그 난이도의 문제를 정ㅋ벅ㅋ 한 것은 아니란 것이죠. 정보올림피아드 초등부 문제를 다 풀어보고 이해하고 내것으로 만들 정도의 공부량이면 SW역량 테스트는 정ㅋ벅ㅋ 가능할 것 이라는 개인적인 사견이 있습니다. 최소 이정도 난이도에 이정도 개수의 문제는 풀어봐야 단단한 실력을 갖는다 라는 생각이지요.
반드시 이해하고 넘어가세요
사실 23개년 문제 4문제씩은 많은 양이 아닙니다. 따라서 못푸는 문제의 풀이를 듣게 되면 열심히 이해해서 본인 것으로 만들어 주세요. 당연한 이야기 같기도 합니다. 코딩을 단순히 많이 한다고 느는 것이 아니라, 중고등학교때 수학문제를 풀듯이 하나하나 제대로 이해하고 넘어가고, 문제를 풀기 위해 사고하는 과정에서 많이 성장하는 것입니다.
2-2단계 "A형과 출제 범위, 난이도 및 유형이 비슷한 문제들을 풀어보는 단계" 공부법
2-1단계에서 초급문제들을 풀어가면서 어느정도 실력을 쌓았다면, 이제는 A형 유형과 더 비슷한 문제들을 풀어줍니다.
많이 풀 수록 좋기도 하겠지만, 2-1단계에서 탄탄한 실력을 쌓았다면 문제 하나하나 풀어보면서 A형 문제 스타일을 음미한다는 느낌으로 풀면서 즐겨주세요.
2-2단계에 해당하는 문제들이 처음에는 조금 낯설수는 있지만 몇개만 풀어봐도 금방 익숙해지고 풀만하다는 느낌이 든다면, 2-1단계에서 공부가 잘 된 것입니다.
관련 문제들을 계속해서 풀어봐도 막막하고, 풀이를 봐도 매우 이해하기 힘들다면 2-1단계로 다시 돌아가시는게 좋습니다.
2-2단계에서 풀만한 추천 문제들은 아래에 있습니다.
A형에서 주로 나오는 문제 유형은 대부분 모든 경우의 수를 다 찾아보는 완전탐색(Exhaustive Search 혹은 Brute-Force Algorithm이라고도 합니다)문제와 하나하나 그대로 따라해보는 시뮬레이션 문제, 그리고 고급 알고리즘 보다는 코딩 구현 능력을 필요로하는 구현형 문제들이 많이 나옵니다.
동적 계획법(Dynamic Programming)문제들은 거의 나오지 않고, 동적 계획법으로 풀 수 있는 문제가 나올 수는 있지만, 그 문제는 완전탐색으로도 풀 수 있는 문제일 것입니다.
