본문 바로가기

파이썬45

[Algorithm] 백준 1912 연속합 | 파이썬 (DP, Dynamic Programming) ※ 1912 연속합https://www.acmicpc.net/problem/1912 문제 해결 TIP현재값이 큰지, 이전 dp값과 현재값을 더한 값이 큰지 비교해야 한다. dp의 상태는 다음과 같이 변화한다. 최종 dp의 max값을 출력하면 된다.  전체 코드 n = int(input())number = list(map(int,input().split()))#number = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]dp = [-10000]*(n+1)dp[0] = number[0]for i in range(1,len(number)): dp[i] = max(dp[i-1]+number[i],number[i])print(max(dp)) 2024. 7. 10.
[Algorithm] 백준 18353, 이코테 병사 배치하기, 최장 증가 부분 수열 | 파이썬 (DP, Dynamic Programming) ※ 18353 병사 배치하기https://www.acmicpc.net/problem/18353 문제 해결 TIP최장 증가 부분 수열이란?예를 들어 다음 수열이 주어졌다고 하자.3 5 7 9 2 1 4 8위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.3 7 9 1 4 8 (5, 2 제거)7 9 1 8 (3, 5, 2, 4 제거)3 5 7 8 (9, 2, 1, 4 제거)1 4 8 (3, 5, 7, 9, 2 제거)위와 같이 일부, 혹은 전체가 오름차순인 수열을 '증가 부분 수열'이라고 한다. 그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다. 즉, 위의 수열의 집합에선 부분수열 3 5 7 8이 LIS이다. O(N^2) 알고리즘으로 구현할 수 있다. 새로운.. 2024. 7. 7.
[Algorithm] 프로그래머스 정수 삼각형 | 파이썬 (DP, Dynamic Programming) ※ 정수 삼각형https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 TIP우선 예제 입력에 대해 30이 어떻게 나왔는지 파악해보자. 맨 위인 7에서 부터 밑으로 내려가며 합해준다. 두 번째 줄은 가운데가 없고 양끝만 존재하므로 10, 15가 된다. 세 번째 줄부터는 바로 위(두 번째 줄)에서 얻을 수 있는 숫자가 2가지(왼쪽 10, 오른쪽 15) 경우의 수인 가운데가 존재한다. 이때, 더 큰 숫자인 16으로 교체가 된다. 이를 반복하여 알 수.. 2024. 7. 6.
[Algorithm] 이코테 금광 | 파이썬 (DP, Dynamic Programming) [문제]n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.만약 다음과 같이 3 x 4 크기의 금광이 존재한다고 가정합시다.가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) → (3, 2) → (3, 3) → (3, 4)의 위치로 이동하면 총 19만큼의 금을 .. 2024. 7. 6.
[Algorithm] 프로그래머스 멀리 뛰기 | 파이썬 (DP, Dynamic Programming) ※ 멀리 뛰기https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 해결 TIPn이 1일 때부터 생각해보자. dp[1] = 1, 2라면 1씩 2번, 2씩 1번 총 2이다. dp[3]은 (1,1,1),(2,1),(1,2) 3이다. dp[4] = 5, dp[5] = 8이므로 피보나치 수열이 떠오른다. 전체 코드def solution(n): if n == 1: return 1 else: dp = [0] * (n+1) .. 2024. 7. 5.
[Algorithm] 이코테 개미 전사 | 파이썬 (DP, Dynamic Programming) [문제]개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.{1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 .. 2024. 7. 3.
[Algorithm] 백준 1463, 이코테 1로 만들기 | 파이썬 (DP, Dynamic Programming) ※ 1463 1로 만들기https://www.acmicpc.net/problem/1463[문제]정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. ⓐ X가 5로 나누어 떨어지면 5로 나눈다.ⓑ X가 3으로 나누어 떨어지면 3으로 나눈다.ⓒ X가 2로 나누어 떨어지면 2로 나눈다.ⓓ X에서 1을 뺀다. 정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 1. 26 - 1 = 25 ( ⓓ)2. 25 / 5 = 5 ( ⓐ)3. 5 / 5 = 1 ( ⓐ) [입력 조건]첫째 줄에 정수 X가 주어진다.(1 [출력 조건]첫째 줄에 연산을 하는 횟수의 .. 2024. 7. 3.
[Algorithm] 백준 16234 인구 이동 | 파이썬 BFS ※ 16234 인구 이동https://www.acmicpc.net/problem/16234문제 해결 TIP모든 나라의 위치에서 BFS를 수행하여 인접한 나라의 인구수를 확인한 뒤에, 가능하다면 국경선을 열고 인구 이동 처리를 진행한다. visited 배열을 따로 두어 index를 확인하면서 더 이상 인구 이동을 할 수 없을 때까지 반복한다. BFS를 처리할 때 인구 분배를 같이 해나가는게 중요한 것 같다.   전체 코드 from collections import dequeN, L, R = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))#graph = [[50, 30], [2.. 2024. 7. 3.
[Algorithm] 백준 18405 경쟁적 전염 | 파이썬 BFS ※ 18405 경쟁적 전염https://www.acmicpc.net/problem/18405첫번째 문제 풀이 (시간 초과)문제를 보고 먼저 생각해낸 해결방법은1. 바이러스 번호 1번부터 graph에서 위치한 자리값을 position 배열에 저장한다.2. position 배열에서 하나씩 꺼내어 확산을 진행한다.N, K = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))S, X, Y = map(int,input().split())#graph = [[1, 0, 2], [0, 0, 0], [3, 0, 0]]dx = [-1,1,0,0]dy = [0,0,-1,1]def bfs(x,y,.. 2024. 7. 2.

티스토리툴바