그래프변태가 돼었다... 기본 탐색은 골3 정도까지는 건드려 볼 수 있는 수준이 된 것 같아 그래프를 졸업하고 정렬을 들어갈까 했지만 그래프 이론이라는 파트가 따로 있어서 그 부분을 먼저 건드려 본 다음에 다른 것을 해보기로 했다. 앞으로 할 그래프 이론 알고리즘은 아래와 같다. 1. 분리집합, 서로소 집합(Disjoint Sets, Union-Find) 2. 신장 트리 (MST, LST) 3. 크루스칼 알고리즘 4. 위상 정렬 알고리즘 오늘은 네가지 알고리즘 중 분리집합에 대해 공부했고, 기본 문제 하나를 풀어보았다. 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는..

from collections import deque def bfs(x, y): q = deque() q.append([x, y]) dx, dy = [1, -1, 0, 0], [0, 0, 1, -1] while q: cx, cy = q.popleft() for i in range(4): nx, ny = cx + dx[i], cy + dy[i] if 0

[백준] 안전 영역 (2468) - BFS 문제 링크: https://www.acmicpc.net/problem/2468 문제 요약 N x N 크기의 지역이 있다. 각 지역의 높이는 1 이상 100 이하의 자연수이다. 비가 내리면 높이가 같거나 낮은 지역은 물에 잠긴다. 물에 잠기지 않는 안전한 영역의 개수를 구하라. [위 문제 요약은 chat-gpt를 이용하였습니다.] import copy from collections import deque n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] max_height = max(map(max, graph)) def run(graph, visited, i, j): visit..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 아이디어에 대한 힌트는 인터넷을 참고하였다. 처음 풀어보는 유형이다. 아래 문제는 BFS를 2번 적용하여 탐색하였다. 우선 "섬" 인 곳은 라벨링을 하였고 (2~n) 여기서 섬을 찾을때 첫번쨰 BFS를 이용하였다. 두번쨰로 섬과 섬을 잇는 바다를 탐색할 때인데, BFS로 탐색 후 새로운 섬을 만나게 되면 이전의 result값과 비교한다. result와 비교하여 더 작은 값을 result에 넣은 후 마지막에 result를 출력하면 가장 짧은 다리의 거리가 나온다. 사실..

그래프 졸업의날. 일단 오늘은 골 3 문제 풀이를 무조건 완료하고 그래프를 졸업해야겠다. 그래프 졸업하면 각종 탐색 알고리즘이랑 정렬 알고리즘에 대한 공부를 시작하고 이 공부가 완료되면 다이나믹 프로그래밍, 다익스트라 순으로 공부를 진행할 예정이다. 아쉬운점은 근무때마다 수학 공부를 하기로 계획했는데, 최근 너무 바빠서 못하고 있다는 점이며, 아마 이번 일요일에는 할 수 있지 않을까 라는 생각을 하고 있다,.,

지난주부터 이번주까지 7일간 활동을 리뷰하려고 한다. 1. 구현 2. 그리디 3. 그래프 구현은 단순 피지컬이므로, 약간 맛만 보고 넘어갔고, 그리디의 어려운 문제를 풀기 위해선 보통 다른 알고리즘과 연계된다는 사실을 알았다. 또한 그리디만으로 골드 이상의 문제를 만나면,,, 너무 어렵다... 그래서 다른 알고리즘을 먼저 접하고나서 그리디 및 다른 알고리즘을 같이 하기로했다. 바로 다음장에 나온 알고리즘의 경우 "그래프" 인데, 이전부터 너무 공부해보고 싶었던 분야의 알고리즘이다. 아직 BFS, DFS라는 탐색 알고리즘만 진행했는데 상당히 많은 문제를 풀어보았고, 다음 알고리즘으로 넘어가기 위한 마지막 단계에 왔다는 생각이 들었다. 골드 3정도의 문제를 약간의 코드 참고를 이용해서 풀 정도이고, 골드 5..