Hi

1️⃣ 기본 개념서로소 집합(Disjoint Set) 자료구조를 관리하는 알고리즘이다. 두 가지 연산을 수행한다.Find: 특정 원소가 속한 집합의 대표 원소를 찾는다.Union: 두 원소가 속한 집합을 하나의 새로운 집합으로 통합한다.집합을 트리 구조로 표현하며 트리의 루트 노드가 집합의 대표 원소가 된다. 2️⃣ 시간 복잡도$ O(\alpha(N)) $ 로, N의 크기에 관계없이 매우 빠른 연산이 가능하다$\alpha(N)$은 아커만 함수(Ackermann function)의 역함수이다. 3️⃣ 동작 과정초기화: 모든 원소에 대해 자기 자신을 부모로( $\text{parent}[i] = i$ ) 설정한 N개의 집합을 만든다Find 동작: 원소의 루트를 찾기 위해 $\text{parent}[x]$를 따..

https://school.programmers.co.kr/learn/courses/30/lessons/12980📌 문제 접근N번째 칸까지 가면서 순간이동 또는 점프를 이용할 수 있다.점프는 이동한만큼 건전지 사용량이 증가하고, 순간이동은 현재까지 이동한 칸수*2의 위치에 도달한다.문제를 읽으면서 DP를 이용하면 된다고 생각했다. 🧐 첫 번째 풀이: DP (실패)너무나 당연하게 통과할 줄 알았는데 시간초과가 났다 ㅠㅠdef solution(n): dp = [float('inf')]*(n+1) dp[0] = 0 for i in range(n): # 점프 dp[i+1] = min(dp[i]+1, dp[i+1]) # 순간이동 if 0 제한..

https://www.acmicpc.net/problem/20055 📌 문제 접근보자마자 구현문제라고 생각을 했다. 전체 길이 2N의 컨베이어에서 1번은 로봇이 올라가는 위치, N번은 로봇이 내려가는 위치이다.동작과정은 아래와 같다.벨트와 벨트 위 로봇이 함께 한 칸 회전한다.가장 먼저 올라간 로봇부터 순서대로, 이동할 수 있다면 한 칸 이동한다.이동 조건: 이동하려는 칸에 로봇이 없고, 내구도가 1 이상 남아 있어야 한다.올리는 위치의 내구도가 남아 있다면 새로운 로봇을 올린다.내구도가 0인 칸이 K개 이상이면 과정을 종료한다. 아니면 다시 1번으로 돌아간다. 💡구현 아이디어처음엔 두 가지 방법을 생각했다.윗줄/아랫줄 컨베이어를 나눠서 따로 관리인덱스를 직접 이동시키면서 관리하지만 구현이 생각보다..

https://www.acmicpc.net/problem/2573📌 문제 접근빙산은 1년 동안 동서남북 방향으로 접한 바닷물 칸수만큼 줄어든다.빙산이 두 덩어리가 됐을 때가 몇 년 후 인지 구하는 문제이다. 단 두 덩어리가 되지 못하면 0을 출력해야 한다.문제를 읽으며 dfs나 bfs로 풀면 되겠다고 생각했다. 🧐 첫 번째 풀이: DFS (실패)처음에는 DFS로 연결된 빙산을 탐색했다.def dfs(x, y): visited[x][y] = 1 for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: nx, ny = x + dx, y + dy if 0 = 2: break if cnt == 0: year..

https://www.acmicpc.net/problem/2096 📌 문제 접근원룡이가 한줄씩 내려가면서 얻을 수 있는 최대 점수와 최소 점수를 구하는 문제이다.DP를 이용해서 풀면 된다고 생각했다. 🔍 첫 번째 풀이 (실패)처음에는 이중 for문 + 2차원 DP 테이블을 사용했다.N = int(input()) arr = [[0] + list(map(int, input().split())) + [0] for _ in range(N)] mxdp = [[0] * (N + 2) for _ in range(N)] mxdp[0] = arr[0] for i in range(1, N): for j in range(1, N + 1): mxdp[i][j] = max(mxdp[i - 1][j - 1], ..

https://www.acmicpc.net/problem/1916 📌 문제 접근문제를 보자마자 며칠 전에 푼 택배 배송이 떠올랐다. 도시의 개수 N과 버스 노선 M이 주어지고, 각 버스 노선은 출발 도시, 도착 도시, 비용으로 표현된다. 목표는 특정 시작 도시에서 도착 도시까지 드는 최소 비용을 구하는 것이다. 즉, 다익스트라를 이용한 최단 거리 문제로 풀 수 있다.🔍 문제 풀이import heapqN = int(input()) # 도시 개수M = int(input()) # 버스 노선 개수# 인접 리스트 그래프graph = [[] for _ in range(N + 1)]for _ in range(M): s, e, cost = map(int, input().split()) graph[s..

https://www.acmicpc.net/problem/5972 📌 문제 접근1번 헛간에서 출발해 N번 헛간까지 이동하는 과정에서, 각 길을 지날 때마다 소에게 줄 여물의 비용이 발생한다. 목표는 여물의 총합이 최소가 되는 경로를 찾는 것이다. 즉, 최단 경로 문제로 풀면 된다.간선의 가중치가 모두 양수이므로 다익스트라 알고리즘을 적용할 수 있다N과 M의 범위가 1 ~ 50,000이기때문에 우선순위 큐를 이용하여 구현했다.[Python] 다익스트라(Dijkstra) 알고리즘 [Python] 다익스트라(Dijkstra) 알고리즘💡 기본 개념최단 경로 알고리즘 중 하나시작 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.방향그래프와 무방향그래프에서 사용할 수 있다. 💡 시간 복잡도V: 정점..

💡 기본 개념최단 경로 알고리즘 중 하나시작 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.방향그래프와 무방향그래프에서 사용할 수 있다. 💡 시간 복잡도V: 정점 수, E: 간선 수단순 구현 : O(V²)우선순위 큐 사용 : O((V + E) log V)우선순위 큐를 사용하는 것이 더 효율적이기 때문에 대부분의 경우 우선순위 큐를 사용해서 구현한다. 💡 동작 과정방문하지 않은 정점 중 최단 거리가 가장 짧은 정점을 선택해당 정점을 기준으로 인접한 정점들의 거리를 확인하고 더 짧은 경로로 갱신모든 정점을 방문할 때까지 반복 ✅ 동작 예시다음과 같이 가중치가 있는 무방향 그래프에 대해 생각해보자. (0) / \ 2 5 / \(1)---1---(2) \ 9 ..