알고리즘 문풀을 잘하고 싶어졌다. 게임중독?인 나에게는 게임적 요소가 필요한데, solved.ac가 도움이 될 수 있을 거 같았다. 목표는 플레티넘이다.
알고리즘 문제를 풀다가 깨달을 부분들이 있다면 여기에 꾸준히 기록해 나아갈 예정이다. 나는 c++을 사용해 알고리즘 문제를 풀 것이다.
stoll vs atoi
문제를 풀다보면 문자열을 정수형으로 바꿔줘야할 경우가 생기는데, 이때 사용할 수 있다.
char* => int 의 역할을 하는 atoi(<cstdlib>), string => long long 역할을 하는 stoll(<cstring>)이 존재한다.
c++을 사용할땐 stoll을 사용할 수 있다.
문자열과 정수 처리하기
입력으로 [1,2,3,4,5]가 들어왔는데, 우리에게 필요한 건 정수 뿐이라면?
%c를 사용해서 받고 이를 변환하는 방법도 있겠지만 자릿수가 많아질 경우를
생각하면 번거롭다. 그러면 cin보다는 scanf를 사용하여 처리한다.
int num;
char tmp;
// [ 는 따로 처리
scanf("%d%c",&num,&tmp);이렇게 한다면 num만 따로 뽑아 관리할 수 있다.
scanf 사용 시 주의할 점은 띄어쓰기가 있냐 없냐에 따라 STDIN에 있는 띄어쓰기를 무시할 지 인식할 지 결정한다는 것!
최소거리 구하기
dfs + 흔적남기기
void dfs(int cur,vector<vector<pair<int,int>>>& graph,int distance){
if(cur == end_){
min_ = min(min_,distance);
}
for(auto e: graph[cur]){
if(visited[e.first]==0){
visited[e.first]=1;
dis[e.first]=distance+e.second;
dfs(e.first,graph,distance+e.second);
}
else if(distance+e.second < dis[e.first]){
dis[e.first]=distance+e.second;
dfs(e.first,graph,distance+e.second);
}
}
}처음 시도했던 최소거리 구하는 방식이다. dfs를 활용하고, 방문 시 만약 이미 방문헀다면 저장된 거리보다 적다면 다시 방문하는 방식이다.
하지만 이 방식으로 최단거리 구하는 문제를 풀게되면 시간 초과가 뜬다. dfs를 사용하기 때문에 모든 노드를 방문하는데, 그러면서도 갱신후보라면 또 검사를 하기 때문에 시간복잡도가 O(N^2)까지 가능한 형태이다.
다익스트라 알고리즘
가장 간단하게는 해결하기 위해 다익스트라 알고리즘을 활용한다.
vector<int> dist(n+1, 987654321);
dist[start] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
while(!pq.empty()){
auto [curDist, cur] = pq.top();
pq.pop();
if(curDist > dist[cur]) continue;
for(auto edge : graph[cur]){
int next = edge.first;
int weight = edge.second;
if(dist[cur] + weight < dist[next]){
dist[next] = dist[cur] + weight;
pq.push({dist[next], next});
}
}
}우선순위 큐를 사용하기 때문에 pop되는 노드는 무조건 최소 경로가 되어 다익스트라 알고리즘이 된다.
비트마스킹과 dp
이 문제는 해당 방법으로 풀 수없지만, 다른 문제에서는 응용할 수 있을거라 생각한다.
void dfs(int cur,vector<vector<pair<int,int>>>& graph,int distance,int masking){
if(dp[masking][cur] != -1 && distance < dp[masking][cur]) return;
dp[masking][cur] = distance;
if((1<<(n+1))-1 == masking){
min_ = min(min_,distance);
return;
}
for(auto e: graph[cur]){
if(masking & (1<<e.first)) continue;
else {
dfs(e.first,graph,distance+e.second, masking | (1<<e.first));
}
}
}시도한 방식이다. 실제로 돌리진 못했는데, dp배열의 크기가 너무 커서 오류가 발생했다.
비트마스킹을 통해 내가 여태 지나온 경로를 dp를 활용해 기록하기 때문에
dfs만 사용하는 것과는 다르게 모든 경로만 재탐색하는게 아니라 특정 경로에
대해서만 재탐색이 필요해 시간을 줄일 수 있다.
0-1 bfs
bfs에서 가중치가 0 또는 1만 존재할때(ex. 백준 13549) 사용할 수 있다. 가중치가 0이라 함은 사용하는데 무언가를 잴 필요가 없기 떄문에, 앞으로 넣어주는 개념이다.
deque를 활용하여 0인 경우는 front에 넣어주고, 1인 경우는 back에 넣어주는 방식이다.
while(!q.empty()){
int curN = q.front().first;
int cnt = q.front().second;
q.pop();
if(curN==k){
cout << cnt;
return 0;
}
int tmpN = curN;
while(tmpN*2<=100000 && visited[tmpN*2]==0){
if(tmpN*2 == k){
cout << cnt;
return 0;
}
q.push({tmpN*2,cnt});
visited[tmpN*2] = 1;
tmpN *=2;
}
if(curN-1 >=0 && visited[curN-1]==0){
q.push({curN-1,cnt+1});
visited[curN-1] = 1;
}
if(curN+1<=100000 &&visited[curN+1]==0){
q.push({curN+1,cnt+1});
visited[curN+1] = 1;
}
}이건 내 풀인데, 일반적인 bfs를 사용했다. 이 방법으로도 풀리긴 하지만 시간초과가 뜬다면 0-1 bfs를 시도해볼 수 있겠다.
조합
백준 15686번 문제였다.
n개중 k를 선택해야 하는데, 이게 변수여서 미리 for문을 작성할 수 없어서 이걸 분기처리할 수도 없고 어떡하지 하다가 함수로 처리할 수 있다는 것을 알았다.
void johab(int cnt,vector<int> visited,int idx){
if(cnt == m) findMin(visited);
else{
for(int i =idx;i<visited.size();i++){
if(visited[i]==0){
visited[i] = 1;
johab(cnt+1, visited,i);
visited[i] = 0;
}
}
}
}함수를 새로 만들고 선택한 k개를 visited 배열로 관리한다. k개에 만족하면 알고리즘을 유발하는 함수로 보낸다.
주의할 점은 for문의 출발이 idx가 아니라 0이면 중복순열이 되므로 idx로 설정해줘야 한다는 것이다.
행렬의 분할정복
행렬의 제곱을 분할하는 백준 10830번. 행렬제곱을 구현했지만 분할정복을 구현하는데 어려움을 겪었다.
짝수라면 a^4 = a^2 * a^2, 홀수라면 a^5 = a^2 * a^2 * a로 하면 되는건 알겠는데 행렬곱셈에 이를 어떻게 적용해야되는지 모르겠었다.
행렬로 넘기는 건 배열(==주소)이기 때문에 반환값으로 배열을 줄 필요없이
인자로 넘긴 배열을 조작해 이를 결과값으로 사용할 수 있었다.
while(b>0){
if(b%2 == 0){
matrixMulti(arr,arr);
}
else{
matrixMulti(ans, arr);
matrixMulti(arr, arr);
}
b/=2;
}분할정복은 다음과 같이 짤 수 있었다. 홀수 인경우 배열을 곱해주고 배열끼리 곱, 짝수인 경우 배열끼리 곱.
b가 1인 경우는 항상 존재하고, 마지막에 ans에 arr를 곱해주기 때문에 ans는 정답이다.
트리의 지름 찾기
체화된 방법은 dfs 2번 사용하기. 임의의 한 점에서 dfs를 돌려 지름의 한점을 찾고, 거기서 dfs를 돌려 지름을 구하기.
더 좋은 풀이도 있나 남의 풀이들을 살펴봤는데, dfs를 1번 이용하는 풀이가 있었다.
// 현재노드 v, 부모노드 p. 부모노드의 반대방향으로 뻗어 트리까지 가장 긴 경로를 탐색 후 반환
int getlf(int v, int p) {
if(dp[v] != -1) return dp[v];
int ret = 0;
for(auto [e, w] : adj[v]) {
if(e == p) continue;
ret = max(ret, getlf(e, v) + w);
}
return dp[v] = ret;
}
// 모든 점을 순회하며 트리로 dfs를 뻗어 가장 긴 경로 a, b를 저장해 합을 비교한다.
int dfs(int v) {
vis[v] = 1;
int a = 0, b = 0;
int ret = 0;
for(auto [e, w] : adj[v]) {
if(vis[e]) continue;
b = max(b, getlf(e, v) + w);
if(b > a) swap(a, b);
ret = max(ret, dfs(e));
}
return max(ret, a + b);
}이 방식을 사용하면 한 번의 dfs호출만으로 답을 찾을 수 있었다. 혹시 dfs 2번을 사용했을때 시간초과가 뜬다면 이 방법을 고려해볼 수 있겠다.
수학문제
백준 11444번. 처음으로 골드상위권 수학문제를 접했다. 분할정복인 것은 눈치챘지만 도저히 모르겠었지만, 어려운 문제를 접할때는 점화식을 찾아 관계성을 찾으면 된단다.
분할정복이라는 것 특성상 2배의 관계를 가질거라 예상하고, 2n과 n의 관계를 찾기위해 점화식을 세워 둘의 관계를 정리했다. 2n은 짝수일때만 가능하기때문에 2n+1도 찾아줘야 했다.
정작 제출과정에서 애먹었던 부분은 long long처리.. 입력부터 반환값, 인자
전부 자료형 설정을 잘하자..
스도쿠
최근에 만난 사람 중에 스도쿠를 푼다는 사람이 있었어서 눈이 간 문제였다.
처음에는 브루트포스인 줄 알았으나, 스도쿠에 무지해서 생긴 일.. 당연히 현재상태에서 가능한 가장 작은 수를 넣는다고 스도쿠를 채울 수 없다.
백트래킹을 통해 구현해야 했다. 아직 백트래킹, 재귀 심화문제가 나오면
헤매는 느낌이다.
bool stockWorld(int y,int x, int weight){
if(y==9) return true;
if(arr[y][x]!=0){
int v = x == 8 ? 0 : x+1;
bool b = stockWorld(y+(x+2)/10,v,weight);
return b;
}
bool b = false;
while(1){
vector<int> visited(10,0);
int flag = findStock(y,x,visited,weight);
if(flag == -1) return false;
if(flag!=-1){
int v = x == 8 ? 0 : x+1;
b = stockWorld(y+(x+2)/10,v,weight-flag);
}
if(b) break;
arr[y][x] = 0;
weight++;
}
return true;
}내 로직의 핵심함수였다. 가장 작은 수부터 채울 수 있도록 (0,0)에서부터 오른쪽 아래로 향하게 쌓았고, y==9에서 끝나게 했다.
실패할때마다 findStock()을 재실행하는게 아니라 이전세상으로 돌아가 그 세상에서 findStock()을 다시 돌리게 하는 게 관건이였다.
이제 난 스도쿠를 0.6초만에 푼다!
위상정렬
백준 2252번. 순서가 배정되어서 이를 어떻게 처리하지 하면서 바이너리 트리를 만들고 이를 관리하면 어떨까? 싶었지만 트리에 없는 관계가 주어지면 트리가 여러 개가 되면서 너무 복잡해졌다.
disjoint set을 사용하는 건 어떨까 싶었지만 집합 내 우선순위를 배정할 방법을 생각하지 못했다.
해결책은 위상정렬이였다. 말은 들어봤지만 실제로 구현해본적은 없어 겁
먹었지만, 원리는 간단했다.
그래프를 입력받고, 입력받으면서 진입차수를 센다. 진입차수가 0인 것이 우선순위가 낮은, 시작점이 된다(DAG 방향성x 비순환 그래프).
진입차수가 0인 것은 큐에 넣고 시작한다. deque를 하며 연결된 간선을 지우고 진입차수를 감소시킨다. deque된 노드는 그 다음 우선순위가 낮은 노드이다. 이 과정에서 진입차수가 0이되는 노드들은 새롭게 큐에 추가되고 이 과정을 반복한다.
최소 스패닝 트리
모든 노드를 잇는데 최소환의 가중치를 사용하여 건물을 잇는 방법.
크루스칼 알고리즘, 분리집합을 사용한다.
노드 N개를 잇기 위해 필요한 간선은 N-1개임을 이용한다.
가중치를 기준으로 오름차순 정렬을 하여 뽑기 시작한다. 뽑을 때마다 집합으로 묶어주고, 새로 뽑은 간선의 양 끝(노드)이 이미 집합이라면 그 간선은 무시하는 방법으로 설계한다.
외판원 순회
비트마스킹 + DP를 사용한 문제. 다만 시간초과가 계속 떠서 힘들었다.
//처음에 짠 코드
void dfs(int N, const vector<vector<int>> &cost_graph, int cur_node,int answer,int start,int state,vector<vector<int>> &dp){
if(dp[state][cur_node]!=-1 && (dp[state][cur_node]<answer)){
return;
}
dp[state][cur_node]=answer;
if(state==(1<<N)-1){
min_=min(min_,dp[state][cur_node]+cost_graph[cur_node][start]);
}
for(int i =0;i<N;i++){
if(state&(1<<i) || cost_graph[cur_node][i]==0) continue;
dfs(N,cost_graph,i,cost_graph[cur_node][i]+answer,start,state|(1<<i),dp);
}
}순회하는 최소경로는 결국 똑같다
최소경로가 1->2->3->4->5->1라고 한다면, 1에서 출발하든 5에서 출발하든 결국 최소경로는 같다
가지치기
전역변수를 설정하고, 최종상태에 이르면 전역변수를 비교하는 쪽으로 짰는데, 아마 불필요한 재귀가 계속 발생했던 것 같다.
전역변수가 아니라 반환값을 통해 값을 관리하도록 수정했다.
// 수정
int dfs(int N, const vector<vector<int>> &cost_graph, int cur_node,int start,int state,vector<vector<int>> &dp){
if(state==(1<<N)-1){
if(cost_graph[cur_node][start]==0) return INF;
else return cost_graph[cur_node][start];
}
if(dp[state][cur_node]!=-1) return dp[state][cur_node];
dp[state][cur_node] = INF;
for(int i =0;i<N;i++){
if(cost_graph[cur_node][i]==0) continue;
if(state&(1<<i)) continue;
dp[state][cur_node] = min(dp[state][cur_node],cost_graph[cur_node][i] + dfs(N,cost_graph,i,start,state|(1<<i),dp));
}
return dp[state][cur_node];
}쓰리포인터
세용액문제이다. 두 용액 문제를 접근할 때는 투포인터로 풀었고, 이런 류의 문제는 이분탐색도 가능하다는 것을 알았었다.
하지만 세 용액은 조금 당황해서 어떻게 할 지 모르겠었지만, 투 포인터를 고르고 랜덤으로(순회)골라 최소값을 찾으면 되지 않을까? 했지만 계속 오류가 떴다.
// 틀린 접근
sort(v.begin(), v.end());
long long start = 0;
long long end = v.size() - 1;
ans ans = {-1,-1,-1,10000000000};
while (start < end) {
long long sum = v[start] + v[end];
for (long long i =0;i<n;i++) {
if (i==start || i==end) continue;
long long tmpSum = sum + v[i];
if (abs(tmpSum)<ans.sum) {
...순회를 내부에서 하는게 아니라, 먼저 하나를 정하고, 그 다음 수를 start로 지정하여 코드를 짜니 해결할 수 있었다.
for (long long i = 0; i < n-2; i++) {
long long start = i+1;
long long end = v.size() - 1;
while (start < end) {
...LCS
가장 긴 부분수열을 찾는문제. 처음 생각했던 방법은 2차원 dp를 만들어놓고, 일치하는 부분이 생기면 i-1,j-1크기의 배열의 가장 큰 값에 +1을 하는 방법이였는데 이 방법은 어떻게해도 n^3이 되었고, 틀린코드임에도 구현해보고 싶어서 구현하는데 시간이 걸렸다. 그냥 존재한다면 [i-1][j-1]+1을 하고, 아닌 경우는 위, 왼쪽에서 큰 값을 가져오도록 설계하면 되었다.
그 부분수열을 출력해야해서 이또한 배열로 만들어서 가지고 갔는데, 터지진
않았지만 n^3의 메모리공간을 필요로하니 터질 염려가 있었다. 증가하는 방식이
대각선 혹은 오른쪽, 아랫쪽이기 때문에 값을 비교해가며 어디서 왔는지를
tracking하여 이를 역순으로 출력하면 정답이였다.
트랙킹하는 방식으로는 stack형식도 있지만, 재귀함수를 돌며 출력하게 할 수도 있었다.
void print(int y, int x) {
if (dp[y][x]==0) return;
if (s1[y-1] == s2[x-1]) {
print(y-1,x-1);
cout << s2[x-1]; // 후 출력
}
else dp[y-1][x] > dp[y][x-1] ? print(y-1,x) : print(y,x-1);
}누적합
개똥벌레문제는 누적합으로 푼다는 건 알았는데 누적합이 뭔지 몰라서 나이브하게 풀었다.
for(int i=0;i<seok.size();i++){ //석순 탐색
if(seok[i]<curH){ // 가장 높은위치에서 시작하여 부딪히지 않으면 현재까지 부딪힌 횟수 기록하고 현재위치--
i--;
crack1[curH-1]=crackCnt;
curH--;
}
else if(seok[i]>=curH){ // 부딪혔다면
while(1){
if(seok[i]<curH) break; //안부딪힐때까지 그 다음으로 작은 석순 찾기
crackCnt++;
i++;
}
crack1[curH-1]=crackCnt; // 부딪힌 횟수 기록
curH--;
i--;
}
}
crack1[0]=crackCnt;종유석에도 똑같이 적용해주면 풀렸으나, 남들에게 설명하기는 힘든 코드였다.
누적합을 사용하는 방법은 입력으로 들어오는 높이를 cnt++해주고, 높이를
한칸 씩 올려가며 그에따른 석순의 갯수--, 종유석 갯수++을 해주는 방식이였다.
for (int i = 1; i <= N; i++) {
cin >> h;
if (i % 2) {
h_down[h]++; // 석순 누적합
cur++; // 1층에선 모든 석순과 부딪힘
}
else {
h_up[H - h]++; // 종유석 누적합
}
}
for (int i = 1; i <= H; i++) {
cnt[cur]++; // 갯수 카운트
if (ans > cur) ans = cur;
cur -= h_down[i]; // 층이 오르기 전 해당 높이의 석순 제거
cur += h_up[i]; // 층이 오르기 전 다음 층에서 부딪힐 종유석 추가
}싸이클
백준 9466번. 그래프에서 사이클을 확인하는 것이 관건인 문제였다.
int dfs(int cur,int start) {
visited[cur] = 1;
int next = graph[cur][0];
if(next == start) {
return 1;
}
int isSuccess=0;
if (visited[next] == 0) {
isSuccess = dfs(next,start);
}
if (isSuccess==1) return 1;
if (cur == start) visited[cur] = -1;
else visited[cur] = 0;
return 0;
}처음에 생각했던 로직이다. 순회를 돌다가 내가 시작한 곳에 돌아오면 이를 사이클로 확인하고 재귀함수가 풀리면서 해당 노드가 사이클의 멤버인 지 알 수 있도록 했다. 하지만 시간초과가 떴고, 아무리 최적화를 해도 해결이 안되었다. 그래서 질게에서 확인을 했더니, 마지막에 사이클이 허용되고 그 전까지는 모든 노드를 순회할 수도 있다고 했다.
5
5 5 4 5 3다음과 같은 경우가 있다고 하면, 1,2번에서 분명 사이클을 순회하지만, start는 사이클이 아니므로 내 로직에서는 이를 사이클로 판단하지 못하고 그저 순회한다.
그래서 각 노드마다 모든 노드를 방문해야 하니 O(n^2)의 시간복잡도가 나온 것이다. 이를 수행하기 위해선 새로운 배열을 만들어서 관리해야했다.
void dfs(int cur) {
visited[cur] = 1;
int next = graph[cur][0];
if (visited[next] == 0) {
dfs(next);
}
else if (done[next] == 0) {
for (int i =next; i!=cur; i=graph[i][0]) {
cnt++;
}
cnt++;
}
done[cur] = 1;
}방문을 하지 않았다면 방문을 하고, 방문을 했는데 사이클이 아닌 경우라면 이는 사이클로 포함해줘야 하므로 만들어진 사이클을 순회하며 사이클 멤버의 갯수를 세주는 방식으로 구현했다.
dp의 출발지
백준 11049번. 크기가 작아서 3중 for문도 가능하겠다 생각했지만 풀이가 떠오르지 않았다. 나이브하게 푸는건 당연히 안될거고, 현재까지 계산한 경우를 저장한 1차원 dp는 빼먹는 케이스가 있는 듯해 2차원 dp를 해야할 것 같았지만 방법이 떠오르지 않았다.
떠올리지 못했던 이유는 출발지를 항상 (0,0) (1,1)이라고 생각하고 x축 혹은 y축부터 채워야 한다고 생각해서였다.
dp[i][j]에서 i를 구간의 범위, j를 출발지로 잡는다. 그리고 구간 사이를 움직이는 k를 잡아 앞에까지의 곱과 뒤의 곱을 곱해준다.
이 방법이 가능한 이유는 행렬곱셈의 특성상 결합법칙이 가능하고, 더 넓은 범위의 계산은 더 좁은 범위의 계산을 요하기 때문이다.
즉, 대각선 방향으로 먼저채우고 이를 옆으로 벌려가며 채운 후 dp[1][n]으로 출력한다.
for (int i = 1; i < n; i++) { // i : 구간의 범위
for (int j = 1; j <= n-i; j++) { // j : 시작점
for (int k = j+1; k <= i+j; k++) { // k: 분할포인트
dp[j][j+i] = min(dp[j][j+i],v[j].first*v[k].first*v[j+i].second + dp[j][k-1] + dp[k][j+i]);
}
}
}