BOJ 2252 - 줄 세우기
문제 \(N(1 \le N \le 32000),\; M(1\le M \le 100000)\)이 주어진다. \(N\)개의 정점에 대해 \(M\) 개의 단방향 간선이 주어질 때, 위상 정렬의 경우의 수 중 하나를 출력해야 한다. 풀이 In-degree, DFS를 ...
Recent posts
BOJ 14003 - 가장 긴 증가하는 부분 수열 5
문제 크기가 \(N(1 \le N \le 32000)\)인 수열 \(A(-1000000000\le A_i \le 10000000000)\)이 주어진다. 수열 \(A\)의 LIS의 길이와, 정답이 될 수 있는 LIS 중 하나를 출력해야 한다. 풀이 Binary ...
BOJ 2568 - 전깃줄 - 2
문제 LIS를 \(\text{O(n log n)}\)으로 구현하는 문제이다. 각 항의 정보는 a b로 주어지는데, a가 A 전봇대와의 연결 위치, b가 B 전봇대와의 연결 위치이다. a를 인덱스, b를 값으로 보면, LIS를 구성할 수 있는 하나의 경우의 a의 집합을...
BOJ 16639 - 괄호 추가하기 3
문제 아래 조건들을 만족하는 수식이 주어진다. 길이가 1이상 19 이하 수식의 수들은 모두 한 자릿수(0-9) 연산자는 +, -, * 연산자 우선순위 존재 괄호 없음 아래 조건을 만족하며 수식에...
BOJ 16638 - 괄호 추가하기 2
문제 아래 조건들을 만족하는 수식이 주어진다. 길이가 1이상 19 이하 수식의 수들은 모두 한 자릿수(0-9) 연산자는 +, -, * 연산자 우선순위 존재 괄호 없음 아래 조건을 만족하며 수식에...