본문 바로가기

전체 글

 (84)
백준 8980 택배 www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 필자는 이 문제를 보면서 백준의 회의실 배정, 강의실 배정과 비슷하다는 느낌을 받았다. 그 둘과 같이 이 문제도 그리디 문제이기 때문이다. 필자도 비전공자이며, 이론을 아주 탄탄하게 알고 있는 게 아니라서 그리디가 무엇인지 정확하게 설명하긴 어렵다. 하지만, 이 문제에 빗대서 대략적으로라도 풀어본다면, "트럭이 꽉 찼을 때, 가장 나중에 도착하는 마을로 배달하는 박스들부터 버린다"이다. 다른..
백준 3020 개똥벌레 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이 문제의 제한조건을 보자. 일단 중요한 건 종유석과 석순의 길이대로 일일이 ++을 해주는 식으로 풀 수는 없다. H가 50만, N이 20만이기 때문이다. 아래의 그림을 보자. 위에서처럼, 입력을 N번 받고, 그때마다 0부터 k까지 확인하며 2차원 배열 arr안에 1을 채워나가는 방식으로 풀려고 한다면 시간적으로도 공간적으로도 효율적이지 못하다. 애초에 20만 곱하기 50만짜리 2차원 배열을 만드는 것부터 잘못되었..
기계적인 풀이, 정형화된 틀 -> PS는 암기? * ps = problem solving (알고리즘 문제풀이를 일컫는다.) 가끔 어떤 문제가 어떤 알고리즘 문제로 분류되는지를 파악하지 못할 때가 종종 있다. 풀 수는 있는데, 이게 무슨 풀이인지를 본인도 잘 모르겠는 것이다. 그것은 아마도 필자가 어떤 정형화된 틀이 갖춰져 있지 않음이기도 하다. 장단점이 있겠지만, 일단 생각나는 단점은 빠른 풀이가 조금 힘들 때가 있다. 척하면 팍하고 나와야 하는 코드가 바로바로 나오지 않아서 처음부터 다시 생각해야 하기 때문이다. 마치 DP에서 이전 값을 바로 참조하여 바로 현재의 값을 구하는 것처럼 빠르게 풀이가 되어야 하는데, DP[0] 또는 DP[1]부터 다시 생각해서 쌓아 올려야 할 때가 있기 때문이다. 물론 거듭된 연습으로 익숙한 형식들은 빠르게 풀겠지만, ..
백준 2668 숫자고르기 www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 이 문제는 그래프 탐색, 깊이 우선 탐색 등으로 분류되어 있는데, 필자는 집합을 활용한 풀이를 생각했다. 첫 번째줄은 항상 1부터 N까지이고, 두 번째 줄에는 랜덤으로 숫자가 배치된다. 각 줄을 집합으로 묶어주고, 비교를 통해 같은지 판단하면 된다. 중요한 점은 항상 첫 번째 줄에는 모든 숫자가 등장하지만, 두 번째 줄에는 숫자들이 선택적으로 등장한다. 따라서 첫번째 줄을 순회하면서 두 번째 줄에 ..
백준 2917 늑대 사냥꾼 www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 필자는 다익스트라 알고리즘을 활용하여 풀었으나 사실 BFS와 방문체크를 통해도 해결할 수는 있다. 오히려 속도도 더 빠를 것이다. 일단 필자의 풀이를 보면, BFS를 활용하는 방법도 바로 자연스레 이해될 것이다. 사실 한 정점에서 다른 정점으로 갈때의 비용이 항상 1이기에 BFS를 생각하는 것이 더 자연스럽다. 위와 같이 지도 상에 나무( + )가 배치되어있다고 하자. 각 나무에 cost=0을 두고 BFS나 다익스트라 ..

티스토리툴바