CodeDrive

문제:

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력:

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력:

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

풀이방법:

**python3이 아닌 pypy3으로 통과한 문제입니다.**

플로이드-와샬 알고리즘을 적용하면 쉽게 풀 수 있는 문제다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다. 

이 과정을 마친 후에 a to b가 inf가 아니면 -1을, b to a가 inf가 아니면 1을 inf면 0을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/1613

문제:

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다.

출력:

가능한 모든 비밀번호의 개수를 출력한다.

풀이방법:

 처음에는 dfs를 활용한 백트래킹 방법으로 풀었다가 시간초과가 발생했다. 다른 방법을 생각해보던 중 수학적으로 풀 수 있음을 알게 되었다.

 따라서 포함배제의 원리를 사용해서 이 문제를 푼다. 문제에서 주어지는 n과 m만을 사용해서 풀수 있다.

m개의 수를 반드시 포함하는 경우의 수를 구하기 위해서 전체 가능한 경우의 수에서 m개의 수를 포함하지 않는 경우의 수를 빼는 것으로 구한다. 즉 다음과 같다.

비밀번호에 들어가는 수 m을 반드시 포함하는 비밀번호의 수 = 전체 비밀번호의 수 - m개의 수가 포함되지 않은 비밀번호의 수

전체 경우의 수는 10^n가 된다. m개의 수가 포함되지 않은 비밀번호의 수는 포함배제의 원리를 사용해서 구하도록 한다. 즉 구하는 식은 다음과 같이 된다.

answer = 10^n - mC1*9^n+mC2*8^n-mC3*7^n+.....

문제링크:

www.acmicpc.net/problem/13908

문제:

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력:

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력:

check 연산이 주어질때마다, 결과를 출력한다.

풀이방법:

python의 set의 내장함수를 적절히 사용하면 쉽게 풀 수 있다.

1. add : set의 add를 사용한다. python의 set은 중복을 지원하지 않기 때문에 x가 이미 있는 경우에는 중복으로 들어가지 않는다.

2. remove : set에서 원소를 제거하는 방법은 remove와 discard가 있다. remove는 원소가 없는 경우 에러를 반환하지만 discard를 그렇지 않다. 따라서 discard를 사용한다.

3. check : python의 in 기능을 사용한다.

4. toggle : 1. add, 2. remove, 3.check의 기능을 적절히 활용하면 된다. 이 명령어에서 원소를 제거하는 경우에는 항상 있다는 보장이 있으므로 remove를 사용했다.

5. all : S를 재정의한다.

6. empty: S를 재정의한다.

연산의 수가 매우 많으므로 sys.stdin.readline()를 사용해서 빠른 입력을 사용한다.

문제링크:

www.acmicpc.net/problem/11723

문제:

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

풀이방법:

 주어진 수가 1,000,000,000로 엄청 크게 주어졌기 때문에 A~B 사이의 수가 4와 7로 이루어져있는지 탐색하는 것은 시간초과가 발생할 것이다. 따라서4와 7로 구성된 숫자를 만들면서 이 숫자가 A~B 사이에 있는지 확인하도록 한다.

 A와 B가 큰 수로 주어질 수도 있기 때문에 깊이라는 개념을 사용해서 최대한 탐색할 수 있도록 했다. 깊이는 상한값으로 인해 최대 9까지 가능하다. 깊이라는 개념이 추가되었기 때문에 깊이우선탐색을 사용해서 값을 만들어내도록 한다.

 생성된 값이 주어진 범위 안에 들어 있으면 count를 1 올려주고 상한 값을 넘어가면 더 빠른 탐색을 위해서 0을 반환하도록 했다. 하한값에 보다 작은 값에 대해서는 조건이 없는데, 그 이유는 앞서 말했던 A와 B가 큰 수로 주어졌을 때, 그 범위 내까지는 이동하도록 하기 위함이다.

문제링크:

www.acmicpc.net/problem/1527

문제:

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다.

출력:

합이 0이 되는 쌍의 개수를 출력한다

풀이방법:

***Pypy3으로 통과한 문제입니다.***

 이 문제를 그냥 완전탐색으로 풀면 O(N^4)가 되고, N은 최대 4000까지 주어지므로 시간초과가 발생할 것이다. 따라서 4개의 배열을 두개씩 묶어서 O(N^2)으로 줄이도록 한다.

 A와 B의 가능한 합의 경우의 수를 담고 있는 one을 해싱 방법으로 딕셔너리 형태로 저장한다. 포함되는 정수가 중복이 없다는 조건이 없기 때문에, 해당하는 키가 여러개 존재할 수 있으므로 key,value = (두 정수의 합, 나타나는 횟수)와 같이 딕셔너리 형태로 저장한다.

 C와 D의 가능한 합의 경우의 수를 구하면서 이 합의 마이너스 부호를 취한 것이 one 딕셔너리에 있다면 합이 0이 되는 경우이므로 value 값을 answer에 더하도록 한다.

**[21.01.17 수정]현재 재채점으로 인해 아래 코드도 통과하지 못합니다.**

문제링크:

www.acmicpc.net/problem/7453

문제:

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력:

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력:

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이방법:

www.acmicpc.net/problem/2293 의 동전 1 문제를 응용해서 풀면 된다. 이 문제에서는 k원을 만드는 경우의 수를 구하는 문제였지만, 이 문제에서는 최솟값을 구해야 한다. 따라서 동전의 가치가 최대 100,000원이므로 초기값으로 100,001원(0원은 0으로 초기화 한다.) 으로 설정하고, 작은 동전부터 사용해서 각 p원을 만들 수 있는 최소 갯수를 구하도록 한다.

 이 문제의 예시로 생각하면 다음과 같다. (1,5,12)원이 있을 때, 1원으로 15원을 만드는 방법은 다음과 같이 비교할 것이다.

 위 표는 다음 두 조건을 비교하면서 채워나갔다. 1원을 만드는 경우로 예시를 든다.

1. 현재 값을 그대로 사용한다. dp[1]

2. 0원에서 1원을 더해서 사용한다. dp[1-1]+1

3. 1과 2중 더 작은 값을 사용한다. min(dp[1],dp[1-1]+1)

즉 이를 일반화 하면 다음과 같다. min(dp[n],dp[n-c]+1), n은 현재 만들고자 하는 금액, c는 현재 사용하고 있는 동전의 가치다.

 5원을 사용하는 경우는 1~4원은 만드는 것이 불가능하므로 5원부터 반복한다.

 12원을 사용하는 경우는 1~11원은 만드는 것이 불가능하므로 12부터 반복한다.

 최종적으로는 dp[k]원이 초기화한 값에서 변경이 되었다면 dp[k]를 출력하고, 바뀌지 않았다면 -1을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2294

문제:

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력:

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이방법:

0으로 초기화 된 DP 배열을 미로의 값에 따라 초기화 하면서 진행하면 된다.

이 문제의 예제를 통해서 설명한다. 처음에는 다음과 같이 초기화 된다.

numbers[0]의 값은 1이므로 dp[1]의 값을 업데이트한다.

numbers[1]의 값은 2이므로 dp[2]~dp[3]의 값을 업데이트한다.

numbers[2]의 값은 0이므로 넘어가고, numbers[5]까지 반복하면 아래와 같이 된다.

 만약 이미 dp[i+j]에 0이 아닌 다른 값이 초기화되어 있다면, dp[i+j]값과 dp[i]+1값 중 작은 값을 사용하도록 한다. 끝까지 진행하면 다음과 같이 된다.

 위 작업을 모두 반복했을 때, 맨 마지막 값이 0이 아닌 다른 값으로 바뀌었다면, 끝에 도달할 수 있는 것이므로 해당 값을 출력하면 되고, 아니라면 -1을 출력하도록 한다. 그리고 생각해야 하는 예외가 두가지가 있다.

 첫번째는 5 (0,0,0,1,0)과 같은 경우가 있다. 이런 경우는 if dp[i]==0 and i!=0 와 같은 조건문을 넣어서 해결해준다. 정상적으로 진행될 때, dp에 0 값은 dp[0]을 제외하고 생기면 안되기 때문이다.

 두번째는 1 (0) 이다. 이 경우에는 시작과 동시에 오른쪽 끝으로 도달한 경우이기 때문에, 마지막 출력하는 단계에서 예외처리로 0을 출력하도록 한다.

문제:

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다.

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

입력:

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

출력:

얻을 수 있는 최종 점수의 최댓값을 출력한다.

풀이방법:

 DP를 사용해서 풀어야 하는 문제다. 처음에는 재귀로 이 문제를 접근했었는데, 시간초과랑 메모리 초과가 반복적으로 발생해서 반복문을 사용해서 풀게 되었다. 반복문을 사용해서 풀게 될 경우에는 정방향으로 DP를 배치하는 것이 아닌, 역방향으로 DP를 구성해야 한다고 한다. 마치 재귀로 풀이 되던 것들이 반복문으로 풀어져서 풀이 된다고 생각하면 된다.

문제링크:

www.acmicpc.net/problem/10835

문제:

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 조건을 만족하는 수를 출력한다.

풀이방법:

 소수를 판정하는 알고리즘 중 에라토느테네스의 체와 팰린드롬 알고리즘을 함께 사용하는 알고리즘이다. N으로 들어올 수 있는 가장 큰 숫자인 1,000,000에 해당하는 답은 1003001이라는 사실을 사용해서 그 만큼을 sosu 리스트를 초기화했다. (혹은 넉넉하게 큰 길이로 초기화해도 된다.) 이 sosu 리스트를 에라토스테네스의 체를 사용해서 소수만 남겨둔다.

 이후 while 반복문을 통해서 sosu이면서 팰린드롬인 경우에 그 숫자를 출력하고 break를 통해 정지시키면 된다.

문제링크:

www.acmicpc.net/problem/1747

문제:

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력:

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이방법:

 위키피디아에 따르면 이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉 한 변의 양 끝은 빨강과 파랑으로 서로 달라야 한다는 것이다.

 dfs로 정점을 탐색하며, visited에다 색을 기록한다. dfs로 탐색하는 도중에 visited에 서로 다른 색이 들어오게 되면 이분그래프가 아니므로 False를 반환하도록 한다.

문제링크:

www.acmicpc.net/problem/1707