16.4 졸업 학기
1학년 때 엄청나게 논 태우를 도와주는 문제입니다. 자세한 내용은 책을 참고해주시면 됩니다. 문제 : N개의 과목 중 K개 이상을 수강해야 졸업이 가능하다. 그리고 한 학기마다 열리는 강의의 수는 제한되어있고, 해당 과목을 수강하기 위해서는 선수과목을 들어야한다. 입력 테스트 케이스 C, 전공과목 수 N, 들어야하는 과목 수 K, 학기의 수 M, 한 학기 최대 수강 과목 수 L이 주어진다. 그리고 N개의 줄에 0번 과목부터 선수과목의 목록이 주어진다. 선수과목의 개수와 선수과목 목록을 입력받는다. 예를 들어, 2번 과목의 줄에 3 0 1 3 인 경우 선수과목 3개, 선수과목 목록 : 0,1,3 번 과목 인 것이다. 그 다음으로 해당 학기에 개설되는 과목의 수와 과목 목록을 입력받는다. 예를 들어, 2번 ..
2권의 첫 내용은 비트마스크이다. 익히 알고 있는 내용이지만 새롭게 알게 된 내용도 있고 하여 정리해 보겠다. 우선 비트마스크란, 말 그대로 비트를 가지고 집합과 유사하게 연산하는 것이다. AND, OR, XOR, NOT, shift 연산 등이 있다. 유의 사항 1. C++, java 에서는 &, |, ^, 등 비트 연산자가 ==, != 등 비교 연산자보다 우선순위가 낮다. 반면 파이썬의 경우 비트 연산자의 우선순위가 더 높다. 언어마다 우선순위가 다르니 괄호를 통해 확실히 하는 것이 좋다. 2. 자료형이 다른 경우 오버플로우가 발생한다. 예를 들어, long long a, int b 에 대해 a & (1
원래 재작년에 1권을 봤었다. 그 때는 자료구조도 뭔지 잘 모르고 일단 친구가 알고리즘 공부에는 이 책이 좋다고 하여 1,2권을 바로 샀었다. 하지만 1권만 본 뒤 2권은 보지 못했다. (사실 그 때는 뭘 잘 모르던 때라 그냥 따라 친 수준) 이번 겨울 방학 때부터는 알바 안 하고 공부만 할 것이기 때문에 방학은 조금 지나갔지만 2권을 볼 것이다. 목표는 방학 안에 2권 다 보는 것이다. (지금은 전체적인 내용을 알고 있기 때문에 보는 데 오래 걸리진 않을 것 같다.) 책에 나온 개념을 간단히 정리하고, 예제를 직접 풀어보도록 할 예정이다.
www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 최소공통조상 트리 문제이다. 트리가 연결되어있을 때 두 노드의 최소 공통 조상을 구하는 문제이다. 예를 들어 3-4-5, 3-6-7 으로 트리가 연결되어있으면 5와 7의 최소공통조상은 3인 것이다. 틀렸던 풀이 1. 처음에는 두 노드 중 더 위에 (깊이가 안 깊은) 있는 노드 A에 대해서 dfs를 이용해 트리를 탐색해 찾고자하는 더 깊은 노드 B가 있는지 판단하고, 없으면 A의 조상 노드에 대해서 다시 탐..
www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 전형적인 dp문제이다. 우선 0~k원까지 전부 inf로 초기화 한다. 그리고 dp[동전 가치]=1로 잡는다. (1개로 만들수 있으므로) 그러면 점화식이 다음과 같다. dp[ j + coin[i] ] = min( dp[ j + coin[i] ], dp[ j ] + 1) 여기서 j는 구하고자 하는 가치이다. 우선 우리는 dp를 inf로 초기화하였고, 동전의 개수 제한이 없으므로, i번..