본문 바로가기

전체 글

 (191)
2-SAT 구하기 개요 2-SAT는 N개의 논리값을 가지는 변수를 사용하여 논리곱 정규형으로 표현했을 때, 각각의 절에 변수가 2개씩 존재하는 논리식을 의미합니다. 2-SAT는 기본적으로 아래와 같은 형식을 가지고 있습니다. f = (~X1 ∨ X2) ∧ (~X2 ∨ X3) ∧ (X1 ∨ X3) ∧ (X3 ∨ X2) 이렇게 논리식 f를 참(true)로 만족하게 만드는 X1 ~ X3까지의 값을 구하는 것이 2-SAT 문제의 핵심입니다. 그럼 2-SAT의 값은 어떻게 구할 수 있을까요? 물론 X1 ~ X3까지 참(true)과 거짓(false)을 하나씩 넣어보는 브루트포스 방식으로 풀 수 있습니다. 그리고 2-SAT를 제외한 대부분의 CNF 문제(Ex. 3-SAT, 5-SAT)들은 NP-Hard문제로 브루트포스 방식으로 해결해..
SCC 구하기 개요 SCC(강결합 컴포넌트)란 Strongly Connected Component의 약자로, 방향 그래프에서 서로 연결되어 있는 정점들의 집합을 의미합니다. 여기서 말하는 연결은 같은 집합 내 모든 정점들이 서로를 방문할 수 있는 상태를 의미합니다. 영문 위키피디아의 그림을 참고해보면 쉽게 이해할 수 있습니다. 아래 그림을 보면 { a, b, e }는 하나의 집합으로 묶여 있으며, 각각의 정점에서는 같은 집합에 포함된 정점으로 방문할 수 있습니다. 이렇게 방향 그래프을 서브 그래프로 나눈 것을 의미합니다. 그럼 SCC는 어디에 사용할 수 있을까요? SCC를 활용하여 그래프를 서브 그래프로 나누면 우리는 SCC를 정점으로 하는 DAG(Directed Acyclic Graph)를 만들 수 있으며, 이 과정..
오아시스 재결합( BOJ 3015 ) 문제 : https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 문제 파악하기 N명의 사람 중 서로를 볼 수 있는 사람이 총 몇 명인지 구하는 문제입니다. 서로를 볼 수 있다는 의미는 두 사람 사이에 어느 누구보다도 큰 사람이 없다는 의미입니다. 즉, 어느 한 사람만 볼 수 있는 경우는 제외해야 합니다. 예를 들어, 3명의 사람이 [ 6 5 4 ] 순서로 서있다고 가정해봅시다. 이 경우 가장 맨 앞의 사람(6)은 나머지 사람들(..
Parcel( BOJ 16287 ) 문제 : https://www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 문제 파악하기 N개의 숫자 중 4개의 서로 다른 숫자의 합이 정확하게 W를 만족하는 경우가 있는지 찾는 문제입니다. N의 값이 최대 5,000이라 작은 편이지만 모든 경우의 수를 탐색하는 O(N4) 알고리즘을 사용하기에는 충분히 큰 숫자입니다. 따라서, 적절한 탐색 기법을 활용해 O(N2) 알고리즘으로 바꾸어야 합니다. 어떻게 해야 알고리즘..
책 페이지( BOJ 1019 ) 문제 : https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 파악하기 1 페이지부터 입력된 N 페이지까지 모든 페이지에서 등장한 숫자(0-9)의 개수를 구하는 문제입니다. N의 범위가 작다면 반복문을 활용하여 쉽게 구할 수 있지만 최대 10억까지 입력될 수 있기에 단순히 반복문으로는 구할 수 없습니다. 이 경우, N을 잘게 나눠서 문제를 해결할 수 있습니다. 문제 해결하기 N을 어떻게 나눌 수 있을지 생각해보는 건, 어떤 상황일 때 숫자의 개수를 구하기 쉬운지 생각하면 됩니다. 만약 N이 1234라면 어떻게 ..
최대공약수들( BOJ 10244 ) 문제 : https://www.acmicpc.net/problem/10244 10244번: 최대공약수들 n개의 수로 이루어진 수열 A가 주어질 때, 1≤lo≤hi≤n의 정의역을 가지는 함수 f(lo,hi)는 Alo부터 Ahi까지 모든 원소들의 최대공약수로 정의된다. lo와 hi는 수열의 원소가 아닌 인덱스라는 점에 주 www.acmicpc.net 문제 파악하기 f(lo, hi)를 A[lo] ~ A[hi] 사이의 모든 숫자의 최대공약수라고 할 때, f(lo, hi)의 값이 될 수 있는 모든 경우의 수를 구하는 문제입니다. 수열의 길이는 최대 100,000이기에 모든 구간을 확인할 수는 없지만 다행히 수열의 원소 값인 a의 범위는 1~100 사이의 정수로 범위가 작습니다. 이 점을 활용하면 문제를 해결할 수..
홍준이의 친위대( BOJ 3948 ) 문제 : https://www.acmicpc.net/problem/3948 3948번: 홍준이의 친위대 홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 나머 www.acmicpc.net 문제 파악하기 N개의 숫자를 규칙에 맞게 세우는 경우의 수를 구하는 문제입니다. 통칭 지그재그 수열이라고 불리는 이 수열의 가짓수를 세는 방법에는 여러가지가 있지만, 점화식을 사용하여 가짓수를 구하는 방법을 사용해보겠습니다. 문제 해결하기 홍준이가 원하는 방식으로 나열한 N개의 숫자는 두 번째 숫자의 크기에 따라 2가지 종류로 구분할 수 있습니다. 두 번째 숫자는 첫 번째 숫자보다 클 ..
스승님 찾기( BOJ 15979 ) 문제 : https://www.acmicpc.net/problem/15979 15979번: 스승님 찾기 첫째 줄에 (M, N) 좌표로 이동하기 위해 필요한 최소 순간이동 횟수를 출력한다. www.acmicpc.net 문제 파악하기 (0, 0)에서 (M, N)까지 이동하는데 필요한 순간이동 횟수를 구하는 문제입니다. 순간이동은 항상 현재 좌표에서 볼 수 있는 좌표로 이동할 수 있습니다. 떠올릴 수 있는 가장 간단한 방법은 최대공약수를 구하는 것입니다. 입력된 좌표값 (M, N)의 최대공약수를 구하면 (0, 0)에서 해당 숫자까지 이동하는 최단 직선 거리로 이동하는 순간이동 횟수를 구할 수 있습니다. 하지만 이 방법은 아쉽게도 반례가 있습니다. 만약 (3, 3)으로 이동하려면 어떻게 해야할까요? (3, 3)..

티스토리툴바