본문 바로가기

전체 글

 (386)
백준 1516번 - 게임 개발 (C++, 위상정렬, 다이나믹 프로그래밍) https://www.acmicpc.net/problem/1516 다시풀어본 위상정렬 + 다이나믹 프로그래밍 문제이다.문제 분류가 다이나믹 프로그래밍이라 dp라 쓰긴 했는데 솔직히 이게 dp인가 싶다. 그냥 정답을 계속 갱신하는데만 쓰이는데 이게 디피라고 볼 수 있는건가..?  위상정렬은 순서가 정해진 그래프를 보고 그 순서대로 정렬이 가능한 유용한 알고리즘이다. 그것을 사용해 이 예제를 풀어보자.선행조건이 없는 1번과 7번 건물이 먼저 지어질 것이다. 3번의 경우 1번을 짓는데 100의 시간, 7번이 200, 6번이 300 이라 가정하면 3번을 짓는데 드는 시간은 6,7번을 지어야하는 500의 시간이다.  그리고 3은 1번에서 도착할 경우와 6번에서 도착할 경우를 비교해야한다. 즉, F(3) = com..
누적합 알고리즘(1차원, 2차원 누적합) 누적합 알고리즘은 1~N까지 합을 효율적으로 구할 수 있는 알고리즘이다. 11 + 21 + 2 + 31 + 2 + 3 + 4 라고하면 sum[1] = 1sum[2] = 3sum[3] = 6sum[4] = 10 이고 여기서 2~4까지의 합을 구하면 sum[4] - sum[1] 과 같다. 즉 answer = sum[end] - sum[start - 1] 이다. 그리고 중요한건 모든 sum 배열을 구성하는 것이다. 이 때 O(N^2)의 시간을 사용하는 것은 너무 비효율적이다. 효율적으로 사용하기 위해 sum[2] = sum[1] + arr[2]sum[3] = sum[2] + arr[3]... 식을 사용하면 O(N)으로 prefix배열을 구성할 수 있다. 1차원 배열 누적합은 쉽게 구성이 가능하다. 이것을 응용..
백준 1103번 - 게임(C++, dfs를 DP로 최적화) https://www.acmicpc.net/problem/1103 문제를 처음 봤을 때 가장 먼저 떠올라야하는 것은 dfs이다. 어딘가 최소거리로 도착하는 것도 아니고 한 노드에 도착한 후에 4방향으로 가장 멀리 가는 것이 목표이기 때문에 bfs를 적용하는 것은 옳지 않다.하지만 dfs로 모든 방법을 찾는 것은 시간이 매우 오래걸린다. N^M 의 크기를 갖고 있고, 만약 모든 노드의 크기가 1이라면 한 노드에서 나아갈 수 있는 방향은 4방향이므로 O(4^N *M) 의 매우 큰 시간이 소모된다. 그래서 dfs를 dp로 최적화해야한다. 예제를 살펴보자  394217812345679123532 0,0 에서 왼위아래 모두 갈 수 없다. 그렇다면 오른쪽으로 가야하고 왼쪽으로 세칸이니까 0, 3으로 이동하게 되면 ..
백준 1600번 - 말이 되고픈 원숭이 (C++) https://www.acmicpc.net/problem/1600 bfs 문제로 1년만에 다시 풀어보았다. 흥미로운 점은 과거의 나는 k값을 주어진 개수만큼 넣어놓고 --한 반면 오늘의 나는 0으로 두고 하나씩 늘려나갔다는 것과 지금은 큐 내에서 cnt 를 늘렸는데 과거에선 dis 배열을 만들어서 거기에다가 값을 넣어놓았다. 둘 다 할 수 있는 방법이지만 왜 굳이 저렇게 했는지..  그런데 dis배열에 넣는 것이 훨씬 시간이 짧았다... 이걸로 다익스트라처럼 가지치기를 하는 것도 아니고 같은 순회를 할 탠데 왜 시간이 덜 걸리는지 모르겠다. 각설하고 이 문제는 말처럼 이동할 수 있는 k이동을 20번 남았을 때와 10번 남았을 때의 상황을 따로 가정하여 방문 표시를 해야한다. 때문에 3차원 visited ..
백준 1092번 - 배(c++) https://www.acmicpc.net/problem/1092 6개월만에 다시 본 문제. 그러나 엄청나게 틀렸다.. 문제 접근법이 틀리진 않았으나 조금 더 디테일이 필요하다.문제 유형은 그리디로 각 크레인에 가장 비슷한 무게를 달아줘야한다. 그래서 필연적으로 크레인과 박스 둘 다 정렬이 필요한데, 여기서 어떻게 크레인과 박스를 매치해줄 수 있는가?  그리디 하게 생각하면  1. 크레인 x번을 모든 박스와 매칭해보고 가장 맞는 것을 고른다.2. 이것을 크레인의 개수만큼 반복한다. 먼저 시간복잡도를 고려해보자. 그렇다면 O(N * M) 의 시간이 소요되며 최악의 경우 O(N * M * M)의 시간이 걸린다. M = 10000, N = 50 이므로 M * M은 안된다. 그래서 처음엔 각 박스의 인덱스를 b..
최소 스패닝 트리 (MST) - 크루스칼 알고리즘 MST는 최소 스패닝 트리의 줄임말로 어떤 그래프가 있을 때 모든 노드를 포함하여 사이클이 생기지 않는 트리를 뜻한다. 한붓그리기를 생각하면 편하다. 크루스칼 알고리즘은 Greedy 알고리즘의 일종이다. 간선을 선택할 때 가장 비용이 적은 간선을 선택하면서 사이클이 생기면 넘어가는 식으로 진행된다.그렇기 때문에 크루스칼 알고리즘은 모든 간선의 정보가 정렬되어 있어야 사용할 수 있고 모든 간선을 한번씩 검사하기 때문에 시간 복잡도 = 모든 간선의 수 + 정렬 시간 이 소요된다. 사이클을 검사해야하기 때문에 필연적으로 유니온 파인드 알고리즘도 필요하다. 나름 여러 알고리즘이 합쳐진 고급 알고리즘이라 할 수 있다. 정리해보면  1. 간선의 정보들을 모두 정렬한다. 간선의 비용이 적은 순서대로2. 선택한 간선들..
백준 8980번 - 택배 (C++) https://www.acmicpc.net/problem/8980 이 문제에서 떠올릴 수 있는 풀이법으로 처음에 배낭문제를 떠올렸다. 하지만 cost 와 value 를 나타낼 수 없었고 표가 그렇게 생긴 것 뿐이었다. 그래서 조금 더 고민하다가 떠오른 방법은 Greedy 였다. 이 문제는 대표적인 그리디 문제인 https://www.acmicpc.net/problem/1931 과 유사하다. 워딩은 다르지만 결국 택배를 많이 배달하기 위해선 가장 짧은 거리의 도착지에 도착해야한다. 회의실 배정 또한 가장 빨리 끝나는 회의를 담는 것과 같다.그래서 이 문제는 회의실 배정에서 진행할 수 있는 회의의 갯수가 정해져있으며 동일한 회의를 중복하여 진행할 수 있는 문제로 바뀐다. 그러므로 회의실 배정과 같은 아이디어..
백준 1931번 - 회의실 배정(C++) https://www.acmicpc.net/problem/1931 회의실 배정 문제는 아주 유명한 그리디 문제라고 한다. 그런데 이것을 아직도 안풀어봤다 ㅎ 이전에 다른 그리디 문제를 접했는데 그 문제가 이 문제를 응용한 것이라해서 풀어봤는데 잘 느낌이 안왔다. 아무튼 이 문제는 https://www.acmicpc.net/problem/11000 강의실 배정 문제와 비슷한 입력을 받기 때문에 우선순위큐를 떠올릴수도 있다. 그러나 우선순위큐 문제는 아니다. 무언가 최소로 사용하는 문제가 아니기 때문이다. 아이디어먼저 회의를 아주 많이 하기 위해선 어떤 회의를 진행해야할지 고민해보자. 그렇다. 빨리 끝나는 회의들로 구성해야한다. 여기서 시간이 짧은 회의를 하면 안되나요? 라고 할 수 있는데 만약  1 2 /..

티스토리툴바