min's devlog min's devlog

크루스칼(Kruskal) 알고리즘 Spanning Tree 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 MST (Minimum Spanning Tree) 최소 스패닝 트리 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치의 합이 최소인 스패닝 트리 '임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록' '임의의 두 집 사이에 경로가 항상 존재하면서 길의 유지비의 합을 최소로' 크루스칼 알고리즘 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. - 사이클이 발생하지 않는 경우 최소 스패닝 트리에 포함시킨다. - 사이클이 발생하는 경우 최소 스패닝 트리에 포함시키지 않는다..

Union-Find (서로소 집합) 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 • union(합집합) 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 • find(찾기) 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 Union-Find 알고리즘 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. - A와 B의 루트 노드 A', B'를 각각 찾는다. - A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다. * 일반적으로 더 번호가 작은 원소가 부모 노드(작은 원소를 가르킴)가 되도록 구현하는 경우가 많다. ..

🎈 백준 17299 오등큰수 www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 오등큰수는 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. => 수열 A에서 등장한 횟수를 카운트해서 저장한다. => 스택을 이용하여 F[A[스택의 top]] 값과 F[A[i]]을 비교한다. F[A[i]]가 더 크면 A[i]가 A[스택의 top]의 오등큰수이다. ✅ 전체 코드 import sys input = sys.std..

🎈 백준 20002 사과나무 www.acmicpc.net/problem/20002 1~K 까지의 정사각형을 설정하고 과수원 범위만큼 완전탐색하여 최대 총이익을 구할 수 있다. => 또한, Prefix Sum을 이용하여 효율적으로 구현할 수 있다. pre[i][j]에 (0,0)~(i, j) 까지의 구간합을 구한다. arr[i][j]는 주어진 2차원 배열의 총이익이다. pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + arr[i][j] 과수원 범위 안에서 시작점(i, j), 끝점이(i+k, j+k)인 정사각형의 총이익 profit = pre[i+k][j+k] - pre[i-1][j+k] - pre[i+k][j-1] + pre[i-1][j-1] ✅ 전체 코드 ..

🎈 백준 10025 게으른 백곰 www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • x 좌표마다 양동이가 있고, 각 양동이 안에는 g씩의 얼음이 들어있다. => arr 배열을 초기화하고, arr[x] = g 으로 입력값을 받는다. • 앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다. => 엘버트의 닿을 수 있는 거리의 마지막 원소가 주어진 x 좌표의 최대값만큼 이동했을 때까지 고려해야한다. - 좌표의 최..

🎈 백준 18405 경쟁적 전염 www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 바이러스는 1초마다 상하좌우 방향으로 증식해 나간다. 또한 어떤 특정 칸에 어떠한 바이러스가 존재하면, 그 곳에는 바이러스가 들어갈 수 없다. => 전형적인 bfs 문제이다. 초기 graph를 0으로 설정하고 바이러스가 있거나 번진 경우 graph를 그 바이러스로 변경시킨다. • 매 초마다 번호가 낮은 종류의 바이러스..

🎈 백준 16234 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 인구 이동은 더 이상 인구 이동이 없을 때까지 지속된다. => 인구 이동이 있는지 없는지 체크가 필요하다. • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. • 조건을 만족하는 국경선이 모두 열렸다면, 인구 이동을 시작한다 => 조건이 만족하면 모두 열고 하루 동..

DFS (Depth-First-Search: 깊이 우선 탐색) 알고리즘 스택을 이용한 DFS 동작 방식 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2의 과정을 더 이상 수행할 수 없을 때까지 반복한다. * 스택 대신 재귀 함수를 이용해서 구현할 수 있다. • 인접 리스트로 표현된 그래프에 대한 dfs 소스코드 # 인접 리스트로 표현된 그래프에 대한 dfs # V: 정점 개수, E: 간선 개수 def dfs(v): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 ..