코딩하는 두꺼비

programmers.co.kr/learn/courses/30/lessons/49191

python으로 코테를 준비할 때 고득점 킷/그래프 이론에서 풀었던 문제이다. 처음 접근법을 생각해내긴 했는데 그것을 잘 가공해서 구현을 했어야 했는데 그걸 실패해 결국 다른 사람의 풀이를 보고 풀 수 있었다.

파이썬 set의 활용에 대해서 좀 더 공부하면 좋을 것 같다.

이 문제에서 중요한 것은 인접행렬과 비슷하게 승리와 패배 셋을 잘 만들어주고(A가 B를 이겻다면 A의 승리셋에 B를 넣어주고 B의 패배셋에 A를 넣어준다.)

승 갯수와 패 갯수가 n-1이 되는 사람이 답이라는 것을 캐치하는 것이 중요한 것 같다.

def solution(n, results):
    answer = 0
    win = {x:set() for x in range(1, n+1)}
    lose = {x:set() for x in range(1, n+1)}
    for a, b in results:
        win[a].add(b)
        lose[b].add(a)
    
    for i in range(1, n+1):
        for winner in lose[i]:
            win[winner].update(win[i])
        for loser in win[i]:
            lose[loser].update(lose[i])
            
    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n-1:
            answer += 1
    
    return answer

programmers.co.kr/learn/courses/30/lessons/68645#

쉬운 문제인 줄 알고 접근했는데 생각보다 어려워서 시간을 많이 썻다..

처음 접근할 때 3가지 방향을 나눠서 하는 법은 생각했지만 좌표를 설정해서 조절하는 것을 생각하지 못한 것이 잘못했다고 생각한다.

그래서 풀이를 위해서

1. 위에서 왼쪽 아래로 나가는 방향, 일직선 가로로 나가는 방향, 아래 오른쪽에서 위쪽 대각선으로 나가는 방향으로 모드를 나누었다. (이 부분은 모듈러 연산을 사용하는 것이 더깔끔할듯?)

2. x,y 좌표를 만들어서 n, n-1, n-2...씩 연산을 해주고 각 모드의 연산이 끝나면 x,y좌표를 재설정해주었다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int dal[1001][1001];

vector<int> solution(int n) {
    vector<int> answer;
    int mode = 1;
    int cnt = 1;
    int x = 0, y = 0;
    for(int i = n; i >= 1; i--){
        if(mode == 1){
            for(int j = 0; j < i; j++){
                dal[x+j][y] = cnt;
                cnt++;
            }
            x += i-1;
            y += 1;
            mode++;
        }else if(mode == 2){
            for(int j = 0; j < i; j++){
                dal[x][y+j] = cnt;
                cnt++;
            }
            x -= 1;
            y += i-2;
            mode++;
        }else{
            for(int j = 0; j < i ; j++){
                dal[x-j][y-j] = cnt;
                cnt++;
            }
            x -= i-2;
            y -= i-1;
            mode = 1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            answer.push_back(dal[i-1][j]);
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/12913

처음 문제를 접했을때 DP로 푸는 것임을 직감할 수 있었다.

좀 더 깔끔하게 문제를 풀고 싶었는데 좋은 방법이 생각이 안나서 그냥 무작정 모든 경우의 수를 나눠서 풀었다.

DP배열 크기를 실수로 40004로 하니 segmentaion fault가 났던 것을 생각하면 항상 배열이나 벡터를 선언할때

사이즈를 잘보고 넉넉하게 선언하는 것이 중요할 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cmp(int a, int b, int c){
    int temp;
    temp = max(a,b);
    temp = max(temp, c);
    return temp;
}

int dp[400000];

int solution(vector<vector<int>> land){
    int answer = 0;
    int a = 0;
    for(int i = 0; i < land.size(); i++){
        for(int j = 0; j < 4; j++){
            dp[a] = land[i][j];
            a++;
        }
    }
    int n = land.size()*4;
    for(int i = 4; i < n; i++){
        if(i % 4 == 0){
            dp[i] += cmp(dp[i-1], dp[i-2], dp[i-3]);
        }else if(i % 4 == 1){
            dp[i] += cmp(dp[i-2], dp[i-3], dp[i-5]);
        }else if(i % 4 == 2){
            dp[i] += cmp(dp[i-3], dp[i-5], dp[i-6]);
        }else{
            dp[i] += cmp(dp[i-5], dp[i-6], dp[i-7]);
        }
    }
    answer = cmp(dp[n-1],dp[n-2],dp[n-3]);
    answer = max(answer, dp[n-4]);
    return answer;
}

www.acmicpc.net/problem/1922

앞서 풀었던 최소 스패닝 트리 문제와 사실상 동일한 문제였다.

하지만 런타임에러로 고생을 했었는데

edge.resize(100001);

이부분에서 resize를 m+1로 하니 너무 작게 선언한 것이 문제가 되어 결국 런타임에러가 발생해서 이유를 찾는데 고생을 했다.

다음 부터 mst문제를 풀 때에는 STL의 크기에 대해서 잘 생각을 하고 구현을 해야겠다고 생각했다.

또한 프림 알고리즘을 푸는 것이외에 크루스칼 알고리즘으로 푸는 것에 대해서도 공부를 좀 해봐야겠다.

#define _CRT_SECRUE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int n, m, sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;
	for (auto u : edge[v]) {
		if (!visit[u.second]) {
			pq.push(u);
		}
	}

	while (!pq.empty()) {
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int a, b, c;
	cin >> n >> m;
	edge.resize(100001);
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		edge[a].push_back({ c,b });
		edge[b].push_back({ c,a });
	}
	prim(1);
	cout << sum;
	return 0;
}

www.acmicpc.net/problem/1197

문제를 보고 크루스칼 알고리즘이나 프림알고리즘으로 풀어야 겠다는 생각을 했는데

둘 다 실제로 구현해본적이 없어서 고민을 하다가

결국 답을 보고 풀 수 있었다..

#define _CRT_SECRUE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int v, e, c;
long long sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;		//방문 노드 체크
	for (auto u : edge[v]) {
		if (!visit[u.second]) {		//방문 노드에 연결된 모든 간선 추가
			pq.push({ u.first, u.second });
		}
	}

	while (!pq.empty()) {		//방문 노드와 연결된 간선 중 최소값 더하기
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int x, y, z;
	cin >> v >> e;
	edge.resize(v + 1);
	for (int i = 0; i < e; i++) {
		cin >> x >> y >> z;
		edge[x].push_back({ z,y });
		edge[y].push_back({ z,x });
	}
	prim(1);
	cout << sum;
	return 0;
}

출처: dhpark-ghost.herokuapp.com/2018/06/12/c-peurim-prim-algorijeum/

www.acmicpc.net/problem/5014

처음엔 dfs로 해결하려고 문제를 접근했지만 원하는 층에 접근하지 못하는 경우가 있기에 이 부분을 조절할 수 없을 것

같아서 포기했다.

알고리즘 분류를 보지않고 풀려고 했는데 결국 실패하고 분류를 본 후에 bfs임을 알고 문제를 풀 수 있었다ㅠㅠ

문제 분류를 안 후에는 그냥 전형적인 bfs문제라서 편하게 반복문안에 엘베가 위로 올라가는 경우와 내려가는 경우를 모두 고려해서 풀 수 있었다.

쉬운 문제였지만 문제를 보고 알고리즘을 파악하는 방법을 더 키워야 할 것 같다!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

queue<int> q;
int ans, cnt;
int F, S, G, U, D;

void bfs(int S, vector<int> &v) {
	v[S] = 1;
	q.push(S);
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			int x = q.front();
			q.pop();
			if (x == G) {
				ans = cnt;
				return;
			}
			if (x + U <= F && v[x + U] == 0) {
				v[x + U] = 1;
				q.push(x + U);
			}
			if (x - D >= 1 && v[x - D] == 0) {
				v[x - D] = 1;
				q.push(x - D);
			}
		}
		cnt++;
	}
	return;
}

int main() {
	cin >> F >> S >> G >> U >> D;
	vector<int> visit(F+1);
	bfs(S, visit);
	if (S == G) {
		cout << 0;
	}
	else {
		if (ans == 0) {
			cout << "use the stairs";
		}
		else {
			cout << ans;
		}
	}
	return 0;
}

취업 준비를 하면서 깃허브 관리와 블로그 관리에 절실함을 느끼게 되었고

그래서 한번 시작해보려한다!!

혼자서 프로젝트도 해보고 알고리즘 문제 풀이에 관해서 올릴 예정이다.

오늘 이후로 1일 1커밋 + 일주일에 3회 이상 블로그 글쓰기를 실천해보자!