Gi-Log

문제 링크: https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 이진 탐색, 파라메트릭 서치 주어진 상황에서 가장 최적의 값을 고르는 문제이므로, 아직 실력이 부족한 나는... 탐욕법을 떠올렸다. 하지만 입력의 크기를 보아하니, 탐색의 범위가 굉장히 크다는 점과 결국 확인해야할 것은 "1회 인출 시 금액"으로 1번째 날부터 n번째 날까지 생활이 가능한 지, 불가능한 지 결정하는 문제 같다고 생각하여 이진 탐색으로 접근하기로..

문제 링크 : https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 모든 행성 간에 플로우를 설치하고 싶지만, 플로우를 설치할 때 사용되는 군대 주둔 비용이 비싸서, 가장 효율적으로 플로우를 설치해야 하는 문제이다. 개인적으로 이런 그래프에서 효율성이나 일의 순서를 파악하는 문제를 보면, 신장 트리와 위상 정렬을 떠올린다. 효율성과 관련된 것은 최소 신장 트리(MST), 일이나 작업 순서를 파악해야하는 문제는 위상 정렬을 이용하며 현재 문제는 최소 ..