반응형 { Computer Science }/Algorithm21 [알고리즘/파이썬] 2-sat 알고리즘 https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 위와 같은 문제가 2-sat 알고리즘이며 알고리즘 자체가 문제화되어있다. 2-sat이 무엇인지부터 설명하면 글이 매우 길어질 것이므로(나는 시간이 없다..) 해법에 대해 간략히 설명해보겠다.(기록을 위한 요약 설명이므로 부족하다면 다른 글을 같이 참고하자) 2-SAT은 함수의 각 절이 AND조건으로 연결되어있기 때문에 모든 절이 Tru.. 2024. 3. 16. [알고리즘/파이썬] 볼록 껍질 Convex Hull 알아보기 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 볼록 껍질 그 자체인 위의 문제를 보면서 볼록 껍질 알고리즘을 알아보자. 여러 점들이 좌표 상에 흩뿌려져 있을 때 그 점들을 모두 가두는 볼록 다각형을 만들어낼 수 있다.(선분 위의 점도 허용) * 오목 다각형이라면 오목의 원인이 되는 점을 빼버리면 되기 때문에 항상 볼록 다각형을 만들어낼 수 있다 * 모든 점들이 일직선 상에 있거나 점이 2개인 경우처럼 예외인 경우는 있을 수.. 2024. 3. 13. [알고리즘/파이썬] 최소 공통 조상(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. [알고리즘/ 파이썬] KMP 알고리즘 알아보기 KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다. 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다. KMP 알고리즘을 이해하려면 파이 배열에 대해 알아야 한다. 파이 배열의 i번째 성분은, 문자열의 i번째까지의 부분 문자열에서 접두사, 접미사가 같아지는 최대 길이를 뜻한다. 파이 배열의 예시는 아래와 같다. KMP 알고리즘은 2단계에 걸쳐 실행된다. 1. 주어진 패턴에 대해 파이 배열 만들어내기 2. 파이 배열을 활용하여 패턴의 등장 위치를 빠르게 찾아내기 1. 파이 배열 만들기 파이 배열의 0번째 값은 무조건 0이 된다. 한글자 짜리 문자열에는 접두사, 접미사가 없기 때문이다. 파이 배.. 2022. 3. 29. [알고리즘/파이썬] 강한 연결 요소(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. 이전 1 2 3 4 다음 반응형
