Python

Heap

Heap-hop 나는 힙스터다. 힙(heap)은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안되었다. 힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리다(최소 힙의 경우). 위의 그림과 같이 힙에는 두 가지 종류가 있다. 최소 힙: 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음 최대 힙: 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음 따라서 항상 루트 노드(heap[0])가 최솟값 또는 최댓값이다. 이 특성을 이용해 우선순위 큐와 같은 추상적인 자료형을 구현할 수 있다. 또한 형제 노드간에는 대소 관계가 정해지지 않는다. 힙을 직접 구현할 수도 있지만 파이썬에는 최소 힙 알고리즘을 제공하는 heapq 모듈이 있다. heapq 모듈은 리..

[13913] 숨바꼭질 4 - Python

/* 문제 */ 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾을 수 있는 가장 빠른 시간과 이동 순서를 출력하는 문제다. 최단거리 문제이므로 bfs로 풀었다. 처음에는 이동 순서를 저장하기 위해 visited 딕셔너리를 선언해 각 위치에 도달하기 위한 이동 순서를 ..

[12852] 1로 만들기 2 - Python

/* 문제 */ 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. dp 문제지만 이번에는 최소 연산 횟수 뿐만 아니라 그 연산에 포함된 수까지 출력해야 한다. # 정답 코드 n = int(input()) dp = {} # key: 숫자, value: 그 과정의 수 리스트 dp[1] = [1] dp[2] = [1, 2] for i in range(3, n+1): tem = [dp[i-1][:]] if i%3 == 0: tem.append(dp[i/..

[1525] 퍼즐 - Python

/* 문제 */ 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자. 가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오. 최소의 이동으로 퍼즐을 정리해야 한다는 점, 숫자 블록을 상하좌우로 움직일 수 있다는 점에서 그래프 문제와 비슷하다고 생각했지만 풀이법을 한 번에 떠올리기는 쉽지 않았다. 예전 문제에서 풀었던 대로 표를 2차원 리..

[2295] 세 수의 합 - Python

/* 문제 */ N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라. 예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다. 풀이 방법 자체는 간단하게 떠올릴 수 있지만 시간 제한이 있기 때문에 효율적으로 푸는 방법을 고민해야 한다. 처음에는 itertools를 이용해 리스트에서 세 수를 뽑은 후 더해 그 합이 리스트에 포함되는지를 확인했다. 불필요한 계산을 줄이기 위해 세 수를 뽑을 때..

[1043] 거짓말 - Python

/* 문제 */ 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 사람의 수 N이 주어진다...

[1309] 동물원 - Python

/* 문제 */ 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. dp 문제다. 앞 칸에 사자가 왼쪽에 있는지, 오른쪽에 있는지, 한 마리도 없는지에 따라 다음 칸에 사자를 배치할 수 있는 경우의 수가 달라진다. 처음에는 [[1,1,1], [2,3,2] ... ]와 같은 dp 리스트를 만들어 각..

[1780] 종이의 개수 - Python

/* 문제 */ N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. 2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 종이를 4등분하던 앞의 분할정복 문제들과 같은 문제다. 다른 점은 이번에는 종이를 9등분 한다는 것인데 재귀 호출을 9번 작성해야 해서 귀찮긴 했지만 풀이에 어려움은 없..