알고리즘/BOJ (5) 썸네일형 리스트형 [BOJ 2302] 극장 좌석 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 2부터는 d - 1의 경우의 수와 d - 2의 경우의 수를 더하면 된다. (피보나치) [BOJ 15480] LCA와 쿼리 https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)가 주어진다. 다음 M개의 줄에는 쿼리를 나타내는 r, u, v가 주어진다. www.acmicpc.net 만약 기존에 LCA2를 풀어봤다면 딱 case만 분류하면 끝이다. while (Q--) { int u, v, r; cin >> u >> v >> r; u -= 1; v -= 1; r -= 1; int c = LCA(u, v); if (LCA(c, r) != c).. [BOJ 5214] 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫 www.acmicpc.net 역과 역 사이에 간선을 만들면 시간초과다. 왜냐하면 하이퍼큐브는 M개이고 하이퍼큐브가 연결하는 역의 갯수가 K인데 K(K-1)개의 간선을 M.. [BOJ 16639] 괄호 추가하기 3 https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다. www.acmicpc.net 1. 연산자 우선순위 O 2. 연산자의 갯수 여러개 가능 3. 괄호의 중첩 O 3번 조건에 의해서 1번, 2번 조건은 신경 안써도 괜찮다. 1번 -> 우선순위는 괄호를 쳐서 무시하면 되고 ex) 1 + 3 * 2 ->.. [BOJ 2263] 트리의 순회 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net in order : L root R post order : L R root pre order : root L R post의 마지막은 root다. 1. post-order에서 현재 범위에서 루트가 어떤 노드인지 파악한다. 2. in-order에서 왼쪽 서브트리와 오른쪽 서브트리의 범위를 파악한다. 3. 루트를 출력하고 각 서브트리가 있다면 재귀호출한다. import sys sys.setrecursionlimit(10**9) inpu.. 이전 1 다음
