CodeDrive

문제:

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력:

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이방법:

 nodes라는 이중배열을 사용해서 입력으로 주어지는 연결된 두 정점 사이의 관계를 기록한다. 그리고 항상 트리의 루트는 1이라고 정해졌기 때문에, 1부터 dfs를 사용해서 노드들을 탐색하면서 parent를 기록한다.

문제링크:

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

문제:

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

입력:

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다. 

출력:

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

풀이방법:

문자열 알고리즘 중 효율성이 가장 좋은 트라이(Trie) 알고리즘을 사용해서 입력받는 문자열을 정리하고, 별도의 탐색없이 지정된 출력형식으로 출력하면 되기 때문에, 재귀를 사용해서 문제에서 요구하는 방식대로 출력하도록 한다.

class Node(object):
    def __init__(self,name,flag=False):
        self.parent = name
        self.terminate = flag
        self.child = {}
        
    def __str__(self):
        return self.parent
        
class Trie(object):
    @classmethod
    def __init__(self):
        self.root = Node(None)
        
    @classmethod
    def insert(self, food):
        currNode = self.root
        for f in food:
            if f not in currNode.child:
                currNode.child[f] = Node(f)
            currNode.terminate = False
            currNode = currNode.child[f]
        currNode.terminate = True
        
    @staticmethod
    def antPrint(curNode,count):
        currList = sorted(list(curNode.child))
        for curr in currList:
            print("-"*count*2,end='')
            print(curNode.child[curr])
            Trie.antPrint(curNode.child[curr],count+1)

n = int(input())
T = Trie()
for _ in range(n):
    list_ = input().split()
    m, foods = list_[0], list_[1:]
    Trie.insert(foods)
Trie.antPrint(Trie.root,0)

문제링크:

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

문제:

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력:

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

풀이방법:

 각 학생들이 작성한 예상 등수를 바탕으로 정렬을 하고, 그와 동일하게 순위를 부여하는 것이 가장 사람들의 불만도를 최소로 하는 방법이다.

문제링크:

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

문제:

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력:

이 문제는 입력이 없다.

출력:

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이방법:

 조건이 맞는 a,b,c,d를 찾는 것은 쉬우나 시간을 줄이는 것이 이 문제의 핵심이다. a 같은 경우에는 6이 가장 같은 경우의 수 이기 때문에 6부터 시작하게 한다. 그리고 1보다 큰 자연수여야 하기 때문에 b는 2부터, b<c<d를 만족해야하기 때문에 c는 b부터, d는 c부터 시작하게 하도록 한다.

문제링크:

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

문제:

유진이가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.

이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.

예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다

랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다. 그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 송유진의 새로운 점수가 주어진다. 이때, 송유진의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그램을 작성하시오. 만약 점수가 랭킹 리스트에 올라갈 수 없을 정도로 낮다면 -1을 출력한다.

만약, 랭킹 리스트가 꽉 차있을 때, 새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다. (예제 2)

입력:

첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보다 작거나 같은 자연수 또는 0이다. 둘째 줄에는 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다. 둘째 줄은 N이 0보다 큰 경우에만 주어진다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 기존에 있던 중복된 숫자가 있을 수 있는데, 이를 새로 들어오는 숫자와 구분을 할 수 있어야 하는 문제다. 이를 구분하기 위해서 기존에 있던 숫자들에게 인덱스를 부여했으며, 새로 들어오는 숫자는 가장 큰 인덱스를 가지도록 하게 한다. 이렇게 하면 새로 들어오는 숫자가 기존에 있던 점수와 동일한 것이 있으면 그 뒤에 배치되게 된다.

 새로 정렬을 마친 뒤에 앞에서부터 P개 자르고, (새로 들어온 숫자, 인덱스)가 그 배열에 있다면 등수를 찾아 출력을 하고, 그렇지 않다면 -1을 출력하게 한다.

 또한 N이 0일 경우도 존재하게 되는데, 이 때는 두번째 줄을 입력받지 않아야 한다. 따라서 따로 예외처리를 해주어 빈 리스트를 정의하게 하도록 한다.

문제링크:

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

문제:

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력:

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력:

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

풀이방법:

 자두가 움직일 수 있는 횟수는 W로 초는 T로 고정되어 있기 때문에 열은 W이고, 행은 T인 DP 테이블을 만들어서 이 문제를 해결하도록 한다.

 계속해서 움직이지 않는 경우는 1에서만 점수가 오르기 때문에 1일때만 이전 행의 0열 값을 가져와 1을 더하도록 한다. 1번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 짝수일 때 카운트가 오르게 되고, 2번 나무에서 떨어질 때 먹기 위해서는 바뀐 횟수가 홀수일 때 카운트가 오르게 된다. (1번나무에서 초기에 위치하기 때문)

문제링크:

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

문제:

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력:

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력:

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)

풀이방법:

N명이 있을 때, 발생하는 경우의 수를 점화식으로 구하면 DP[N] = DP[N-1]+DP[N-2]와 같이 구할 수 있다.

그리고 VIP들 같은 경우에는 움직이지 못하기 때문에 주위 사람들과 자리 변경이 불가능하다. 따라서 양 옆을 분할한다라고 생각할 수 있다. 즉 문제에서 소개한 예시로 보면 9개의 자리가 있을 때, 4와 7에서 자리를 분할하고 있다. 이제 이 문제는 DP[3] * DP[2] * DP[2]와 같이 경우의 수를 구하면 된다.

문제링크:

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

문제:

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

풀이방법:

 처음에는 이 문제를 투포인터를 사용하는 방법으로 접근하였다. list의 합이 N과 같으면 길이를 비교하여 저장하도록 하였고, N보다 작으면 리스트의 길이를 늘려주고 N보다 크면 리스트의 길이를 줄여주도록 하였다.

 하지만 이 방법은 N의 크기에 따라 시간이 많이 증가할 수 있다는 단점을 가지고 있었고 결국 시간초과가 발생하게 되었다. 코드는 다음과 같다.

따라서 다른 방법을 생각해보았는데, 이 문제를 수학적으로 접근해보았다. 

우선 길이가 L인 연속된 수들의 합이 N이 되는 수열은 항상 존재한다고 가정한다. 그리고 그 수열의 첫 시작 수를 X라고 할 때, 다음과 같이 식을 표현할 수 있다.

N = X + (X+1) + (X+2) + (X+3) + ... + (X+L-1)

이를 정리하면 다음과 같이 표현할 수 있다.

N = LX + (1+2+3+...+L-1)

   = LX + (L-1)L/2

그럼 X는 다음과 같이 구할 수 있다.

X = N/L - (L-1)/2

따라서 L을 증가 시키면서, 음이 아닌 정수가 되는 X를 찾으면 된다. 그리고 만약 L이 100이 넘어간다면 -1을 문제 조건에 따라 출력하도록 한다.

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

문제:

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

입력:

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력:

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

풀이방법:

1. 우선순위 큐를 사용해서 연료 내에서 움직일 수 있는 주유소에서 주유하도록 한다.

2. 데이터를 전처리할 때, 거리는 작은 순으로 주어지지 않는다. 정렬이 필요하다

3. 마을에 도착하지 못하는 경우는 while에 있지만 더 이상 움직이지 못할 때를 의미한다. (candidates가 비어있는 경우)

문제링크:

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

문제:

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력:

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력:

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

풀이방법:

 가지고 있는 수 K 보다 사용해야 하는 갯수 N이 더 크면 가장 큰 숫자를 여러번 사용하는 것이 큰 수를 만드는데 유리하다. 따라서 가장 큰 수를 찾은 뒤에 N-K개 만큼 배열에 추가적으로 넣어준다.

 큰 수를 만들기 위해서는 두 수를 앞 뒤로 붙여보면 된다. 예를 들어 100 과 9 두 숫자가 있다고 했을 때, 큰 수가 무조건 가장 앞으로 오게 한다면 1009를 생성하게 되지만 실제로 큰 수는 9100가 되어야 한다. 따라서 1009 vs 9100과 같이 두 수를 번갈아 붙여보며 큰 수를 찾는 방법을 사용해야 한다. 

 따라서 python의 sort의 key 기능을 사용하며, 특수한 함수를 기준으로 정렬을 해야 하기 때문에 cmp_to_key를 사용하도록 한다.

문제링크:

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