본문 바로가기
반응형

전체 글 목록571

[알고리즘/파이썬] 최소 공통 조상(LCA) 알아보기(코드) Lowest Common Ancestor(LCA)는 트리 구조에서 특정한 두 노드의 공통 조상 중 가장 가까운 조상을 뜻한다. 희소 테이블을 공부한 적 있다면 매우 유사한 방식으로 진행된다. LCA풀이는 다음의 순서로 진행된다. 1. dfs로 모든 노드의 깊이, 부모를 체크한다. 여기서 부모는 바로 위 직속 부모를 말한다. 2. 위의 결과를 이용해서 모든 노드의 2**i번째 부모를 찾아 그 결과를 저장한다. 3. 두 노드가 주어지면 둘 중 더 깊은 노드를 두 노드의 깊이가 같아질 때까지 거슬러 올려보낸다. 4. 최상단 노드부터 내려오며 두 노드의 공통 부모를 찾는다. 문제로 바로 알아보자. https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수.. 2022. 4. 9.
[알고리즘/파이썬] Sparse Table 희소 테이블 알아보기(코드) Sparse table의 역할 배열에 대한 다양한 구간 쿼리를 할 수 있다. 생성에는 O(NlogN)이지만, 구간 쿼리는 O(1) (또는 O(logN))에 수행할 수 있다. 구간 쿼리에 대한 알고리즘으로 세그먼트 트리가 있는데, 그 역할과 매우 유사하다. 참고로 세그먼트 트리는 O(NlogN)시간에 생성하고 쿼리 처리는 O(logN)에 가능하다. 차이점이라면 세그먼트 트리는 mutable(변경 가능)한 자료구조이지만 sparse table은 immutable(변경 불가능)한 자료구조이다. Sparse table의 원리 sparse table은 위의 그림과 같이 2차원 배열을 갖게 된다. 이때 열 갯수는 배열 길이가 N일때 [logN]을 해주면 된다. 테이블이 어떤 방식으로 구성되어 있는 지 알아보자. s.. 2022. 4. 9.
[희소 테이블/파이썬] 백준 3117번 : YouTube / 플래5 https://www.acmicpc.net/problem/3117 3117번: YouTube 첫째 줄에 N, K, M이 주어진다. (1 ≤ N,K ≤ 100,000) (1 ≤ M ≤ 1,000,000,000) N은 학생의 수, K는 동영상의 개수, M은 남은 수업 시간이다. 둘째 줄에는 1보다 크거나 같고, K보다 작거나 같은 수가 N개 www.acmicpc.net import sys input = sys.stdin.readline n, k, m = map(int, input().split()) lst = list(map(int, input().split())) next = list(map(int, input().split())) h = 1 count = 0 while h 2022. 4. 9.
[KMP/파이썬] 백준 1097번 : 마법의 문자열 / 플래5 https://www.acmicpc.net/problem/1097 1097번: 마법의 문자열 L개의 문자로 이루어진 문자열 T가 있다. T(i)는 T를 i (0 ≤ i < L)번째 문자부터 시작하게 부터 시작하게 원형 이동한 것이고, 길이는 T의 길이와 같다. 즉, 0 ≤ j < L을 만족하는 모든 j에 대해서, T(i) www.acmicpc.net import itertools n = int(input()) words = [] for _ in range(n): words.append(input()) k = int(input()) def kmp(pattern, all_string): table = [0 for _ in range(len(pattern))] i = 0 for j in range(1, len.. 2022. 4. 8.
[컴퓨터구조] 컴퓨터의 구성 컴퓨터 종류>1. personal computer(pc)2. server computers- high performance3. supercomputers-high-end scientific and engineering calculations4. embedded computers- hidden as components of systems- 스마트폰, 태블릿pc 컴퓨터 숫자 단위>2^10 bytes = 1 Kilobyte2^20 bytes = 1 Megabyte2^30 bytes = 1 Gigabyte2^40 bytes = 1 Terabyte2^50 bytes = 1 Petabyte High-level language : C코드Assembly language: textual representation of .. 2022. 4. 8.
[다이나믹 프로그래밍/파이썬] 백준 2533번 : 사회망 서비스(SNS) / 골드 3 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net import sys sys.setrecursionlimit(10**7) n = int(input()) graph = [[] for _ in range(n+1)] for i in range(n-1): u, v = map(int, sys.stdin.readline().split()) graph[u].append(v) graph[v].append(u) dp = [[0, 1] for _ in ran.. 2022. 4. 7.
반응형

티스토리툴바