📜 알고리즘/BOJ(백준)_Python

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 3020번을 풀어보겠습니다. 이 문제는 동굴을 통과하는 장애물들을 피하기 위해 최소한의 충돌 횟수를 계산하는 문제입니다. 석순과 종유석의 높이를 고려하여 최적의 경로를 찾아보겠습니다. 1. 문제 설명주어진 동굴의 높이와 장애물의 위치를 이용하여, 동굴을 통과할 때 최소한의 충돌 횟수를 계산하는 문제입니다. 석순과 종유석의 높이를 누적합 배열을 이용하여 최적의 경로를 구합니다. 2. 접근법 1. 입력받기: 동굴의 높이(H)와 장애물의 개수(N)를 입력받습니다. 2. 장애물 데이터 입력: 각 장애물의 높이를 입력받아 석순과 종유석을 구분하여 배열에 저장합니다. 3. 누적합 배열 초기화: 장애물의 누적합을 계산하여 저장할 배열을 초기화합니다. 4. 누적합 계산..

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 11660번을 풀어보겠습니다. 이 문제는 주어진 2차원 배열에서 여러 쿼리에 대한 부분합을 구하는 문제입니다. 좌표 (x1, y1)부터 (x2, y2)까지의 합을 빠르게 계산할 수 있도록 누적합 배열을 사용하여 문제를 해결해보겠습니다. 1. 문제 설명주어진 2차원 배열에서 여러 쿼리에 대한 부분합을 구하는 문제입니다. 좌표 (x1, y1)부터 (x2, y2)까지의 합을 빠르게 계산할 수 있도록 누적합 배열을 사용하여 문제를 해결합니다. 2. 접근법 1. 입력받기: 배열의 크기(N)와 쿼리의 개수(M)를 입력받습니다. 2. 그래프 입력받기: N x N 크기의 2차원 배열을 입력받습니다. 3. 누적합 배열 초기화: 누적합 배열(prefix sum 배열)을 초..

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2304번을 풀어보겠습니다. 이 문제는 주어진 기둥들의 위치와 높이를 이용하여 창고 다각형의 면적을 구하는 문제입니다. 문제 URL: https://www.acmicpc.net/problem/2304 1. 문제 설명주어진 기둥들의 위치와 높이를 이용하여 창고 다각형의 면적을 구하는 문제입니다. 기둥의 위치와 높이를 고려하여 전체 다각형의 면적을 계산합니다. 2. 접근법 1. 기둥의 개수를 입력받습니다. 2. 각 기둥의 위치와 높이를 입력받아 리스트에 저장합니다. 3. 가장 높은 기둥의 위치와 높이를 찾습니다. 4. 왼쪽에서 오른쪽으로 이동하며 면적을 계산합니다. 5. 오른쪽에서 왼쪽으로 이동하며 면적을 계산합니다. 6. 두 부분의 면적을 합산하여 최종 면..

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 1912번을 풀어보겠습니다. 이 문제는 주어진 수열에서 연속된 부분 수열의 합이 최대가 되는 값을 찾는 문제입니다. 문제 URL: https://www.acmicpc.net/problem/1912 1. 문제 설명주어진 수열에서 연속된 부분 수열의 합이 최대가 되는 값을 찾아야 합니다. 예를 들어, 주어진 수열이 [2, 1, -4, 3, 4, -4, 6, 5, -5, 1]인 경우, 최대 합을 갖는 연속 부분 수열은 [3, 4, -4, 6, 5]로서 그 합은 14입니다. 2. 접근법 1. 수열의 크기 n을 입력받습니다. 2. 수열을 입력받아 리스트로 저장합니다. 3. 누적 최대 합(prefix sum)을 이용하여 효율적으로 계산합니다: • 각 원소를 누적하면..

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2559번을 풀어보겠습니다. 이 문제는 주어진 온도 리스트에서 연속된 K일 동안의 온도의 합이 최대가 되는 값을 찾는 문제입니다. 문제 URL: https://www.acmicpc.net/problem/2559 1. 문제 설명주어진 온도 리스트에서 연속된 K일 동안의 온도의 합이 최대가 되는 값을 찾는 문제입니다. 주어진 온도 리스트에서 연속된 K일 동안의 온도의 합이 최대가 되는 값을 계산해야 합니다. 2. 접근법 1. 각 테스트 케이스마다 온도 리스트가 주어집니다. 2. 연속된 K일 동안의 온도의 합을 계산하여 최대값을 찾습니다. 3. 누적합(prefix sum)을 이용하여 효율적으로 계산합니다: • 온도 리스트의 누적합을 계산합니다. • 누적합을 이..