알고리즘
백준 1715번 : 카드 정렬하기
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net N개 만큼의 카드묶음이 있으며 이들 중 2개를 골라 1개의 카드묶음으로 만드는 작업을 수행할 수 있고 최종적으로 N개의 카드묶음을 1개의 카드묶음으로 만드려고 한다. 2개의 카드묶음을 합칠 때에는 각 카드묶음에 있는 카드 수를 합한 만큼 비교를 수행하는데, 비교 횟수를 최소화하려고 한다. 이때 최소화된 비교 횟수를 구하는 문제이다. 전형적인 그리디 알고리즘 유형이다. N개의 카드묶음..
백준 22871번 : 징검다리(large)
https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색 카테고리 문제를 풀다가 접하게 된 문제다. 연산시간 때문에 하루종일 이 문제만 붙잡고 고민했다. 최적화 하려는 변수가 M이라면 보통 이분탐색 문제는 O(log M) 시간안에 해결이 가능하거나 그 보다 오래 걸리더라도 주어진 시간 안에 해결이 가능했다. 관련하여 문제를 풀면서 고민한 것들을 글에 풀어서 써보겠다. N개의 징검다리..
백준 3079번 : 입국심사
https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 2110번에서 알게된 내용들을 적용해서 생각보다 쉽게 푼 문제다. M명의 사람들은 입국하기위해 입국심사를 받는다. 심사대는 총 N개가 있고 심사대마다 심사에 소요되는 시간이 정해져있다. M명의 사람들을 모두 통과시키는 최소한의 시간을 구하는 문제이다. 앞서 푼 문제에서 배운 이분 탐색의 요령을 그대로 적용했다. 구하려는 값은 시간이기 때문에 가능한 범위 안에서 조건(시간 안에 사람들..
백준 2110번 : 공유기 설치
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 우아한 테크코스 코딩테스트를 준비할겸 기초 알고리즘을 복습하기 위해 접했던 이분 탐색 문제다. 기존에 풀었던 이분 탐색 문제와 달리 바로 해결 아이디어가 떠오르지 않아서 질문 게시판을 참고해서 해결했다. 일직선(1차원) 좌표상의 특정 좌표에 집이 존재하고 주어진 개수만큼의 공유기를 집에 설치하고자 한다. 공유기는 한 집에 1개만 설치가능하며 주어..
백준 17836번 : 공주님을 구해라!
https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 용사는 마왕성에서 공주를 구해야한다. 마왕성은 1x1 크기의 정사각형으로 이뤄져있고, 각 칸은 이동할 수 있는 길 또는 벽이다. 용사는 인접 칸으로 이동하기 위해서 1시간이 걸리고 주어진 시간 내에 공주에게 도달해야한다. 마왕성 어딘가에는 용사의 무기 "그람"이 1개 존재하는데, 이 그람을 가지면 그 순간부터 벽을 부수고 지나갈 수 있다. 용사가 공주를 구할 수 있는지 여부를 확인..
백준 13549번 : 숨바꼭질 3
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제의 첫 인상은 그래프 탐색 문제처럼 보이지 않고 독특했다. 0부터 100,000까지 점이 존재하고 수빈이와 동생이 이 점들 중 한 곳에 존재한다. 수빈이는 현재 위치를 기준으로 1만큼 뒤로 가거나 앞으로 갈 수 있지만 시간이 1초 소모된다. 또한 수빈이는 시간 소요없이 현재 위치에 2배가 되는 곳으로 순간이동 할 수 있다. 수빈이가 동생을 찾기 위해 소요되..
백준 16956번 : 늑대와 양
https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net DFS, BFS를 이용한 그래프탐색 카테고리에 포함된 문제들을 풀다가 특이한 문제를 발견했다. 문제를 요약하면 1x1 크기의 칸으로 나뉘어진 목장의 상태를 보고, 자유롭게 움직일 수 있는 늑대가 양에게 접근할 수 없게 울타리를 친다. 문제를 보고 이해했을땐 단순히 처음 주어진 늑대의 위치 좌표를 초기 큐에 넣고 BFS 탐색을 하면서 인접한 칸들을 확인하며 인접칸에 양이 있다면 그 자리에 울타리..