Algorithm

[1780] 종이의 개수 - Python

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

[1629] 곱셈 - Python

/* 문제 */ 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 분할 정복 문제다. 어떤 수의 거듭제곱을 단순히 모두 곱해서 구한다면 시간 복잡도는 O(n)이지만 분할 정복을 이용해 구하면 O(log n)으로 해결할 수 있다. a의 b제곱은 b가 짝수일 경우 a^b = a^(b/2) * a^(b/2) b가 홀수일 경우 a^b = a^((b-1)/2) * a^((b-1)/2) * a 로 나타낼 수 있다. 따라서 재귀를 이용해 b가 1이 될 때까지 문제를 쪼개서 풀도록 구현했다. 또한 이 문제는 단순히 거듭제곱을 구하는 것이 아니라 나머지를 구하는 문제다. a = cx + y (a를 c로 나눈 나머지는 y) 라고 한다면..

[1707] 이분 그래프 - Python

/* 문제 */ 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 그래프 탐색 문제다. 이분 그래프를 처음 들어봐서 찾아봤다. 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 2색변 이분 그래프의 예 그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점 ko.wikipedia.org 노드들을 차례로 탐색하며 이전 노드와 다른 색으로 칠..

[2805] 나무 자르기 - Python

/* 문제 */ 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 ..

[1992] 쿼드트리 - Python

/* 문제 */ 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, ..

[2630] 색종이 만들기 - Python

/* 문제 */ 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑..

[1654] 랜선 자르기 - Python

/* 문제 */ 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이..

이진 탐색

특정 값을 찾기 위해 앞에서부터 모든 값을 확인하는 순차 탐색과 달리, 이진 탐색은 탐색 범위를 절반씩 좁혀가며 탐색하는 빠른 알고리즘이다. 순차 탐색의 시간 복잡도는 O(N)이고 이진 탐색의 시간 복잡도는 O(logN)이다. 이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있다. 탐색할 범위의 시작점, 끝점, 중간점을 설정하고, 찾으려는 값과 중간값을 비교하여 시작점, 끝점, 중간점을 업데이트하는 과정을 반복한다. 반복되는 과정은 재귀함수나 반복문을 통해 구현할 수 있다. # 재귀 함수 사용 def binary_search(array, target, start, end): if start > end: return None# None: 파이썬의 Null mid = (start + end) // 2 if..