노래부르다

17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 문제 분석 문제에서의 핵심은 안전 거리의 최댓값이다. 결국 한 지점에서 갈 수 있는 상어사이의 최단 거리를 구하고, 이를 비교해야하기에 모든 경우의 수를 구하는 브루트포스 알고리즘을 사용해야 한다! 문제에서 말하는 안전 거리란? - 이곳에서 말하는 안전거리란, (1)상어가 없는 위치에서 각 상어와의 거리를 구하고, (2)그 거리들 중 최솟값을 말한다. 여기서 더욱 중요한 부분은, 2차원 평면에서 한 점을 기준으로 8개의 인접한 모든 방..

문제 분석 봄버맨 문제를 읽고, 마땅한 알고리즘이 떠오르지 않았다. 어떤 알고리즘을 활용하기보다는 문제 자체에서 해결하는 구현에 초점을 맞춘 문제로 판단했다. 이는 3가지의 키워드를 잡고 접근하면 쉽게 해결할 수 있다. 초기 설정 이후, 봄버맨은 1초간 아무것도 하지 않는다. 다음 1초간 폭탄이 없는 곳에 폭탄을 설치한다. 폭탄이 터지는 시간은 3초이며, 폭발위치에 폭탄은 연쇄반응을 하지 않는다. 특히 2, 3번의 동작을 반복하기에 2가지 중 가장 중요한 분석이 있다고 생각할 수 있으나, 필자는 1번이 가장 중요하다고 생각한다. -> 1번을 살펴보면 초기 설정 이후 봄버맨은 계속해서 폭탄을 설치하고, 폭발하고를 반복하게 된다. 이 부분이 문제 전체에서 어색하다고 생각했고, 일정 규칙을 만들기 위한 조건이..

4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 분석 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 각 구간을 3등분으로 하여 가운데 구간을 반복적으로 제외하는 방식이다. 이를 토대로 칸토어 집합의 근사를 만들고자 하는 문제이다. 문제는 3등분으로 나눈 구간을 각 1, 2, 3이라 할 때, 1. 2의 구간을 공백으로 둔다. 2. 후에 1, 3 구간을 다시 각 3등분으로 나누며 위 과정을 반복한다. = 재귀를 사용함. 3. 모든 선의 길이가 1이면 멈춘다. = 선이 이어진 상태는 존재하지 않는다...

1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 분석 문제는 N x N 행렬을 보고, 3종류(-1, 0, 1)의 종이가 각각의 개수를 구하는 문제이다. 여기서 2개의 규칙을 반복하는데, 문제의 해석을 이러하다. 1. 만약 종이가 모두 같은 수로 되어있다면 이 종이를 그대로 사용한다. 2. 1번이 아닌 경우, 종이를 같은 크기의 종이 9개로 자르고, 각 잘린 종이에 대해 1번의 과정을 반복한다. -> 처음 주어진 예제의 종이가 1장이고, 이것이 3개의 수(-1, 0, 1) 중 하나로 이루어져 있..

11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 분석 문제는 입력받는 숫자 중 절댓값이 가장 작은 숫자를, 만약 절댓값이 같다면 수가 가장 작은 수를 기준으로 정렬시키려 한다. 그리고 0을 입력받았을 때, 위의 조건에서 가장 앞에 정렬된 숫자를 출력하고 삭제한다. 결국 배열을 정렬시키는 정렬방식이 가장 핵심이라고 할 수 있다. 문제 풀이 첫 접근은 swap함수를 이용한 정렬이었다. 입력받은 숫자를 하나의 배열에 집어넣고, 집어넣은 숫자와 옆숫자와 서로의 절댓값을 비교하도록 했다. 위 ..

슬라이딩 윈도우(Sliding Window)란? 슬라이딩 윈도우란, 2개의 양 끝점을 가지고, 각 끝점의 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘 입니다.예를 들어, 설명해드리겠습니다. 1 ~ 7 까지의 배열에서 4개의 연속된 숫자의 합을 계산하는 문제입니다.1 2 3 4 5 6 71 2 3 4 5 6 71 2 3 4 5 6 71 2 3 4 5 6 7이처럼 고정된 크기의 범위를 유지한 채 문제를 해결하는 모습을 볼 수 있습니다.start point(시작점)과 end point(끝점)이 함께 움직이는 모습이 특징입니다!슬라이딩 윈도우 vs 투 포인터 투 포인터(two pointer)과 유사한 점이 많은 알고리즘인데, 두 알고리즘 모두 시작점과 끝점이 있고(+ 양 점을 서로 갱신함), 이 범위를..

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제분석 문제 자체는 매우 간단한 모습을 볼 수 있다. N개의 수가 주어지고, L이라는 숫자가 주어진다. 이 떄 D(i) = N개의 수에서 i - L + 1번째부터 i번째 사이의 최솟값을 말한다. 원소의 index가 i> N >> L; vector vec(N + 1); deque window; // 슬라이딩 윈도우 for (int i = 1; i > vec[i]; } for (int i = 1;..

투 포인터(two pointer)란?- 투 포인터란, 배열에서 필요한 목표에 도달하기 위해, 두 개의 점을 순차적으로 이동하면서 목표에 도달하는지 확인하는 알고리즘입니다. 여기서 포인트는 바로 두 개의 점! 투 포인터라는 알고리즘의 이름을 갖게 한 핵심 원리입니다. 12345                 start                                                                      end 위에서 보시는 것처럼, start와 end가 바로 투 포인터의 핵심 역할을 진행합니다. 현재는 start가 1, end가 3을 가리키는데 특정 조건을 걸어서 조건을 이행하며, start와 end를 이동시켜 원하는 값을 구하도록 합니다.  ??? : "투 포인터보다,..

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제분석 N개의 배열 중, 어떤 숫자를 n이라 할 때, 다른 수 '두' 개의 합으로 나타낼 수 있는 '좋은' 수의 개수를 찾는 문제이다. 문제를 보면 두 수의 합이 n과 같은 경우의 수만 찾으면 된다고 생각하지만... 중요한 포인트는 2개이다. 1. 배열의 원소는 중복될 수 있다. 그리고 수의 위치가 다르면 값이 같아도 다른 수이다. 2. '두' 개의 합으로 목표의 숫자를 만들어야 한다. 1. 배열의 원소 중복 예를 들어서, [1 2 3 3 3 4 5]의 배열이 있다고 가정하자. 첫번째 3..

1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 분석 N개의 갑옷 재료 중, 두개의 조합으로 M을 만드는 문제이다. 투 포인터를 사용하여, 원소 두 개의 조합이 목표로 하는 숫자가 되는가를 확인하면 되는 문제이다. 문제 풀이를 총 2가지를 가져왔다. 투포인터를 이용한 풀이와 그렇지 않은 풀이이다. 투 포인터에 대해 알고싶다면 아래 링크로 공부해보자. [Algorithm] 투 포인터(two pointer) 완.전.정.복 투 포인터(two pointer)란? - 투 포인터란, 배열에..