CodeDrive

문제:

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력:

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

풀이방법:

 사이클이 존재하지 않고, 방향이 존재하는 그래프 상에서의 정렬을 해야 하는 문제이기 때문에 위상정렬을 사용해서 이 문제를 푼다. 

 위상정렬의 기본 알고리즘 진행은 다음과 같다.

1. 각 입력으로 들어온 값들을 그래프 형태로 저장한다. 이와 동시에 in_degree라는 간선이 연결된 갯수를 저장하는 배열도 같이 초기화 시킨다.

2. 모든 입력을 마친 뒤, in_degree가 0인 것부터 queue(deque)에 입력해 준다.

3. queue에서 값을 하나씩 빼면서 나온 노드들이 정렬된 것이며, 해당 노드와 연결되어 있는 선을 하나씩 제거한다.

3-1. 이 때, in_degree 값이 0이 된다면 queue에 넣는다.

4. 위 과정을 queue가 비어 있을 때까지 한다.

문제링크:

https://www.acmicpc.net/problem/2252

문제:

8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다.

킹은 다음과 같이 움직일 수 있다.

• R : 한 칸 오른쪽으로
• L : 한 칸 왼쪽으로
• B : 한 칸 아래로
• T : 한 칸 위로
• RT : 오른쪽 위 대각선으로
• LT : 왼쪽 위 대각선으로
• RB : 오른쪽 아래 대각선으로
• LB : 왼쪽 아래 대각선으로

체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다. 아래 그림을 참고하자.

입력으로 킹이 어떻게 움직여야 하는지 주어진다. 입력으로 주어진 대로 움직여서 킹이나 돌이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다.

킹과 돌의 마지막 위치를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 킹의 위치, 돌의 위치, 움직이는 횟수 N이 주어진다. 둘째 줄부터 N개의 줄에는 킹이 어떻게 움직여야 하는지 주어진다. N은 50보다 작거나 같은 자연수이고, 움직이는 정보는 위에 쓰여 있는 8가지 중 하나이다.

출력:

첫째 줄에 킹의 마지막 위치, 둘째 줄에 돌의 마지막 위치를 출력한다.

풀이방법:

주어진 조건대로 구현을 하는 문제다. 이 문제에서는 크게 두 가지 조건이 있다.

1. 체스판 밖으로 나가는 경우에는 해당 이동을 건너 뛴다.

2. 킹이 이동하는 위치에 돌이 있다면 돌도 킹이 이동하는 방향과 같이 이동한다.

이 때, 1에 대한 조건은 킹에만 적용되는 것이 아니라 돌에도 적용되는 것이다. 따라서 킹을 움직였을 때, 돌이 있다면 돌을 이동시켜보고, 만약 체스판 밖으로 나간다면 킹을 다시 원래 자리로 되돌려야 한다. 해당 조건을 고려하여 command들을 구현하면 된다.

문제링크:

https://www.acmicpc.net/problem/1063

문제:

어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.

예를 들어 S="abaabba", P="aaabbbabbbaaa"인 경우를 생각해 보자. 이때는 copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), copy(1, 1) 를 수행하여 P를 만들 수 있다. 각 단계별로 P는 "aa", "aaabb", "aaabbba", …와 같이 변하게 된다.

이와 같은 copy 연산을 이용하여 S에서 P를 만들려고 하는데, 이때 가능하면 copy 함수를 조금 사용하려고 한다.

S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 없는 경우는 입력으로 주어지지 않는다고 가정하자. 각 문자열은 최소한 한 개의 문자로 이루어져 있다.

출력:

첫째 줄에 copy 함수의 최소 사용횟수를 출력한다.

풀이방법:

 P에 있는 부분 문자열을 S에서 그리디하게 찾아내어 이 문제를 해결하도록 한다.

찾으려는 P의 문자를 S에서 찾은 뒤에 그 지점으로부터 얼마나 많이 일치하는지 확인한다. 예를 들어 S="abaabba", P="aaabbbabbbaaa" 일 때, P의 첫 문자는 'a'이며, S에서는 a가 0, 2, 3, 6 번째에 위치하고 있다. python의 find 함수를 이용하여 a의 위치를 확인하고, P와 S 에서 동시에 포인터를 이동하며 얼마나 많이 일치하는지 찾는다. 다음 탐색은 일치하는 수 만큼 P의 포인터를 이동시킨다. 이 경우에는 S의 2번째에서 aa가 가장 길게 일치하므로, P의 2번째 인덱스부터 다음 탐색을 시작한다.

문제링크:

https://www.acmicpc.net/problem/2195

2.1 Introduction

이전 장에서는 확률이 어떻게 머신 러닝에서 사용될 수 있는지 살펴보았다면, 2장에서는 더 자세한 확률 이론에 대해 알아본다. 확률에 대한 기술적인 논의를 하기 전에, "확률이란 무엇인가?"라는 질문에 먼저 답해보도록 한다. 쉽게 생각할 수 있는 주제로 '동전을 던졌을 때, 앞면이 나올 확률은 0.5'라는 것은 다들 알 것이다. 사실 확률에 대한 해석은 크게 2가지가 가능하다.

1. Frequentist

• 빈도주의적인 해석으로써 장기간에 걸쳐 발생 빈도를 의미한다. 즉, 동전을 수없이 많이 던져서 앞면이 나올 확률이 0.5가 나온다는 것을 알 수 있다는 것이다.

2. Bayesian

• 베이지안 해석으로 확률은 어떤 것에 대한 불확실성을 수량화하는 것이며, 반복되는 시도보다는 기본적으로 정봐와 연관된 것이다. 즉, 베이지안적 시각으로 보면, 다음 동전 던지기 때에 앞면과 뒷면이 나올 확률은 동일하다는 것이다.

베이지안식 해석의 큰 장점은 장기간의 빈도를 가지지 않는 사건에 대한 불확실성을 모형화하는 것에 사용할 수 있다는 것이다. 따라서 이 책에서는 베이지안식 해석을 채택하여 설명하도록 한다.

2.2 A brief review of probability theory

이 절에서는 확률 이론에 대한 기초 개념을 간단히 리뷰하도록 한다. 따라서 이미 확률 이론에 대해 익숙한 사람이라면 이 절을 생략해도 무관하다.

2.2.1 Discrete random variables

p(A)는 event A가 발생할 확률을 의미한다. 예를 들어, A는 "내일 비가 올 확률"가 될 수 있다. 0<= p(A) <=1 이어야 하며, p(A)=0은 사건이 절대 발생하지 않는다는 것을 의미하고, p(A)=1은 사건이 반드시 발생한다는 것을 의미한다.
이산 확률 변수 X를 정의해서 이항 사건에 대한 개념을 확장할 수 있으며, X는 유한 집합이나 가산 무한 집합으로부터 어떠한 값도 가질 수 있다. X=x의 확률은 p(X=x)로 나타내고, 간단히 p(x)라고 나타낸다. 여기서 p()는 확률 질량 함수 또는 pmf이다.p(x)도 0과 1 사이의 값을 가지며, 총합은 1이 된다는 조건을 만족한다. 위 그림은 유한한 상태 공간에서 정의된 두 개의 pmf며, 왼쪽은 균등 분포를 가지고 있으며, 오른쪽은 퇴화 분포에 해당하며, X가 항상 1과 같다는 것을 표현한다.

2.2.2 Fundamental rules

생략

2.2.3 Bayes rule

조건부 확률의 곱, 합 법칙을 통합하면 Bayes rule을 도출 할 수 있으며, 이를 Bayes Theorem이라고 부른다.

2.2.3.1 Example: medical diagnosis

베이즈 법칙을 사용하는 예로 의학적 진단 문제를 생각해보자. 당신은 40대 여성이라고 가정하고, 유방조열술로 유방암에 대한 의학 검진을 받기로 했다. 검사가 양성일 때, 실제로 암일 확률은 얼마일까?
이 확률을 구하기 위해서는 우선 검사가 얼마나 신뢰성이 있는지 알아야 한다. 검사가 80%의 정확성을 가지고 있을 경우 당신이 암이라면 0.8의 확률로 양성이 나타날 것이다. 즉, 다음과 같다.

p(x=1|y=1) = 0.8

여기서 x=1은 유방조영술이 양성인 사건을 의미하고, y=1은 유방암인 경우의 사건이다. 대부분의 사람들이 이런 경우 80%가 암이라고 결론을 내린다. 하지만 이것은 False다! 이러한 결론은 유방암을 가지고 있는 사전 확률을 무시한 것이다. 다행히도 암을 가질 확률은 매우 낮다.

p(y=1) = 0.004

사전 확률을 무시하는 것을 기저율 에러(base rate fallacy)라고 한다. 또한 테스트가 거짓 양성 또는 거짓 정보일 케이스인 경우도 고려해야 한다. 불행하게도 거짓 양성인 가능성은 높다.

p(x=1|y=0) = 0.1

베이즈 법칙을 사용해 세 개의 조건을 모두 결합하면 다음과 같이 정확한 답을 계산할 수 있다.

즉, 검사가 양성이라면 실제 유방암일 확률은 대략 3%에 해당한다.

2.2.4 Independence and conditional independence

X와 Y의 결합 확률을 곱으로 표현할 수 있다면 무조건적인 독립, 또는 marginally 독립이라고 하며, X⊥Y로 표현한다. 즉, 다음과 같다.

일반적으로 결합 확률이 marginal의 곱이면 변수 집합이 상호 독립적이라고 한다.
대부분의 변수는 다른 변수에게 영향을 주는 경우가 많기 때문에 무조건적인 독립은 매우 드물다. 하지만 이런 영향은 직접적이라기보다는 다른 변수에 의해 중재된다. 그러므로 조건부 결합 확률이 조건부 주변의 곱으로 표현될 수 있는 경우에만 "Z가 주어졌을 때 X와 Y는 조건부 독립이다" 라고 한다.

2.2.5 Continuous random variables

지금까지는 불확실한 이산량에 대한 추정만을 다뤘으며, 이번 절에서는 어떻게 확률을 확장해야 하는지 알아본다.
X를 불확실한 연속량으로 가정한다면, X가 a이상 b이하일 확률은 다음과 같이 계산한다.

위와 같이 확률을 계산하는 것을 함수 형태로 정의하고, 이것을 X의 누적 분포 함수(cumulative distribution function) 혹은 cdf라고 정의한다. 이는 그림 (a)에 해당하고, 표기법을 사용하면 다음과 같다.

이제 도함수를 정의하고, 이것을 확률 밀도 함수(probability density function) 혹은 pdf라고 한다. 이는 그림 (b)에 해당한다. 표기법을 사용하면 다음과 같다.

2.2.6 Quantiles

cdf F가 단조 증가 함수이기 때문에 역함수를 가지고 있다. 이를 F^-1라고 하고, F의 분위수(quantile)라고 부른다. F^-1(0.5)는 중앙값이고, F^-1(0.25), F^-1(0.75)는 각각 하위 및 상위 사분위수다.

2.2.7 Meana and variance

분포를 설명할 때 가장 익숙한 속성은 평균 또는 기댓값이며, μ와 같이 표기한다. 분산은 분포의 '흩어진 정도'를 측정하는 것이며 σ2로 표기한다.

2.3 Some common discrete distributions

보편적으로 사용되는 이산 상태 공간에서 정의된 모수적 분포들에 해당한다. 자세하게 설명하지 않고, 분포의 종류들만 나열하도록 한다.

1. The binomial and Bernoulli distribuions
2. The multinomial and multinoulli distributions
3. The Poisson distribution
4. The empirical distribution

2.4 Some common continuous distributions

2.3절과 같이 분포들에 대해 나열만 하도록 한다.

1. Gaussian distribution
2. Degenerate pdf
3. The Laplace distribution
4. The gamma distribution
5. The beta distribution
6. Pareto distribution

ㅌ문제:

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력:

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력:

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

풀이방법:

 해당 문제는 N개의 센서가 있을 때, K개의 그룹으로 만드는 것이 목적이다. 따라서 다음과 같은 알고리즘 순서대로 진행한다.

1. 센서들을 오름차순으로 정렬한다.

2. 각 센서들간의 차이를 구한다.

3. 각 센서들간의 차이를 내림차순으로 정렬한다.

4. 앞에서 부터 K-1개를 제외한 나머지들을 다 합한다.

문제링크:

https://www.acmicpc.net/problem/2212

문제:

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

입력:

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력:

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

풀이방법:

 일반적인 회문 문제와는 다르게 한 번의 기회를 더 제공하는 '유사회문'이라는 추가 조건이 더 있다. 따라서 일반적인 회문을 판정하는 함수에 추가적으로 하나의 문자를 삭제하고 추가로 회문인지 판단하는 함수를 더 추가하도록 한다. 이 때, 하나의 문자를 제거할 때, 왼쪽의 문자, 오른쪽의 문자를 한번씩 모두 제거하여 유사회문이 되는지 판단하여야 한다. 만약 한쪽을 우선적으로 판단하면 오류가 되는 케이스를 발견할 수 있다.

 따라서 일반적인 회문이라면 0을 반환하고, 하나를 제거해야 하는 상황인데 왼쪽, 오른쪽을 둘 다 확인했을 때, 하나가 가능하다면 1, 둘 다 불가능하다면 2를 반환하여 출력을 할 수 있도록 한다.

문제링크:

https://www.acmicpc.net/problem/17609

케빈 머피의 Machine Learning 책을 보고 정리한 내용들입니다.

1.4 Some basic concepts in machine learning

이번 절에서는 머신 러닝에서의 주요 아이디어를 제공한다. 뒷 파트에서 더 자세히 다룰 예정이기 때문에 여기서는 간략하게만 다룬다.

1.4.1 Parametric vs non-parametric models

이 책에서는 지도 학습과 비지도 학습에 따라서 확률 모형을 다르게 구성한다. 이런 모형을 정의하는 많은 방법이 있지만, 가장 중요한 차이는 모형이 고정된 개수의 변수(Parametric)를 갖는지, 혹은 훈련 데이터의 양에 따라 개수가 증가하는지(non-parametric) 여부다. Parametric한 모형은 빠르게 사용할 수 있는 장점이 있지만 데이터분포에 대한 강한 가정(데이터 분포에 영향을 많이 받는다.)을 만들기는 어렵다. non-parametric하면 데이터 분포에 영향을 덜 받지만 계산적으로 다루기 어렵다.

1.4.2 A simple non-parametric classifier: K-nearest neighbors

non-parametric 분류기의 가장 간단한 예를 K nearest neighbor (KNN) 분류기다. 이것은 데이터 집하에서 테스트 입력 x에 가장 가까이 에 있는 K개의 포인트를 찾는 것이며, 각 클래스의 멤버가 얼마나 이 집합에 있는지 개수를 계산하고, 실험적 비율을 추정 값으로 반환한다.

1.4.3 The curse of dimensionality

KNN 분류기는 간단하며, 레이블된 훈련 데이터가 충분하게 있다면 잘 작동한다. 하지만 KNN 분류기의 주요 문제는 고차원의 입력에 대해서는 잘 작동하지 않는다는 점이다. 고차원에서 성능이 잘 나오지 않는다는 것은 curse of dimensionality(차원의 저주) 때문이다.

1.4.4 Parametric models for classification and regression

차원의 저주에 대항하는 주요 방법은 데이터 분포의 성질에 관한 가정을 만드는 것이다. 귀납적 편향성이라고 불리는 이 가정은 parametric한 모델로 구현하며, 고정된 개수의 매개변수를 가지는 통계 모형이다. 폭넓게 사용되는 두 가지의 예를 살펴본다.

1.4.5 Linear regrssion

회귀에서는 선형 회귀(Linear regression)이라고 알려져 있는 것을 주로 사용한다. 이 모형에서는 입력에 대한 식을 1차 함수로 나타낸다. 다음과 같이 식을 표현한다.

1.4.6 Logistic regression

앞서 본 선형회귀를 두 가지만 변경한다면 일반화할 수 있다. 첫번째는 선형 회귀에서는 가우시안 분포라고 가정했던 것을 베르누이 분포라고 가정한다. y의 값이 0과 1만을 가진다면 다음과 같이 분포를 정의한다.

1.4.7 Overfitting

유연한 모델을 만들기 위해서 overfit(과적합)하지 않도록 주의해야 한다. 즉, 입력의 모든 변화를 모형화하는 것을 피해야 한다는 것으로, 이런 모형일 수록 노이즈인 경우가 많기 때문이다. 위와 같은 예시가 있을 수 있다. (b)가 모든 변화를 모형화를 한 경우에 해당된다. 하지만 실제 함수가 예시와 같이 생긴 확률을 낮기 때문에, 이런 모형을 사용해서 예측을 하는 경우 부정확한 결과를 얻을 수 있다.

1.4.8 Model selection

생략

1.4.9 No free lunch theorem

대부분의 머신 러닝의 알고리즘은 새로운 모델을 만들거나, 그것들이 적합하도록 만드는 것에 관심이 있다. 특정 문제에 대해서 최적화할 수 있지만, 모든 문제에 대해 최적의 모델은 없다. 이것을 No free lunch theorem 라고 한다. 하나의 영역에서 잘 작동하는 가정이 다른 영역에서 잘 작동하는 가정이 다른 영역에서 잘못 작동하는 경우가 있다.

문제:

민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.

입력:

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다.

항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

출력:

첫째 줄에 문제 번호를 나타내는 1 이상 N 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.

풀이방법:

이 문제는 '사이클'이 없으며 '방향'만 존재하는 그래프에서 정점을 나열하는 방법으로 풀 수 있다. 이러한 문제 푸는 방법을 위상 정렬 (Topological Sort)라고 한다.

 또한 시간을 최소화하기 위해서 최소 힙을 사용한 우선순위 큐를 사용하도록 한다. 문제는 다음과 같은 알고리즘 순서로 해결한다.

1. 정점과 연결된 그래프와 해당 정점과 연결된 정점의 개수 리스트를 만든다.

2. 연결된 정점 개수 리스트(In_degree)가 없는 정점부터 먼저 최소 힙에 넣어준다.

3. 해당 정점과 연결되어 있는 정점(In_degree)들부터 하나씩 제거해 준다.

4. 연결된 정점 개수가 없는 정점이 생긴다면 최소 힙을 다시 넣어준다. 이후 3)으로 돌아간다.

문제링크:

https://www.acmicpc.net/problem/1766

문제:

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력:

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

풀이방법:

해당 문제는 다음과 같은 알고리즘으로 해결하도록 한다.

1. n개의 a m개의 z가 있다고 했을 때, a를 하나 제거했을 때의 경우의 수를 구한다.

2. 이 갯수가 k보다 크다면 a를 먼저 배치한다.

2-1. 이 갯수가 k보다 작다면 z를 먼저 배치하고, k에서 1에서 구한 값을 빼준다.

3. n이나 m 둘 중 하나가 0이 될 때까지를 이를 반복하고, 남은 n과 m이 있다면 다 이어붙이고 종료한다.

문제링크:

https://www.acmicpc.net/problem/1256

문제:

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라

입력:

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력:

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

풀이방법:

 수학 시간에 배웠던 경로의 갯수 공식을 사용하도록 한다. 사각형이 있고, 되돌아 갈 수 없다는 조건이 있다면 시작점에서 도착점까지 가는 경우의 수는 (가로변의 갯수 + 세로변의 갯수)C(가로변의 갯수 or 세로변의 갯수)다. 이 문제의 경우 격자에 하나의 중심점이 표현되어 있기 때문에, 이 점을 기준으로 두 번의 경우의 수를 구한 다음에 둘을 곱하면 최종 답을 얻을 수 있다.

 따라서 이 문제는 O 표시가 되어 있는 지점의 좌표를 정확하게 계산하고, combination 연산 공식을 구현하여 문제를 해결하면 된다.

문제링크:

https://www.acmicpc.net/problem/10164