본문 바로가기

분류 전체보기

 (689)
SCC. [11280] [1. 문제 설명] 2-SAT 는 N 개의 boolean 변수가 있을 때, 2-CNF 식을 true 로 만들기 위해 xi 를 어떤 값으로 정해야하는지를 구하는 문제이다. 2-CNF 식은 아래와 같은 형태이다. f = (x ∨ y) ∧ (￢y ∨ z) ∧ (x ∨ ￢z) ∧ (z ∨ y) N 개의 변수가 있고, M 개의 절이 주어질 때, 식 f 를 true 로 만들 수 있다면 1, 없다면 0을 출력한다. [2. 풀이 접근] 각 절(clause) 들이 모두 true 가 되어야, 전체 식 f 가 true 가 된다. p ∨ q 를 참으로 하는 명제는 아래와 같다. !p -> q !q -> p 정리하면, p 와 q 둘 중 적어도 하나는 true 이어야 한다. p 가 true 이면, q 는 어느 값이어도 상관이 없..
SCC. [4013] [1. 문제 설명] 위와 같이 교차로 에 ATM 및 레스토랑이 있을 때, 시작 점이 주어지고, 어떤 레스토랑까지 이동하면서 인출 할 수 있는 현금의 최대 액수를 구하도록 한다. 한번 출금하면 해당 ATM 에서는 더 이상 출금 할 수 없으며. 한번 지나간 edge 를 다시 지나갈 수 있다. (원: ATM, 이중원: ATM + 레스토랑) [2. 풀이 접근] 한번 지나간 edge 를 다시 지나갈 수 있으므로, 현금을 최대한 인출 하기 위해 cycle 을 형성 할 수 있다. 풀이 개요 전체 그래프를 SCC 단위로 나눈다. 시작 위치를 포함하는 SCC 에서 출발한다. 레스토랑이 있는 SCC 를 방문 하는 모든 경우를 체크하여 최대 값을 구한다. 최대한 많은 현금을 인출하기 위해 같은 SCC 에 속한 모든 노드를 ..
SCC. [3977] [1. 문제 설명] 다른 모든 구역에 도달할 수 있는 시작 구역을 찾는다. 없으면, Confused 를 출력하고, 있다면, 시작 구역을 오름차순으로 출력한다. [2. 풀이 접근] A. 단순한 풀이 dfs 를 수행하여 모든 정점에 도달 할 수 있는 경우가 시작 구역이 된다. 모든 정점을 대상으로 dfs 를 수행한다. 단, 시간 초과가 발생하므로, 이 풀이는 폐기해야 한다. B. SCC 를 이용한 풀이 같은 SCC 에 속한 노드들은 항상 그 경로가 존재한다. 이러한 특성을 이용하여 SCC 에서 SCC 로 이동 하는 경우를 생각한다. 어떤 SCC 에서 다른 SCC 를 모두 방문할 수 있다면, 이 SCC 에 속한 노드만 출력하면 되기 때문이다. 방향 그래프에서 각 SCC 사이를 연결하는 간선들을 모으면, SCC..
SCC. [4196] [1. 문제 설명] 도미노 블록의 배치가 그래프 형태로 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최소값을 출력한다. [2. 풀이 접근] A. 잘못된 접근 dfs 를 수행하면 현재 블록을 기준으로 넘어 질 수 있는 블록들이 모두 방문된다. 이러한 점을 이용하여, dfsAll() 을 실행하여 호출 될 수 있는 dfs() 횟수를 출력한다. 이 풀이가 틀린 이유는 아래와 같은 경우처럼, 최초 dfs 호출 대상에 따라 답이 바뀌기 때문이다. B. 올바른 접근 모든 정점을 SCC 로 묶는다. 이 SCC 속한 블록들은 어떤 블록을 선택하더라도 모두 넘어지게 된다. 이 SCC 에서 다른 SCC 로 연결된 경우를 고려한다. 이 SCC 를 수동으로 넘어뜨린 경우, 연결된 SCC 에 속..
DFS 스패닝 트리 및 edge 의 유형 [1. 개요] 그래프를 대상으로 DFS 를 수행하였을 때, 사용 된 edge 를 모으면, 하나의 tree가 완성 되며, 이 tree 를 dfs 스패닝 트리라 한다. 특히, 연결 그래프를 대상으로 한 탐색 과정에서 이미 방문한 정점으로 향하는 edge 를 무시하지 않고, 이 정보를 수집하면 그래프에서 사용된 edge 를 아래와 같이 4가지 유형으로 분류 할 수 있다. 트리 간선 순방향 간선 역방향 간선 교차 간선 이러한 Edge 의 분류는 DFS 를 어떤 노드부터 시작하느냐에 따라 달라지게 된다. 또한, 무방향 그래프에서는 교차 간선은 존재하지 않고, 순방향/역방향 간선에 구분이 없다 무방향 그래프에서 교차 간선이 존재하지 않는 이유는 # edge: {u, v} 가 교차 간선이 되기 위해서는 # v 를 먼..
SCC. [2150] [1. 문제 설명] 방향 그래프가 주어졌을 때, 그래프 내 SCC(=강결합 컴포넌트) 개수와 각 컴포넌트에 속한 정점 번호를 출력한다. [2. 풀이 접근] 강결합 컴포넌트 (이하 SCC) 란 방향 그래프에서 서로 다른 임의의 두 정점 u ~> v 와 v ~> u 로 가는 경로가 존재하는 컴포넌트를 말한다. 위 그림에서 (a, b) (b, e) (e, a) 는 모두 경로가 존재하므로, 같은 SCC 에 속하게 된다. 이러한 SCC 를 구하는 알고리즘 중 타잔 알고리즘을 적용하여 문제를 해결하도록 한다. 타잔 알고리즘 동작 원리는 아래 링크를 참조하도록 한다. [3. 코드]
Java. Arrays [1. 개요] Arrays 클래스를 이용하여 배열을 제어하는 방법을 정리한다. [2. 예제]
Java. ArrayList [1. 개요] List collection 중 ArrayList 사용법을 간단히 정리한다. [2. 예제]
자바 io 성능 [1. 개요] 알고리즘 문제 풀이 시 입출력 성능 차이로 인한 시간 초과 방지를 위한 내용 정리 [2. 기존] [3. 개선] [4. 장단점] 버퍼 방식에서는 한 줄의 문자열을 읽어오기 때문에 항상 문자열을 split 한 후, int, double 등으로 파싱해서 사용해야 한다. 또한, 출력 시에는 버퍼를 반드시 main() 메소드 종료 전 비워줘야 한다. 비워주지 않으면, 출력이 안될 수 있다. 혹은 main() 메소드 종료 전 Reader / Writer 스트림 자체를 소멸해도 된다.
manifest 지정 [1. 개요] maven build 후 jar 파일 실행 시 기본 Manifest 속성이 없는 경우 대처 한다. [2. 방법] pom.xml 내 main class 지정을 한다. 에 수행 할 main 메소드를 갖는 class 를 명시한다. 패키지가 있는 경우 패키지 까지 명시해야 한다.

티스토리툴바