본문 바로가기

Problem Solving

 (67)
백준 11883 생일수 I https://www.acmicpc.net/problem/11883 11883번: 생일수 I 승현이는 1998년 3월 5일에 태어났습니다. 그래서 승현이는 자신의 생년월일에 있는 수들 중에서 3, 5, 8을 굉장히 좋아합니다. 이에 승현이는 10진수로 표현했을 때 3, 5, 8로만 구성되어 있는 자연 www.acmicpc.net 전형적인 다이나믹 프로그래밍 문제이다. 다만 몇 가지 신경 쓸 부분이 있다. 예제에서 주어진 11을 보자. 11은 3+8=11 이어서 38로 생일수를 만들 수 있다. 이 문제를 풀기 위해서는 3, 5, 8을 차례대로 활용하여 합산 해나가 11을 완성하면 된다고 생각할 수 있다. dp[i]자리에 3, 5, 8등을 넣어주고, dp[목표값]을 읽어서 그 자리에 8이 있다면, dp[목표..
백준 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까지이고, 두 번째 줄에는 랜덤으로 숫자가 배치된다. 각 줄을 집합으로 묶어주고, 비교를 통해 같은지 판단하면 된다. 중요한 점은 항상 첫 번째 줄에는 모든 숫자가 등장하지만, 두 번째 줄에는 숫자들이 선택적으로 등장한다. 따라서 첫번째 줄을 순회하면서 두 번째 줄에 ..
백준 1043 거짓말 www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제는 유니온 파인드+BFS 또는 비트마스킹을 통해 해결할 수 있다. 유니온 파인드를 모른다면 본 블로그의 해당 포스팅을 읽어보길 바란다. 아래의 그림을 보자 문제에 주어진 바와 같이, 파티 3개를 구성했다. 그리고 파티에 참가하는 인원들을 모두 엮어서 그래프로 표현할 수 있다. 2-3-4는 같은 파티에 참가하므로 사이클을 이루고, 1과 2가 같이 파티에 참가하므로 연결된다. 가장 중심에 있는 2가 만약에 진실을 알고..
백준 2352 반도체 설계 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 이 문제는 이런 유형을 아예 처음 보았다면 이것이 LIS인지 쉽게 떠올리기 어려울 수도 있다. LIS에 대한 내용은 이전 포스팅에서 정리해두었으니 참조 부탁드린다. 위와 같이, 1에서 시작한 선은 4로 연결되고, 3에서 시작한 선은 6에서 끝난다. 그 시작점과 끝점을 두줄에 걸쳐 나열하였다. 윗줄에 1, 2, 3, 4, 5, 6을 굳이 쓴 이유는 출발점이 증가하는 순서대로 나열되어있다는 것을..
백준 19238 스타트 택시 (삼성 기출) www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 약간의 자료구조 설계와 BFS를 주로 사용하여 해결할 수 있다. 항상 그렇듯이, 이러한 구현 문제는 문제의 조건을 신경 써서 잘 읽고, 흐름과 스토리를 잘 파악해야 한다. 주요한 조건들은 아래와 같다 - 승객을 고를 때는 최단거리에 있는 승객을 선택한다. - 승객마다 가고자 하는 목적지가 있고, 거기까지는 무조건 이동한다. (그 승객의 목적지가 멀다고 승차거부 등을 하지 ..

티스토리툴바