YANGORITHM

문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최 www.acmicpc.net 풀이 다리를 큐로 생각을 하고 트럭이 다리에 올라가는 것을 큐에 값을 넣는 것으로 생각을 한다. 큐에 넣을 수 있는 최대 수는 w가..

문제 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. www.acmicpc.net 풀이 2차원 배열을 이용해 '*' 과 ' ' 정보를 저장을 하고 출력을 했다. 3*3 에서 9개를 기준으로 다음과 같이 재귀문을 ..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이 문제에 나와있는 조건을 순서대로 구현하면 되는 문제이다. 청소할 공간이 있으면 이동하고 이동한 장소에서 다시 청소할 공..

문제 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 ..