본문 바로가기

Problem Solving

 (67)
백준 1700 멀티탭 스케쥴링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 다행히 이 문제는 아주 어려운 그리디 문제는 아니다. 그리디 문제가 어려우면 정말 어려울 때가 있다. 그리디 문제의 어려운 점은 증명이다. 가끔 어떠한 직관에 의해 풀이가 떠오르고, 그대로 구현했을 때 정답인 경우가 있다. 하지만 그 풀이의 증명이 쉽지 않다. 이 문제의 그 '직관'은 가장 마지막에 다시 사용할 기기를 가장 먼저 뺀다는 것이다. (물론 한번 사용한 기기를 다시 쓰는 일이 없다면 현..
백준 2463 비용 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸 www.acmicpc.net 좋은 문제이다. 가장 좋은 문제 몇 손가락 안에 들 정도로. 발상의 전환이 필요하고, 유니온 파인드의 의미에 대한 이해가 필요하다. (최소 스패닝 트리 알고리즘 안에 유니온 파인드가 포함된다.) 유니온 파인드에서 union 으로 연결된 정점들은 일종의 그룹을 만들게 된다. 자연히 그들은 루트(대표)를 갖는다. 그리고 그 루트 정점의 식별자가 해당 그룹의 식별자이..
백준 1102 발전소 https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 이 문제는 백준 2098 외판원 순회와 비슷하면서 다르다. 가장 큰 차이점은 외판원 순회처럼 i도시에서 j도시로 가는게 아니라, 켜져있는 어떤 발전소든지 꺼진 발전소를 재생시킬 수 있는 것이다. 즉 외판원 순회에서 방문한 도시는 다시 못가지만, 이 문제에서는 방문한 도시에서 다시 다른 도시로 또 갈 수 있는 것이다. 굳이 억지를 들자면, 다시 돌아가는 비용은 0인 상태이다. 그러면 코드에서 나타나는 가장 큰 ..
백준 2098 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 대단히 중요한 문제 중 하나라고 생각한다. 비트마스킹 + 재귀 + DP 가 어우러진 좋은 문제이다. 문제에서도 "computer science 분야에서 가장 중요하게 취급되는 문제"라고 언급하고 있다. 이 문제를 해결함에 있어 깨달아야 하는 몇가지 중요한 점 중 하나는 여행을 어디에서 시작해도 상관없다는 점이다. 왜냐하면 항상 시작한 도시로 돌아와야 하기 때문..
백준 11003 최솟값 찾기 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 이 문제는 우선순위 큐로 해결할 수도 있지만, 모노톤 덱을 이용하면 더 빠르다. 우선순위 큐를 활용하려 할 경우, 데이터가 들어왔을 때 우선순위 큐에 담고, 최솟값 찾을 때 이미 범위를 벗어났는지 여부만 확인해주면 된다. 모노톤 덱을 사용한다면, 크기가 증가하는 수열 형태로 덱을 만들어주면 된다. 차근 차근 오른쪽으로 넣어준다. 범위가 벗어났다면 왼쪽에서 버려주고,..
백준 1185 유럽여행 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 위 문제는 다양한 경우의 수가 있을 것 같지만, 문제에 걸린 제한을 통해 '자동'으로 코너 케이스가 다 사라졌다고 생각한다. 증명할 수만 있으면 자신 있게 코드를 제출할 수 있다. 가장 중요한 조건은 N-1개의 길만 남겨야한다는 것이다. 이를 통해 모든 정점들이 빠짐없이 연결되는 트리구조를 갖게 된다는 것을 알 수 있다. 사이클이 없다는 것이다. 여기서 최소 ..
백준 3015 오아시스 재결합 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 결론부터 먼저 말하면 이 문제는 스택 활용이 필요하다. 어차피 검색을 했다면, 풀이가 필요했을 테니 스포일러가 아니리라 생각한다. 스택 활용 문제는 항상 쉽지 않다. 하지만 시간 복잡도를 O(N)으로 낮춰주는 대단히 강력한 방법이다. O(N^2)이 보통 최악이라면, 그것을 O(NlogN)으로만 낮추어도 효율이 좋은 건데 O(N)은 사실상 최선의 방법이다. 적어도 모든 데이터..
LeetCode 532 K-diff Pairs in an Array https://leetcode.com/problems/k-diff-pairs-in-an-array/ K-diff Pairs in an Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 일단은 정렬, 이분탐색을 활용하는 문제이다. 여기에 조금 더 생각을 붙여야 한다. unique한 페어를 리턴해야하기 때문이다. 이분탐색을 하고자 한다면, 이분탐색을 행하는 배열 등이 정렬되어 있어야 한다. 그래서 이분탐색과 정렬은 붙어다닐 수 밖에 없다. 두 수의 차가 ..

티스토리툴바