알고리즘 (117) 썸네일형 리스트형 [백준] 1922. 네트워크 연결 - 파이썬 풀이. 최소 신장 트리 알고리즘인 크루스칼 알고리즘을 이용해서 풀면된다. 최소 비용을 구해야하는 문제이니 cost를 기준으로 graph를 정렬 시킨 후 크루스칼 알고리즘을 이용하면 어렵지 않게 풀 수 있다. 최소 신장 트리 알고리즘이 가물가물해서 한번 풀어봤다. 소스코드. " target="_blank" rel="noopener">https://gist.github.com/hanhyung6376/f6622fd34ba8c968bc12afce179c4d80.js"> [백준] 11724. 연결 요소의 개수 - 파이썬 풀이. 그래프의 연결 요소끼리 각 그래프의 위치에 추가하고 깊이 우선 탐색을 실시한다. visited배열을 이용하여서 현재 위치를 방문했는지 체크를 해주고 방문하지 않은 위치라면 dfs를 실시하고 +1을 한다. 소스코드. [백준] 17435. 합성함수와 쿼리 풀이. sparse table이라는 자료구조를 이용해야한다. sparse table은 정적 구간 질의를 처리할 수 있는 자료구조인데 대부분의 구간 질의를 O(log n)시간에 처리하지만 특정한 연산에 대해서는 O(1)의 시간 복잡도를 가지는 특징을 가지고 있다. sparse table로 구간 질의를 처리하기 위해서는 배열이 정적이어야한다. 해당 문제를 살펴보면 f2(1) = f(f(1)), f4(1) = f2(f2(1))과 같은 구조로 되어있다. 즉 sparse table에는 2의 제곱으로 늘어나는 값들을 저장해서 풀면된다. 아직 확실히 이해가 되지 않아서 다시 풀어보아야 할 것 같다. 소스코드. [백준] 2170. 선 긋기 - 파이썬 풀이. 우선 좌표를 입력받아 배열에 저장을하고 정렬을 해준다 그리고 좌표의 최솟값이 -1000000000 이기때문에 now 값은 음수float('inf')값으로 설정을 하고 그래프를 반복문으로 돌면서 now 값이 start 값 보다 적다면 now 값을 start 값으로 설정하고 now 값이 end 값 보다 적다면 end - now 값을 결과 값에 저장한다 사실상 end - start의 길이를 구한다고 생각하면 되는데 여러번 선이 그인곳은 한번만 계산해야하기 때문에 now 값을 저장하는 것이다. 소스코드. [백준] 1766 문제집 - 파이썬 풀이. 진입 차수가 0인 정점을 힙에 삽입하고 힙에서 해당 원소를 꺼내고 해당 원소와 연결된 간선을 제거해준다 이후 진입 차수가 0이된 정점을 힙에 삽입을하고 힙이 모두 빌 때까지 반복을 한다. 소스코드. [백준] 3665. 최종 순위 - 파이썬 풀이. 처음에 주어진 순위들의 간선을 모두 처리하고 바뀐 순위의 간선 정보들을 처리하여 풀면된다. 즉 그래프를 통해 사이클이 존재하는지 존재하지 않는지 확인을 하고, 최종 순위를 담는 배열의 길이가 n이 아니라면 불가능의 경우로 하였다. 소스코드. [백준] 2357 최솟값과 최댓값 - 파이썬 풀이. 기존에 봤던 구간 합, 구간 곱이 아닌 구간의 최솟값, 최댓값을 구해야하는 문제이다. 우선 세그먼트 트리에 대해 알고있다면 간단하게 풀 수 있는데 최솟값을 저장하는 트리와 최댓값을 저장하는 트리를 따로 만들어서 각각의 트리를 초기화 하고 쿼리를 실행하면 된다. 소스코드. [백준] 11505 구간 곱 구하기 - 파이썬 풀이. 세그먼트 트리에대한 설명은 https://turret1234.tistory.com/229 [백준] 파이썬 2042 - 구간 합 구하기 풀이 . 세그먼트 트리를 이용하여야 한다. 세그먼트 트리(Segment Tree)란? 세그먼트 트리는 다음 두 연산을 어떻게 더 효율적으로 할 수 있을까라는 고민에서 출발한다. 1. 구간 l, r(l 이전 1 2 3 4 ··· 15 다음 목록 더보기
