문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 그래프 탐색과 이분 탐색을 함께 사용하여 해결했다. 그래프 탐색이 조금 까다로웠는데, 결정 문제를 접합하면 좀 더 간단하게 해결이 가능했다. C의 범위가 굉장히 크기에 이분 탐색을 적용해야 한다. 그래프 탐색 시 인접한 노드와 연결된 다리의 중량제한이 판별하고자 하는 값(target, == mid)과 같거나 큰 경우에만 탐색할 ..
문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 석순과 종유석을 별도의 리스트에 담아 정렬한 후, 이진 탐색을 진행하면 얼마나 많은 장애물을 파괴해야 하는지 구할 수 있다. 이때, bisect 모듈을 사용하면 좀 더 간결하게 코드를 짤 수 있다. 해당 함수들은 리스트에서 특정 값이 삽입될 인덱스를 반환한다. bisect_left(arr, value) bisect_right(arr, value) bisect — 배열 이진 분할 알고리즘 —..
문제 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 풀이 "당근을 먹지 않을 수도 있다"와 "항상 w
문제 https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 풀이 문제의 설명이 아주 친절하기 때문에 그대로 풀면되는 간단한 구현 문제였다. 이중 for문을 통해 해당 열의 가장 위에 있는 인형을 확인한다. 이 과정에서 기존 스택의 가장 위에 있는 인형(basket.peek( ))과 가장 위에 있는 인형(value)을 비교해서 동일하다면 스택에 있는 인형을 제거하고, 아니라면 인형을 스택에 넣는다. 이때, 스택에 먼저 인형을 하나 넣음으로써 ..
문제 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 풀이 정렬을 통해 해결할 수 있는 문제였다. 내림차순으로 정렬된 리스트가 하나 있다고 가정해보자. List = [L1, L2, L3, ... , Ln] (L1 > L2 >L3 > ... > Ln) L1을 기준으로 차이가 가장 적게 나는 원소 2개는 L2와 L3일 것이다. 마찬가지로 L2가 기준이라면 L3, L4일 것이고, 이는 계속해서 반복된다. 또한, 내림차순으로 정렬되어 있기 때문에 당..
