백준 문제 풀이 (148) 썸네일형 리스트형 백준 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.. 백준 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 /.. 백준 2887번 - 행성 터널 (C++) https://www.acmicpc.net/problem/2887 문제 자체는 값에 따라 그래프를 구성하고 MST를 구하면 되는 문제이다. 그러나 노드의 개수가 10만이며 간선의 수도 만만치 않다. 그래서 모든 간선을 각자 비교하여 구하면 10만 * 10만 * 4byte 이므로 말도안되는 메모리를 사용해버린다..! 그래서 이 문제의 핵심은 어떻게 3개의 좌표를 가진 노드들을 효율적으로 비교할 것인가?로 귀결되고 이 것이 문제이다. A: 2, 3, 5B: 6, 9 10C: 11, 1, 3 이렇게 있다고 해보자. 만약 모두 구하려면 9번의 연산이 필요하고 각각 X, Y, Z를 비교한 값을 가지고 있어야한다.하지만 결국 간선이 될 수 있는 후보는 X, Y, Z의 최소차이가 간선의 후보이다. 좌표끼리 한 .. 백준 9328번 - 열쇠(C++) https://www.acmicpc.net/problem/9328 문제를 처음 접했을 땐 bfs + bitmasking을 떠올렸다. 왜냐하면 열쇠를 갖고 있는 상태에 따라 이미 visited 되어 있더라도 다시 갈 수도 있기 때문이다. 그러나 이것은 최소거리를 구할 때나 경로를 구할 때나 필요한 것이다. 무슨 말이냐면 만약 2, 2 -> 2, 3을 이동하는데 2,3 은 A 열쇠가 없어서 갈 수 없다고 가정하자. 만약 최소거리를 구하는 것이라면 A 열쇠를 찾는 거리까지 고려해야하지만 이 문제는 그냥 도달할 수 있는가 없는가 만을 생각한다.그래서 2,3이 필요한 열쇠를 다른 곳에 저장해둔다음, 다른 곳에서 탐색했을 때 만약 A 열쇠를 찾는다면 저장해둔 곳을 이제 갈 수 있으므로 큐에 삽입하면 된다. 단 .. 백준 3015번 - 오아시스 재결합(C++) https://www.acmicpc.net/problem/3015 Greedy 문제처럼 생겨서 그리디로 접근하려 했지만 N의 개수를 확인했을 때 반복문 안에서 다시 반복문이 실행되는 순간 시간 초과가 발생할 것임을 직감했다. 그래서 결국 문제 분류를 보니 stack 을 확인했다.들어오는 숫자에 따라 스택을 사용해 f(x)를 구성하면 N번의 Stack Push로 O(N) 에 문제를 해결할 수 있다. 문제는 3가지 경우로 나눌 수 있다. 이번에 들어온 사람의 키가 직전 사람보다 ~1. 작은 경우2. 같은 경우3. 큰 경우 1번 직전 사람보다 작은 경우를 생각해보자. 543 2 현재 stack.top() = 3 이며 3은 자기 직전 4, 이후 2와 마주볼 수 있다. 2번 같은 경우를 생각해보자. 543 .. 백준 1010번 - 다리놓기 (C++) https://www.acmicpc.net/problem/1010 지능과 센스가 있으면 쉽게 풀 수 있는 문제. 그러나 난 둘다 없다 ㅎ. 다이나믹 프로그래밍 태그에서 들어간 문제이기 때문에 DP임은 알고 있었다. 이 문제에서 DP를 사용하는 방식은 두가지 가 있는데, 하나는 순수 DP, 하나는 조합론을 사용하는 방법이다. 1. 조합론 이 문제는 2 -> 4 문제로 보이지만, 우측에서 좌측으로 보낸다고 생각하면 언제나 꼬이지 않고 선을 연결할 수 있는 방법이 있다. 그러므로 문제는 갑자기 M combination N 을 구하는 문제로 바뀌어버린다. 그대로 주어진 조합을 구해도 괜찮지만 알다시피 조합은 엄청난 시간복잡도를 자랑하기 때문에 사용하기 어렵다. 이 문제에선 가능하지만 말이다. 그렇다면 조합의 .. 백준 1700번 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 골드1 치곤 조금 쉽다고 느낀 문제이다.처음엔 DP를 생각했다. 하지만 알고리즘 분류를 보니 그리디였다. DP로 점화식이나 규칙을 찾아볼 때 이전의 값을 사용하는 낌세가 보이지 않고, 상태를 계속 변경하면서 체크해야하면 그것은 DP가 아님을 인지하고 빠져나와야하는데 실력이 너무너무너무 부족하다. 하,, 그리디로 넘어와서 멀티탭에 꽂아져있거나, 자리가 있으면 괜찮지만 자리가 없으면 무엇을 뽑아야할지 정해야한다. 여기서 난 처음에 2, 4, 5 가 꽂혀있다고 할 때 남은 스케줄 중 2의 개수, 4의 개수, 5의 개수 중 가장 개수가 적은 것을 뽑는 알고리즘을 작성했다. 합리적으로 보이나 반례가 있었다. 만약 3 2 3 4 4 4 5 5 5.. 이전 1 2 3 4 5 6 7 ··· 19 다음
