본문 바로가기

Problem Solving/백준

 (56)
백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이 문제는 다익스트라와 역방향 그래프의 응용법? 사용법?을 한 가지 더 익힐 수 있는 좋은 문제다. 그리고 이 문제는 플로이드와샬을 사용하기는 힘들다 -> O(n^3)이기 때문이다. 위의 그림을 보자. 보통 다익스트라 최단경로 문제에서는 1번에서 출발하여 6번까지 가려고 할 때 소모되는 비용이나 경로를 출력하라고 한다. 그러면 보통 1번 정점에서 시작하여 우선순위 큐..
백준 1019 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 숫자 N이 주어졌을 때 1(첫 페이지)부터 N까지 쭉 순회하면서 등장한 숫자를 세는 건 당연히 안된다. 그 방법으로는 절대로 안된다는 걸 직관적으로 알려주기 위해 N의 상한이 10억이다... 그러면 당연히 숫자가 주어졌을 때 그 숫자만 보면서 답을 구할 수 있지 않을까라는 생각을 해봐야 한다. 필자가 생각한 방법은 주어진 숫자를 첫자리, 중간자리, 끝자리 이렇게 3개의 파트로 나누는 것이다. 예를 들어, 3516라는 숫자가 주어졌다고 하자. 그러면 첫자리는 3이고..
백준 20040 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 본 문제는 전형적인 유니온 파인드 문제이다. 혹시라도 유니온-파인드 알고리즘이 생소하신 분은 이 링크를 참조하여 훑어보기 바란다. 유니온-파인드를 이해하고 잘 적용할 수 있다면 비교적 평이한 문제일 수 있지만, 주의해야 할 부분이 있어서 포스팅하게 되었다. 파이썬 언어를 사용할 경우, 스택 깊이가 1000으로 기본 설정되어있는데, 이 깊이를 키우기 위해서는 아래와 같이 해야 한다. sys.s..
백준 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차원 배열을 만드는 것부터 잘못되었..
백준 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가 만약에 진실을 알고..

티스토리툴바