Algorithm/Algorithm Problem

백준 16206 롤케이크(그리디)

https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 문제를 읽고 그리디적으로 푸는 것이라고 생각했다. 무조껀 10의 케이크만 먹을 수 있기 때문에 10으로 나눈 몫과 나머지에 집중을 하기 시작했다. 규칙을 찾아보니까 1. x에 대해 10으로 나눈 나머지가 있을 경우 x//10번 자르면 x//10개의 10길이 조각이 나온다. 2. x에 대해 10으로 나눈 나머지가 없을 경우 x//10 -1번 자르면 x//10개의 10길이 조각이 나온다...

백준 1068 트리(DFS)

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net DFS를 이용하여 방문처리를 해준다음 풀어나가는 문제였다. 처음에 접근한 방식은 2중 그래프를 만들어서 각각 숫자에 누가 연결되어있는지 판단한 다음에 -1이 root node이기 때문에 -1부터 시작해서 DFS를 돌리고 len(graph[temp]) == 0일 때 자식노드가 없다는 것으로 판단하고 풀었는데 완전히 잘못된 생각이였다. 반례) 4 -1 0 1 2 2 처럼 모두 일직선으로 연결되어..

백준 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 문제의 범위를 보고 이분탐색이라고 생각을 먼저 했다. 하지만 어떤값을 탐색할지에 대해 고민이 많았는데 결과적으로 우리가 구하려는 총 시간에 대해서 탐색한다. 일단 start, end값을 정해야하는데 0이나 1이라고 두고 end는 min(time) * m이 된다. why?) time에서 가장 작은 값의 입국심사대에 m명 모두 그 심사대만 이용가능한 경우이므로 min(time)*m 이 ..

백준 2251 물통(BFS)

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 물을 옮길 수 있는 방법은 총 6가지이다. x -> y, x -> z, y -> x, y -> z, z -> x, z -> y : 6가지 x -> y 라고 한다면 2가지의 경우가 있을 수 있는데 1. x의 담긴 물을 모두 y로 옮긴다 2. x의 담긴 물을 모두 y로 옮기려고 했지만 y의 용량(b)때문에 b-y만 옮기는 경우 1,2 case의 min()값을 옮겨주는 물이라고 생각..

백준 6236 용돈 관리(이분 탐색)

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net K원을 통장에서 빼서 K원을 가지고 일주일 동안 몇번을 뺄 수 있는지 검사하는 문제이다. K의 범위는 max(money) ~ sum(money) 이다 => 일단 sum(money)를 가지고 있으면 통장에서 돈 뺄일 없이 가지고 있는 돈으로 계속 활용 가능하기 때문 => 사실상 K는 1부터 시작해도 되긴함. 하지만 max(money)값 부터 시작하는 이유는 1 ≤ M ≤ N 조건 때문인데 n이 7이라면 ..

백준 10451 순열 사이클(DFS, Union-Find)

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 주어진 순열에 대해서 그래프를 만들고 그 그래프(사이클)이 몇개 있는지 파악하는 문제이다. 문제를 읽고 dfs,bfs나 union-find로 풀 수 있을 것 같다는 생각을 하여 풀었다. union-find로 풀면서 헷갈리는 부분이 있었는데 이 알고리즘을 정확히 알아야한다. union은 단순히 합치기, find는 부모노드를 찾..