본문 바로가기

Algorithm175

2580. 스도쿠 (Python) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 백트래킹을 사용하여 문제를 해결할 수 있다. 풀이 과정은 다음과 같다. 먼저 입력을 받으면서 0이 들어있는 좌표를 리스트에 담아둔다. 첫 번째 0부터 시작하여 1~9까지의 숫자를 넣어본다. 이때 가로, 세로 그리고 사각형에 해당 숫자가 들어있는지를 체크한다. 숫자를 넣을 수 있다면 이제 다음 0이 들어있는 좌표로 이동하여 똑같은 과정을 반복한다. 0이 들어있는 모든 좌표에 숫자를 넣었다면 출력을 해주고 프로그램을 종료한다. 코드 import sys # 백트.. 2022. 5. 1.
17472. 다리 만들기 2 (Python) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 다음과 같은 과정을 통해서 문제를 해결한다. 먼저 각 섬에 번호를 붙여주는 작업을 한다. 각 섬에서 위, 아래, 왼쪽, 오른쪽으로 탐색하여 다리를 만들어본다. 섬에서 다른 섬으로 가는 다리 중에서 가장 짧은 거리를 갖고 있는 다리의 정보를 저장한다. 저장한 다리를 다리의 길이를 기준으로 오름차순 정렬한다. 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구성한다. 사용된 다리의 길이들을 합한 값을 출력한다. 코드 import sys imp.. 2022. 4. 30.
2513. 통학버스 (Python) 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원 www.acmicpc.net 풀이 학교의 위치부터 가장 멀리 떨어져 있는 아파트부터 먼저 방문해서 태울 수 있는 만큼 학생들을 태워가며 버스의 이동거리를 계산해주면 된다. 이때 학교를 기준으로 왼쪽에 있는 아파트와 오른쪽에 있는 아파트로 나누어 왼쪽으로 한 번 작업을 수행하고 오른쪽으로 한 번 작업을 수행해주면 된다. 학교로부터 가장 멀리 떨어져 있는 아파트부터 먼저 방문해야 하므로 왼쪽 아파트의 경우에는 아파트 위치를 기준으로 최소힙으로 구성하였고 오른쪽 아.. 2022. 4. 30.
2550. 전구 (Python) 2550번: 전구 N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 www.acmicpc.net 풀이 LIS를 사용하여 해결하는 문제다. LIS는 여기를 참고하자. 문제는 여기에서 LIS의 길이뿐만 아니라 LIS에 포함되는 원소까지 구해야 한다. 일단 LIS를 구하는 대상이 되는 배열은 n번의 스위치가 전구 리스트에서 몇 번째에 있는지를 나타내는 인덱스 리스트이다. 문제의 예제를 보면 스위치 리스트 [2, 4, 1, 5, 3]은 각각 전구 리스트에서 [4, 0, 2, 1, 3] 인덱스에 존재한다. 따라서 [4, 0, 2, 1, 3]에 대해서 LIS를 구하고 각각에 .. 2022. 4. 28.
1781. 컵라면 (Python) 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 그리디하게 현재 시간에서 풀 수 있는 문제의 리스트 중 가장 많은 컵라면 수를 얻을 수 있는 문제를 풀어 컵라면을 얻도록 하면 된다. 이때 현재 시간은 1에서부터가 아닌 제일 큰 데드라인부터 1씩 줄여가면서 풀 수 있는 문제에 대하여 컵라면 수를 우선순위 큐에 넣고 가장 큰 수를 꺼내어 풀면 된다. 문제의 예제를 보면 가장 큰 데드라인은 6이다. 그렇기 때문에 시간은 6부터 시작한다. 현재 시간 6에서 풀 수 있는 문제는 7번이 있다. 7번을 풀고 얻을 수 있는 컵.. 2022. 4. 27.
11054. 가장 긴 바이토닉 부분 수열 (Python) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 최장 증가 부분 수열(LIS)을 활용하여 해결하는 문제다. LIS는 이 링크를 참고하자. LIS를 구하는 방법에는 dp를 사용하는 방법과 이분 탐색을 사용하는 방법이 있다. 이 문제는 dp를 사용하여 해결하면 된다. A 배열의 각 원소까지 증가 부분 수열을 만들었을 때의 길이를 구한다. 위와 같은 array가 있을 때 dp 배열의 의미는 각 인덱스까지의 증가 부분 수열 중 가장 긴 증가 부분 수열의 길이를 의미한다. 이렇게 한 번 dp를 구하고 이번에는 배열을 뒤집어서 한 번 .. 2022. 4. 26.

티스토리툴바