🔗문제 보러가기 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 👨‍💻풀이 과정 처음에 문제를 보고 별 생각없이 배열 선언하고 분할 정복을 했다가 메모리 초과. (\( 2^{15} \times 2^{15} \)) 배열 없이 카운팅 변수 하나로만 아무 생각없이 셌다가 시간 초과. (하나씩 돌면서 점검하면 결국 \(\mathrm{O( 2^{15} \times 2^{15})}\)) 그래서 4등분을 하고, 찾고자 하는 (행, 열)이 해당 칸에 없는 경우에는 사각형 개수만큼 더해 주었습니다. 만약 찾고자 하는..

🔗문제 보러가기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 🧑‍💻풀이 과정 얼마 전에 다익스트라 알고리즘(Dijkstra Algorithm)을 공부했었으니, 머릿 속에서 인출하는 연습을 위해 비슷한 유형의 문제를 하나 풀어봤습니다. 우리 말이 어려운 건지, 제가 멍청한 건지 모르겠지만 매번 헷갈리는 것 같아요... 그래서 연습장에 그림 그려가며 풉니다. ( "distances[v] vs distances[u] + nextCost" 👉🏻 이게 젤 헷갈립니다. ) 알고리즘은..

🔗문제 보러가기 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 🧑‍💻풀이 과정 DFS + 백트래킹으로 풀 수 있는 문제입니다. 처음에는 같은 문자 방문 여부를 위해 set을 이용했는데, 시간 초과가 나더라구요. 그래서 시간을 줄이기 위해 다른 방법을 생각했는데, 알파벳은 26개가 있고 각각 한 번씩만 방문할 수 있으니, vector Alphabet(26, false) 배열을 통해 방문 여부를 관리하니 통과가 되었습니다. \(\mathrm{O(1)} \) 과 \( \mathrm{O(log \ N)..

🔗문제 보러가기 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 🧑‍💻풀이 과정 연구소의 크기가 최대 \(8 \times 8\) 이기 때문에 벽을 3개 설치하는 모든 경우의 수에 대해 탐색하여 풀었습니다. 백트래킹과 BFS 탐색을 잘 구현하는 것이 목표인 문제인 것 같네요. 2차원 배열에 연구소 정보를 입력 받고, 바이러스의 위치 정보도 별도의 배열에 저장한다. 조합(Combination) 방식을 이용해 열 방향 순서로 벽 3개를 설치한다. 빈 공간일 때에만 벽을 설치한다. 벽을 3개 설치 다 했다면, 3번 과정을 진행 후..

🔗문제 보러가기 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 👨‍💻풀이 과정 BFS + DFS + 최소 신장 트리(MST) 알고리즘을 구현해야 풀 수 있는, 대단히 체력적으로 힘든 문제였습니다. 그래도 문제에서 주어진 조건들이 까다롭진 않아, 구현만 제대로 한다면 통과는 쉽게 되네요. 제가 푼 과정은 다음과 같습니다. 주어진 입력을 2차원 배열에 저장하되, 땅(1)은 1이 아니라 엄청 큰 다른 숫자(1억)로 대신 채워줍니다. BFS 알고리즘을 통해, 각 섬의 번호를 해당 섬의 영역에 채..

🔗문제 보러가기 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🧑‍💻 풀이 과정 최단 경로 알고리즘을 연습 중에 있어, 저는 다익스트라 알고리즘으로 풀었습니다. (비용에 음수가 없기 때문) 시작 위치는 N, 도착 위치는 K로 주어집니다. N에서 i번째 노드로 가는 데에 드는 최소 시간을 저장하는 배열, times를 선언합니다. 범위가 0 ~ 100,000이니, 이 범위를 포함할 수 있는 만큼의 크기로 선언 후, 무한대 값으로 초기화합니다. times[N] = 0 으로 초기..