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

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

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

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

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

코딩테스트 연습 - 추석 트래픽 문제 바로가기 문제 설명 이 문제의 핵심은 시간이 핵심인 만큼 시간을 변환하는 것이 가장 중요합니다. 문제 반환값이 초당 최대 처리량이므로 문제의 모든 시각을 초로 변환 하여 문제를 풀고자 하였습니다. 그리고 입력 형식의 4번 째 조건에서 처리 시간은 시작시간과 끝시간을 포함 한다고 하였으므로 주어진 끝 ...

이 포스트는 백준 사이트의 톱니바퀴 문제 풀이입니다. 문제 해결 과정 문제에서 구하고자 하는 결과값은 각 톱니바퀴의 12시 방향에 있는 정보만 알면 구할 수 있습니다. 그리고 톱니바퀴의 회전 방향은 시계와 반시계 방향이므로 원 모양의 톱니바퀴를 12시 위치에서 자르고 직선형태로 변형하면 아래와 같은 모양이 될 수 있습니다. 그...

이 포스트는 백준 사이트의 구슬 탈출 2 문제 풀이입니다. 문제 해결 과정 이 문제는 2개의 구슬이 굴러다니며 목표 지점에 빨간색 구슬을 먼저 도착시키는 것이 목표인 문제입니다. 문제의 규칙은 아래와 같습니다. 빨간 색 구슬을 파란 색 구슬보다 먼저 목표지점에 도착해야 한다. 두 구슬은 겹쳐질 수 없다. 지형을 기울여 구슬...

이 포스트는 백준 사이트의 경사로 문제 풀이입니다. 문제 해결 과정 N x N 크기의 지도에 각 칸의 높이가 주어질 때, 지나갈 수 있는 길 의 개수를 출력하는 문제입니다. 문제의 입력 조건에서 N 의 범위가 \(2 <= N <= 100\) 이므로 계단 방향 에 따른 순차탐색으로 풀 수 있었습니다. 우선 가로 방향으로 통과하...

C++ 11에서 추가된 tuple 은 pair 보다 더 많은 데이터 타입을 담을 수 있습니다. pair 의 한계 예를들어 그래프 탐색을 노드 번호가 아닌 2차원 배열의 행렬에서 실행하려고 할 때, 행과 열 번호 그리고 현재 경로의 평가 값까지 pair 로 구성한다면 아래와 같이 작성해야 합니다. priority_queue<pair<...