코딩스토리

백준 12852번 - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이 문제는 BFS, 다이나믹 프로그래밍 문제이다. 처음에는 top-down 방식으로 문제를 해결하려 했다. 문제의 조건에 맞게 코드를 짜 보았는데 마지막 출력에서 살짝 맘에 안 들었다. 출력 부분을 보면 n부터 내림차순으로 출력하는데, top-down 방식으로 해결하려면 dp[x]에는 x*3 또는 x*2 또는 x+1 이 들어가 있기 때문에 한번 vector나 배열에 다 넣고 오름차순 정렬을 해줘야 한다. 코드는 몇 줄 차이 안 나겠지만 시간 복잡도 면에서 botto..

백준 2206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 이 문제는 BFS(너비 우선 탐색) 문제이다. 해결 방법은 3차원 배열을 사용하는 것이다. 보통의 쉬운 수준의 BFS 문제들과 달리 '벽'이라는 장애물이 존재한다. 즉 벽을 부순 횟수를 기억해야 하는데 모든 위치에서 기억해야 하므로 3차원 배열을 사용해야 한다. 다행이 벽을 부술 수 있는 횟수가 1번 이므로 3차원 배열의 크기는 ..

백준 11000번 - 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 이 문제는 우선순위 큐를 사용한 문제이다. 처음 문제를 풀 때 실수했던 점은 입력을 받을 때 정렬되서 들어온다고 생각한 것이였다. (사실 생각한게 아니고 아무 생각없이 그냥 알고리즘만 생각해서 풀었따ㅎ) 그래서 한번 입력받을 때마다 우선순위 큐의 top과 비교해서 정답을 도출했는데 당연히 틀렸다. 고민하다가 생각난 풀이법이 우선순위 큐(Priority queue)를 두 개 사용하는 방법이다! 첫 번째 큐에는 모..

백준 17144번 - 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 문제의 정답률이 높길래 쉬울 거라 생각했는데 생각보다 오래 걸렸다. 문제를 풀면서 가장 기억에 남는 실수 두 가지는 1. 확산은 동시에 된다. 2. 바람이 부는 것을 구현할 때 끝에서부터? 시작해야 한다. 쉽게 말하면 아래의 코드는 왼쪽에서 오른쪽으로 바람이 부는 코드인데, 왼쪽부터 시작하지 않고 오른쪽 끝부터 시작한다. 1 ..

백준 16235번 - 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 이 문제는 구현 문제인 것 같다. 처음에 문제를 읽고, 봄, 여름, 가을, 겨울을 각각 함수로 만들고 deque와 tuple을 사용해 코드를 짜 보았는데 당연히 시간초과.. 이유는 아마 deque를 사용하고 체크하는 과정에서 tuple을 사용하면 deque의 장점인 인덱스 접근의 의미가 사라진다. (tuple은 index로 접근이 불가.. tie ..

백준 16236번 - 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 아기 상어 문제는 bfs알고리즘으로 해결하였다. 처음에는 전형적인 bfs문제라 생각하고 문제의 조건 중 가장 가까운 거리에 있는 물고기가 많은 경우의 조건을 잘못 생각해서 bfs를 북 서 동 남 순서대로 돌리면 알아서 조건을 만족할 거라 생각했다. 예제를 돌려보다 이런 방식은 오류가 난다는 것을 알 수 있었다. vector에 pair로 저장해서 가장 가까..

백준 14503번 - 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 처음 문제를 봤을 때 "왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다." 이 문장을 보고 해당 칸의 왼쪽 방향에 있는 모든 칸들을 확인해야 하는 문제로 착각했다. (솔직히 문제가 오해의 소지가 있게 보이긴 했음ㅠ) 그렇게 해서 함수로 전부 확인하고 예제를 돌려보니 ..

백준 1753번 - 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 최단경로 문제는 시간 복잡도가 1초이고 정점의 개수가 20000개, 간선의 개수가 300000개 이므로 단순한 그래프 문제 푸는 방식으로 풀게 되면 시간 초과가 나게 된다. 참고로 다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV)이다. 다익스트라 알고리즘을 간단히 복습해 보자. 먼저 다익스트라 알고리즘의 특징은 간선의 가중치가 모두 ..