YANGORITHM

문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 www.acmicpc.net 풀이 스택을 이용하여 해결할 수 있는 문제다. 스택에는 배열의 인덱스를 저장한다. 배열의 값이 증가하는 경우면..

문제 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 풀이 하노이 탑의 이동 순서를 구현하는 문제이다. 하노이 탑 알고리즘은 다음과 같다. 1. a b c 막대가 있고 ..

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 풀이 0부터 백만까지 이동 가능한 모든 채널을 선택하고, 선택한 채널에서 N번으로 이동했을 때의 값들 중 최소를 구하면 된다. 백만까지 반복하는 이유는, 예를 들어 N=500000이고 사용할 수 있는 버튼이 6만 있을 경우 666666으로 이동한 후 50만까지 -를 누르면 된다. 이처럼 이동하고 싶은 채널 N은 50만이..

문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 풀이 N * N 배열 안에 모든 수를 검사한다. 검사 시작점은 왼쪽 위를 기준으로 한다. 만약 모든 수가 같지 않으면 배열을 9..

문제 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 풀이 a행렬과 b행렬을 만들어서 a행렬의 각 요소를 b행렬과 비교한다. 만약 다를 경우, 그 위치에서 3x3만큼 a행렬의 값들을 뒤집어주면된다. 마지막으로 뒤집은 후 b 행렬과 비교해서 같은지 다른지 확인하면 된다. 행렬을 뒤집어주는 연산은 a행렬의 특정 위치 이후로 3x3의 부분행렬이 존재해야 하므로 a행렬의 모든 값에 대해 비교를 진행할 수 없다. 행 방향으로 N-2번 가능하고, 열 방향으로 M-2번 ..

문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 버블 정렬의 과정이 총 몇 단계로 이루어지는지 구하는 문제이다. 버블 정렬이 진행되는 과정을 통해 문제를 해결할 수 있다. 문제에 10 1 5 2 3 이 주어졌는데 i = 1 일 때 버블 정렬의 진행 과정을 보면 1 10 5 2 3, 1 5 10 2 3, 1 5 2 10 3, 1 5 2 3 10 순서로 된다. 10이 맨 뒤로 가게 된다. i = 2 일 때 진행 과..

문제 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net 풀이 브루트포스로 해결하면 시간초과가 발생한다. 먼저 x를 맞춰주고 그 후에 y를 찾아줘야 한다. 1. x는 M만큼 증가를 한다. 따라서 x = x ..

문제 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 높이에 따라 세 가지 경우로 나누어서 풀어야 한다. 1. 높이가 1인 경우 나이트는 이동할 수 없다. 2. 높이가 2인 경우 위로1칸 오른쪽 2칸, 밑으로 1칸 오른쪽 2칸 으로만 이동할 수 있다. 3. 높이가 3 이상인 경우 가로 길이가 7을 기준으로 나누면 된다. 높이가 2인 경우 이동가능한 방법으로 이동할 수 있는 최대 이동 횟수는 3번이다. 이동 횟수 4번 부터는 4가지 이동 방법을 모두 사용해야 하므로 3번까지만 이동할 수 있다. 높이가 3이..

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 d[k][n]을 k개를 이용해 n을 만든다고 가정한다. k개의 원 ○ + ○ + ○ + ... + ● = N 이라고 한다. ●에 올 수 있는 수 i는 0부터 N까지이다. 그러면 다음과 같은 점화식을 만들 수 있다. d[k][n] = d[k-1][n-i] (i = 0~n) 이 점화식을 이용해 문제를 해결한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include using namespace s..

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으 www.acmicpc.net 풀이 (1,1)에서 (N,M)까지 이동해야 하는 문제이고 이동가능한 방향은 오른쪽, 아래, 오른쪽 대각선 아래 방향 세 가지 경..