이 포스트는 백준 사이트의 스마트 택시 문제 풀이입니다. 문제 해결 과정 이 문제는 손님에게 방문하고 목적지까지 최단경로로 이동하는 것을 M번 반복하는 문제입니다. 이때, 현재 연료가 0이면 ‘-1’을 출력해야 하므로 중요한 것은 이동거리에 따른 연료의 소비입니다. 이 문제에서 사용할 최단 거리 알고리즘 후보와 가능 여부는 다음과 같습...

deque은 vector처럼 랜덤 액세스가 가능하고 list처럼 양방향 push, pop이 가능한 자료구조로 double ended queue의 약자입니다. 이번 포스트에서는 deque의 특징과 멤버 함수에 대해 알아보겠습니다. Deque 메모리 공간 확보 방법 deque은 벡터처럼 랜덤 액세스가 가능해 닮아보이지만, 원소 추가에 대한 메모리...

이 포스트는 백준 사이트의 사다리 조작 문제 풀이입니다. 문제 해결 과정 이 문제는 주어진 상황에서 N개의 사다리가 시작 번호와 도착 번호가 동일하도록 만들기 위한 최소의 사다리 추가 수를 구하는 문제입니다. 따라서 이 문제에서는 2가지 과정이 필요합니다. 현재 상태에서 N개가 각자 동일한 번호(시작 번호 = 도착 번호)인지 확...

이 포스트는 백준 사이트의 백조의 호수 문제 풀이입니다. 문제 해결 과정 이 문제에서 결과를 출력하기 위해서는 3가지 행동을 반복해서 진행해야 합니다. 두 마리의 백조가 만날 수 있는지 확인 물에 인접한 얼음 녹이기 출력할 날짜 증가 1번 과정의 경우, 탐색 알고리즘(BFS, DFS, … etc)를 사용하여 풀 수 있고...

이 포스트는 백준 사이트의 RGB거리 문제 풀이입니다. 문제 해결 과정 문제를 작은 문제들로 나누어 풀 수 있는 문제로 DP(다이나믹 프로그래밍)를 활용하여 해결하였습니다. 문제에서 주어진 3가지 조건을 지키며 집을 칠하는 최소 비용을 구해야하므로 먼저, 점화식을 찾고자 하였습니다. 문제의 3가지 조건이 말하는 의미는 결국 이웃한 집끼...

이 포스트는 백준 사이트의 나무 재테크 문제 풀이입니다. 문제 해결 과정 처음 이 문제를 접하였을 때, 우선순위 큐(priority_queue)를 활용해서 풀어보가자 하였습니다. C++에서 우선순위 큐는 최대힙을 사용하기 때문에 상수시간으로 최댓값에 접근할 수 있습니다. 그러나 최대힙은 균형이진트리 이기 때문에 삽입과 삭제가 빈번하게 ...

이 포스트는 백준 사이트의 연구소 3 문제 풀이입니다. 문제 해결 과정 이 문제는 조합과 탐색 을 반복적으로 수행하여 해결할 수 있습니다. 문제의 설명처럼 바이러스의 개수는 1개 이상이고 10개 이하인 개수로 지형에 존재하고 그 중 승원이가 M 개를 활성화 시켰을 때, 지형 전체에 바이러스가 전파되는 최소시간을 구하고자 합니다. 따라...

이 포스트는 백준 사이트의 인구 이동 문제 풀이입니다. 문제 해결 과정 이 문제는 지도의 원본과 새로운 지도를 나눠 탐색을 해야하는 문제입니다. 문제에서 설명한 인구 이동은 1일 동안 이뤄지며, 더 이상 인구 이동이 없을 때 까지 반복됩니다. 하루동안 이뤄지는 과정은 아래와 같습니다. 국경을 공유(동서남북으로 접한 국가)하는 두...

이 포스트는 백준 사이트의 감시 문제 풀이입니다. 문제 해결 과정 이 문제에서 핵심은 CCTV 회전과 그에 따른 사각지대 개수입니다. 이 문제를 해결하고자 먼저 CCTV 의 방향을 어떻게 구현할지 고민 중 기존에 사용하는 방법인 dir_row, dir_col 배열을 활용해보기로 했습니다. 5가지의 CCTV 는 각각 4가지 방향 중 최...

이 포스트는 백준 사이트의 원판 돌리기 문제 풀이입니다. 문제 해결 과정 원판 돌리기 문제는 이전 풀었던 톱니바퀴 문제와 유사한 원리로 풀 수 있습니다. 그러나 톱니바퀴 문제에서는 12시 방향에 있는 원소만 파악하면 풀 수 있었지만 이번 문제는 모든 원소에 접근이 가능하고 회전도 가능해야 합니다. 그래서 이번 문제의 자료구조는 랜덤 액...