Algorithm/Python
-
[BOJ] 백준 11726 2×n 타일링 (Python)
문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 해석 접근 방법 전형적인 DP(Dynamic Programing) 문제입니다. 각 단계를 이전 단계의 경우의 수의 합으로 나타낼 수 있습니다. 풀이 과정 이번 문제의 경우, 각 단계는 크게 두 가지 경우로 나눌 수 있습니다. 1. 마지막 타일이 세로 타일 한 개인 경우 (세로 타일이 두 개인 경우는 여기에 포함) 2. 마지막 타일이 가로 타일 두 개인 경우 결국 마지막에 어떤 타일이 오는 지에 따른 경우의 수의 합으로 생각할 수 있습니다. 전체 코드 from sys impo..
Algorithm/Python 2023. 8. 25. 23:59 -
[BOJ] 백준 1149 RGB 거리
문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해석 접근 방법 DP(Dynamic Programing)을 사용해 풀 수 있는 문제입니다. 풀이 과정 DP 문제는 점화식을 도출하는 것, 즉 이전 단계에 계산한 값을 어떤 방식으로 활용할 수 있을 지 생각하는 것이 중요합니다. 이번 문제의 경우 인접한 칸에 같은 색깔을 선택할 수 없다는 조건이 있습니다. 따라서 각 색깔을 선택했을 때 얻을 수 있는 최소 누적 비용을 계산해서 배열에 저장한 후, 다음 칸의 누적 비용을 계산할 때는 ..
Algorithm/Python 2023. 8. 24. 20:15 -
[BOJ] 백준 1931 회의실 배정 (Python)
문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해석 접근 방법 그리디 알고리즘과 정렬을 사용해 풀 수 있는 문제입니다. 회의실을 가능한 한 많이 사용해야 하므로 일찍 끝나는 회의부터 순서대로 선택하면 됩니다. 풀이 과정 1. 일찍 끝나는 순서대로 회의들을 정렬 2. 직전에 선택한 회의와 시간이 겹치지 않도록 다음 회의를 선택 일찍 끝나는 회의부터 선택하기 위해 회의의 종료 시간을 기준으로 오름차순으로 정렬합니다. 하지만 회의의 종료 시간만 기준으로 삼으면 풀리지 않는 예외 케이스가 존재합니다. 시작과 동시에 끝나는 회의가 존재하기 때문입니다. 만약 주어진 회의 시간이 다음과 같다고 가정해보겠습니다. (N = 3)..
Algorithm/Python 2023. 8. 23. 01:28 -
[BOJ] 백준 2217 로프 (Python) + enumerate
문제 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 해석 접근 방법 그리디 알고리즘과 정렬을 통해 풀 수 있는 문제입니다. 로프 n개를 선택했을 때 버틸 수 있는 최대 중량을 각각 계산한 후 그 중 가장 높은 값 선택하면 됩니다. 풀이 과정 각 로프의 최대 중량과 로프 조합의 최대 중량을 구분하기 위해 각 로프의 최대 중량은 로프의 내구도라고 표현하겠습니다. 로프 n개를 선택했을 때 버틸 수 있는 최대 중량은 n개 중 가장 약한 로프의 내구도 * n 입니다. 만약 주어진 로프가 다음과 같다면 ..
Algorithm/Python 2023. 8. 22. 17:10 -
[BOJ] 백준 2457 공주님의 정원 (Python)
문제 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제 해석 접근 방법 그리디 알고리즘과 정렬을 사용해 풀이할 수 있는 문제입니다. 현재 선택할 수 있는 꽃 중에서 가장 늦게 지는 꽃을 선택해나가면 최소한의 개수로 조건을 만족할 수 있습니다. (매일 꽃이 한 가지 이상만 피어 있으면 된다는 조건 때문에 그리디 알고리즘을 사용했습니다. 구간의 중복을 고려하지 않고 가장 늦게 지는 꽃을 선택할 수 있기 때문입니다. 만약 조건이 바뀌어 하루에 꽃이 단 한 송이만 피어 있어야 한다면 다른 풀이..
Algorithm/Python 2023. 8. 22. 11:54 -
[BOJ] 백준 1520 내리막 길 (Python)
문제 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 해석 접근 방법 dfs와 dp를 함께 사용해 풀 수 있는 문제입니다. dfs만 사용할 경우 (완전 탐색을 사용할 경우) M과 N이 최대 500이므로 시간 제한에 걸릴 수 있습니다. 이때, dp를 사용해 한 지점에서 목적지까지 갈 수 있는 경우의 수를 합산해서 저장한 후, 다음 지점의 경우의 수에 합산하는 것을 반복한다면 최초 한 번 방문한 지점에 대해서는 dfs를 실행하지 않아도 되므로 실행 시간을 줄일 수 있습니다. 전체 코드 from sys import..
Algorithm/Python 2023. 8. 21. 23:46 -
[BOJ] 백준 5397 키로거 (Python)
문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 전체 코드 from sys import stdin from collections import deque t = int(stdin.readline().rstrip()) ## 문자열 slicing 사용했을 때 시간 초과 ## deque 사용해서 해결 for _ in range(t): pw_left, pw_right = deque([]), deque([]) key_log = stdin.readline().rstrip() for key in key_log:..
Algorithm/Python 2023. 8. 20. 23:21 -
[BOJ] 백준 1475 방 번호 (Python)
문제 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해석 접근 방법 숫자 세트는 방 번호 중 중복된 숫자의 최대 개수만큼 필요합니다. ex) 112312 : 1이 3번 중복되므로 세트 3개 필요 단, 6, 9는 숫자 구분 없이 두 개 당 한 세트만 사용하면 됩니다. 따라서 제시된 방번호 N에 6 또는 9가 포함되어있을 경우 숫자 한 개당 세트 0.5개로 계산해 준 후 올림 처리를 해줍니다. ex) 계산한 세트 수가 3.5개인 경우 > 최소 4개를 사야 충족할 수 있음 이번 문제 풀이에서는 올림 처리를 위해 ceil 함수를 사용했습니다. ceil() : 실수를 올림해 정수 타입인 int로 반환하는 함수..
Algorithm/Python 2023. 8. 20. 00:37