문제 링크 1. 아이디어 님블 게임은 1×N 직사각형 보드가 있고 보드는 1×1 크기의 정사각형으로 이루어져 있으며 가장 왼쪽 정사각형이 0번, 그 오른쪽 정사각형은 1번, …, 가장 오른쪽 정사각형은 N-1번이다. 각 정사각형에는 한 개 이상의 동전이 놓여 있을 수 있으며 각 플레이어는 자신의 차례에 하나의 동전을 선택해서 왼쪽으로 한 칸...

문제 링크 1. 아이디어 전형적인 님 게임 문제로 각 돌 더미의 돌의 개수를 전부 XOR한 Nim-Sum이 0이 아니면 항상 0으로 만들 수 있는 선공이 이기며, 0이면 항상 0이 아닌 선택을 할 수 밖에 없어서 후공이 이긴다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*;...

문제 링크 1. 아이디어 전형적인 Misere 님 게임 문제로 크기가 2 이상인 돌 더미가 하나라도 존재하는 경우 님 게임과 동일하게 승리할 수 있다. 반면 모든 돌 더미의 크기가 1인 경우는 기존 님 게임과 반대로 돌 더미의 수가 짝수 개여야 상대방이 마지막 돌을 가져갈 수 밖에 없다. 2. 코드 1. 풀이 [Java] imp...

문제 링크 1. 아이디어 단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 짓는 것이 괄호의 쌍을 맞추는 것과 동일하다. 스택 자료구조를 활용해서 괄호 쌍 맞추기를 하듯이 해주면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { ...

문제 링크 1. 아이디어 올바른 괄호열인지 여부와 올바른 괄호열이면 괄호값을 출력해야 하는 문제로 괄호 문제다 보니 스택을 사용하면 되며 덧셈과 곱셈의 분배 법칙을 활용해서 해결했다. 산술에서 $(A + B) \times C = A \times C + B \times C$ 로 곱셈을 분배해줄 수 있는데, 이를 올바른 괄호열 계산에도 동일하...

문제 링크 1. 아이디어 프랙탈 형태로 별을 출력하는 문제로 반복되는 구조는 아래와 같다. 높이 3인 삼각형이 반복 구조의 최소 단위이므로 이때까지 재귀를 들어가다가 방문 체크 배열에 별을 마킹해주면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; public class Main { ...

문제 링크 1. 아이디어 프랙탈 형태로 별을 출력하는 문제로 반복되는 구조를 보면 현재 바라보는 영역을 가로, 세로 각각 3등분해서 9개의 작은 정사각형을 만들었을 때 정가운데 정사각형은 비우고 나머지에 대해 같은 행위를 반복하는 것을 볼 수 있다. 방문 체크 배열과 재귀를 활용해서 이를 재귀적으로 탐색하며 크기 1의 정사각형이 될 때까지 ...

문제 링크 1. 아이디어 철학자의 산책로 상에서 철학자의 위치를 구하는 문제로 산책로는 힐베르트 곡선의 모양을 하고 있다. 비슷한 구조가 반복되는 것 같다는 점에서 분할 정복을 활용해서 해결했는데 크기별 산책로는 아래와 같은 관계를 보이고 있다. 0번 영역의 산책로는 $W_i$ 산책로에서 $y = x$ 에 대칭한 형태이며, 1번, 2번...

문제 링크 1. 아이디어 레이저가 절단한 후 조각의 총 개수를 구해야 하는 문제로 스택 자료구조를 활용하면 해결할 수 있다. 레이저는 현재 레이저보다 먼저 등장했으면서 아직 끝이 안나온 막대를 자르며 잘랐을 때 생기는 새로운 조각은 막대의 수와 동일하다. 막대의 경우 자신보다 긴 막대만 위에 놓일 수 있으므로 최근에 넣은 막대가 먼저 빠지게...

문제 링크 1. 아이디어 각 빌딩에서 오른쪽에 위치한 빌딩만 볼 수 있을 때 자신보다 높이가 낮은 빌딩의 개수를 각각 찾는 문제다. 빌딩의 수가 최대 80,000개여서 O(N²)의 시간 복잡도로는 해결할 수 없는데 스택 자료구조를 활용하면 해결할 수 있다. 스택은 왼쪽에서 오른쪽 순서로 빌딩을 담는다. 현재 빌딩에 대해 왼쪽에 위치한 빌딩...