반응형 { Computer Science }76 [알고리즘/파이썬] 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. 가비지 컬렉션(Garbage Collection, GC) 알아보기 GC란? Java의 경우, 유효하지 않은 메모리인 가비지를 JVM의 가비지 컬렉터가 자동으로 메모리에서 해제시켜준다. GC 기본 동작 과정 1. Stop the world 가비지 컬렉션 실행을 위해 어플리케이션이 일시 정지가 되는 상태. GC를 수행하는 스레드를 제외한 모든 스레드는 동작을 멈춘다. 2. Mark and Sweep 사용되는 메모리와 사용되지 않는 메모리를 식별(Mark)하고 사용하지 않는 메모리를 힙으로부터 해제(Sweep) Minor GC와 Major GC 힙영역을 물리적으로 Young 영역과 Old 영역으로 나눈다. - Young 영역(Young Generation) 새롭게 생성된 객체가 할당되는 영역 대부분의 객체가 금방 Unreachable 상태가 되기 때문에, 많은 객체가 You.. 2022. 4. 14. [데이터베이스] 트랜잭션 격리 수준 트랜잭션 격리 수준이란, 하나의 트랜잭션에서 작업 중인 데이터가 다른 트랜잭션에 영향을 받지 않는 정도를 뜻한다. 반대로 하나의 트랜잭션에서 작업 중인 데이터를 다른 트랜잭션에서 어느 정도까지 접근할 수 있는 가를 나타낸다. 일반적으로 격리 수준을 낮게 생성하면 동시성은 좋아진다. 반대로 격리 수준을 높게 생성하면 동시성이 나빠진다. 하지만 격리 수준을 높임으로써 정확성을 확보할 수 있게 된다. 따라서 정확도와 동시성을 모두 확보할 수 있는 방안을 항상 고민해야 한다. 다음과 같이 4단계가 있다. 아래로 내려갈수록 격리 수준은 높은 단계다. READ UNCOMMITTED READ COMMITTED REPEATABLE READ SERIALIZABLE READ 레벨 0. READ UNCOMMITTED SEL.. 2022. 4. 11. [알고리즘/파이썬] 최소 공통 조상(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. 이전 1 2 3 4 ··· 13 다음 반응형
