본문 바로가기

Algorithm/Baekjoon38

5014_스타트링크 ▶ 실버 1 (BFS)풀이현재 층에서 이동하는 경우는 1) 올라가거나, 2) 내려가거나 둘 중 하나입니다.또한, 도착 층까지의 최단 경로를 찾는 것이기 때문에 BFS를 사용했습니다. 주의할 점1. 다음 층이 1부터 f 이하여야합니다.2. 이미 방문한 층은 그 경로가 최소이기 때문에 갱신할 필요가 없습니다. 그래서 BFS와 동일하게 visited 배열로 방문여부를 확인해주면 됩니다. 코드# 5014_스타트링크from collections import dequeimport sysinput = sys.stdin.readline()f, s, g, u, d = map(int, input.split())def BFS(f, s, g, u, d): if s == g: return 0 queue .. 2025. 2. 25.
16935_배열 돌리기3 ▶ 골드 5 (구현)풀이삽질 너무 많이한 문제입니다..일단 처음에 1 ~ 6번 다 나눠서 규칙을 찾았습니다.찾은 규칙으로 이중 for문 돌려서 swap 하면 된다고 생각했는데..그렇게 하니까 한 인덱스 당 swap을 두 번 돌아서 제자리로 돌아오게 되었습니다......그 다음으로 생각한 게, 이중 for문 돌려서 규칙에 따라 즉시 print근데 이렇게 하니까 연산 과정이 한 번이면 성공하는데 여러 개일 경우 모든 경우가 다 출력되었습니다......저의 멍청함에 놀라던 중, 마지막으로 생각한 게 연산을 한 번 할 때 규칙에 맞는 새로운 배열을 생성하고,연산이 끝나면 그 새로운 배열을 원 배열로 갱신해는 방식이었습니다.그리고 모든 연산이 끝나고 마지막에 배열을 출력하였습니다.  처음에는 배열 '돌리기' 라는.. 2025. 2. 24.
11057_오르막수 ▶ 실버 1 (DP)풀이규칙이 있을거라고 생각하고 작은 자리수만 적어보았습니다.# 1 -> 0 1 2 3 4 5 6 7 8 9# 2 -> 00 / 01 11 / 02 12 22 / 03 13 23 33 / 04 14 24 34 44 / ...# 3 -> 000 / 001 011 111 / 002 012 112 022 122 222 /# 4 -> 0000 / 0001 0011 0111 1111# dp[자리수][끝자리] = dp[자리수][끝자리 - 1] + dp[자리수 - 1][끝자리] 적다보니 점화식이 보여서 DP임을 깨달았습니다.이중 for문을 돌려 (시간 복잡도: O(N), 자리수가 0 ~ 9이므로.)dp 배열을 채워줍니다.해당 자리수의 가장 끝자리가 모두 그 전 자리 값들이 누적된 수이므로 답은 dp.. 2025. 2. 24.
16948_데스 나이트 ▶ 실버 1 (BFS) 풀이BFS를 이용하는 문제이다.먼저 이동할 수 있는 경우와 없는 경우를 구분하였다. (bfs를 돌리면서 이동할 수 없는지 확인할수는 없기 때문에 미리 거르는 방식으로)규칙을 찾아보니 1) x좌표(= r) 가 2의 배수인 경우, y좌표(= c)는 2k + 1이 성립.2) x좌표(= r) 가 4의 배수인 경우, y좌표(= c)는 2k 이 성립. 인 것이 보였다.이 때, 2의 배수는 4의 배수를 포함하고 있으므로 4의 배수일 경우부터 걸러야 한다. // 도착 불가인지 확인 int tmp1 = abs(r1 - r2); int tmp2 = abs(c1 - c2); if (tmp1 % 4 == 0) { if (tmp2 % 2 == 0) { ans = bfs(r1, c1, r2, c2);.. 2024. 2. 19.
3584_가장 가까운 공통 조상 ▶ 골드4 (트리) 풀이 부모 노드 값을 가지고 있는 배열: tree 조상을 담을 vector: A 를 선언하고 먼저 입력받은 간선 정보를 이용하여 각 노드의 부모 노드를 채워준다. 그 후, 공통 조상을 구할 두 노드 중 첫 번째 노드의 모든 조상 노드들을 A에 삽입한다. 마지막으로 두 번째 노드의 모든 조상 노드를 A에 삽입하는데, 이 때 A에 이미 존재하는 값이라면 이것이 두 노드의 공통 조상 노드이므로 그 값을 출력하고 배열과 vector를 초기화하고 다음 테스트케이스를 진행한다. 코드 #include #include #include #include #include #include #include #include #define MAX 10001 using namespace std; int tree[.. 2023. 8. 7.
1967_트리의 지름 ▶ 골드4 (트리) 풀이 노드들의 가중치 합 중 최댓 값을 구하는 문제인데, 중요한 것은 꼭 루트 노드를 포함해야할 필요가 없다. 그래서 모든 노드를 기준으로 dfs를 진행해서 가중치 최댓값을 구하면 된다. 코드 #include #include #include #include #include #include #include #define MAX 10001 using namespace std; int n; vector graph[MAX]; bool visited[MAX]; int ans; void dfs(int i, int value) { visited[i] = true; if (value > ans) { ans = value; } for (int j = 0; j < graph[i].size(); j++).. 2023. 8. 5.

티스토리툴바