본문 바로가기
반응형

전체 글 목록571

[알고리즘/파이썬] 강한 연결 요소(Strongly Connected Component) 강한 연결 요소란? 강한 연결 요소(SCC)란 노드들이 서로 자유롭게 이동 가능한 모음집이다. 하나의 그래프에서 여러개의 SCC가 존재할 수 있고, 같은 SCC 내에서는 어느 두 노드를 선택하더라도 한 노드에서 다른 한 노드로 이동이 가능해야 한다. 강한 연결 요소(SCC) 예시 아래의 그래프에는 3개의 SCC가 존재한다. a, b가 같은 SCC에 존재한다. 이 말은, a에서 b로 이동이 가능하며 b에서 a로 이동이 가능하다는 뜻이다. b, f는 다른 SCC에 존재한다. b에서 f로 갈 수는 있지만 f에서 b로 갈 방법은 없다. 강한 연결 요소 특징 무향 그래프면 당연히 서로 왕래가 가능할 것이다. 유향 그래프, 즉 방향이 존재하는 간선으로 이루어진 그래프가 SCC를 갖게 된다. 시간복잡도 O(V+E)를.. 2022. 3. 28.
[세그먼트 트리/파이썬] 백준 2042번 : 구간 합 구하기 / 골드 1 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import sys input = sys.stdin.readline n, m, k = map(int, input().split()) lst = [] for _ in range(n): lst.append(int(input())) def merge(left, right): return left + right def build(stree, no.. 2022. 3. 27.
[알고리즘/파이썬] 세그먼트 트리 segment tree 세그먼트 트리는 언제 쓰나? 배열과 같은 자료형에서 특정 구간에 속한 원소들의 연산(합, 최솟값, 최댓값 등)을 알아볼 때 선형 탐색보다 좀 더 효율적인 탐색이 가능하다. 그럼 누적합이랑 비슷한거 아닌가? 합만을 알려주는 누적합보다 좀 더 폭넓게 활용이 가능하다. 특히 특정 데이터가 변경되었을 때 누적합은 O(N)으로 누적합 데이터를 업데이트해줘야 하지만, 세그먼트는 O(logN)에 특정 데이터 변경을 반영할 수 있다. 사실 알고리즘보다는 자료구조에 가깝다. 대략 아래의 그림처럼, 어떤 배열이 존재할 때 세그먼트 트리는 그 배열의 특정 구간에 대한 정보를 추가로 담고 있게 된다. 이해가 안되면 그림을 보면 된다. 아래의 그림에서 트리의 루트 노드는 0~8번 데이터를 포함하는 정보를 담고 있다. 예를 들어.. 2022. 3. 27.
[누적합/파이썬] 백준 9527번 : 1의 개수 세기 / 골드 2 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net a, b = map(int, input().split()) psum = [0 for x in range(60)] for i in range(1, 60): psum[i] = 2**(i-1) + 2 * psum[i-1] def check(num): count = 0 bin_num = bin(num)[2:] length = len(bin_num) for i in range(le.. 2022. 3. 26.
[알고리즘] 부분합, 누적합 (Prefix Sum) 쉽게 알아보기(파이썬) 부분합, 누적합이라고 불리우는 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있게 해주는 스킬이다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 부분합을 이용하면 모든 부분합을 O(1)에 바로바로 구할 수 있다. 1차원 배열 - 직관적으로 매우 쉽게 이해가 가능하다. arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. sum[i]에는 arr[0] + arr[1] + ... + arr[i-1]의 정보가 담겨 있다고 생각하면 된다. - 활용법 arr의 i항부터 j항까지의 합을 S(i, j)라고 하자. 이때 S(i, j) = sum[j+1] - sum[i]이다. 2차원 배열 - 2차원 배열도 같은 방식이다. arr을 순차 탐색하면서 sum.. 2022. 3. 25.
[다이나믹 프로그래밍/파이썬] 백준 2098번 : 외판원 순회 / 골드 1 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net n = int(input()) board = [] for _ in range(n): board.append(list(map(int, input().split()))) dp = [[-1 for _ in range(1 2022. 3. 25.
반응형

티스토리툴바