코딩스토리

백준 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)이다. 다익스트라 알고리즘을 간단히 복습해 보자. 먼저 다익스트라 알고리즘의 특징은 간선의 가중치가 모두 ..