문제 이해 단계 0과 1로만 이루어진 2개의 서로 다른 2차원 맵이 주어진다. 왼쪽 맵은 0일 때 있는 퍼즐이 있는 것, 오른쪽 맵은 1일 때 퍼즐이 있는 것이다. 왼쪽 맵의 빈칸에 오른쪽 퍼즐을 끼우는데 딱 맞는 퍼즐만 끼울 수 있다. 이때 중요한 것은 퍼즐을 회전해서 끼울 수 있다는 것이다. 이러한 조건일 때 최대한 많은 퍼즐을 끼웠을 때 총퍼즐의 칸 수를 구하는 문제이다. 문제 접근 단계 일단 해당 문제의 유형부터 유추해 보자면 0과 1로만 이루어진 2차원 맵이 주어진 점, 그리고 퍼즐을 알아내야 하는 점을 보면 곧바로 그래프 탐색을 포함한 문제라는 것을 유추할 수 있다. DFS나 DFS 중 하나로 풀면 될 것 같은데 딱히 경로 자체는 그렇게 중요한 점이 아닌 것 같아서, 두 개 중 아무거나 상관없..

문제 이해 단계 알파벳 대문자 3글자로 이루어진 공항(정점)이 존재한다. 그리고 입력으로 티켓(간선) [a, b] 형태로 a->b 로이 단방향 정보로 주어진다. 이때, 모든 항공권을 사용한다는 말은 모든 간선을 사용한다는 말이다. 모든 도시를 방문할 수 없는 경우는 주어지지 않는다는 말은 결국엔 모든 정점을 방문한다는 소리이다. 이때 방문했던 공항 순서대로 출력하도록 하는 게 해당 문제이다. 여기서 한 공항에서 티켓이 여러 개 있다면 사전순(오름차순)으로 더 빠른 것이 우선시된다. 문제 접근 단계 해당 문제는 위에서 말했듯이 공항은 정점이고, 티켓은 두 정점을 잇는 단방향 정보인 간선이다. 그렇기 때문에 해당 문제는 그래프 탐색 문제일 가능성이 높다. 그래서 BFS 또는 DFS로 접근해야 할 것 같은데,..

문제 이해 단계 n개의 섬이 주어지고, 정보로는 각 섬이 이어지는 정보와 그 거리 비용이 주어진다. 이 조건에서 모든 섬을 방문할 수 있도록 선을 이을 때, 돈을 최소한으로 쓰게 하는 문제. 문제 접근 단계 해당 문제는 그림으로만 봐도 알겠지만, 가중치가 주어진 노드 문제이다. "최소한 적은 비용을 골라라" 이 말은 그리디에서 자주 쓰는 말이어서 일단 그리디라고 가정하고 문제를 풀어보겠다. 비용을 최소화하려면 어떻게 해야 유리할까? 1. 비용이 싼 선(다리)을 고른다. 2. 선(다리)을 최대한 적게 쓴다. 2가지 일단 생각난다. 2번 조건이 확실한지 나도 잘 모르겠어서 그림을 여러 번 그려봤다. 왜냐하면 직통으로 가는 다리가 엄청 비싸고, 돌아서 가는 다리가 엄청 싸면 "돌아서 가는 게 더 싼 거 아닌가..

문제 이해 단계 숫자로 이루어진 문자열이 주어지고, 그중에서 없애야 할 문자의 수 k가 주어진다. k개를 지워서 문자열 중 가장 큰 숫자를 만드는 것이다. 여기서 중요한 점은 무조건 k개를 다 써야 한다는 것이다. 문제 접근 단계 상식적으로 한번 접근해 보자. 어떤 문자열(숫자배열)일수록 크다고 할 수 있을까? 당연히 기본적으로 다른 숫자들보다 자릿수가 많으면 비교할 필요도 없이 더 큰 숫자일 것이다. 예를 들어 두 자릿수의 최솟값 (10)은, 한 자릿수의 최댓값(9)보다 무조건 큰 것처럼 말이다. 그럼 비교하는 두 숫자의 자릿수가 같다면? 가장 높은 10의 자리(숫자 배열의 첫 인덱스)가 높은 숫자가 큰 것이다. 예를 들어, "399"와 "400"을 비교하면, 가장 높은 자릿수인 '3'과 '4'만 보고..