Algorithm/Dynamic Programming69 [파이썬] 프로그래머스 : 사칙연산 (레벨4) [파이썬] 프로그래머스 사칙연산 (레벨4) https://school.programmers.co.kr/learn/courses/30/lessons/1843 풀이 방향성 생각 분할정복 or State DP가 생각났다. 분할정복으로 풀이하면, 부분 구조의 최대값, 최소값이 필요하다. ()앞에 어떤 부호가 붙는지가 중요해서 부호 별로 메모제이션을 해줘야한다. 나는 각 현재 숫자에 영향을 줄 수 있는 - 개수가 몇 개 있는지, 현재 몇 번째 숫자를 연산중인지 2가지 상태를 기준으로 삼고 2차원 DP를 업데이트 했다. (-) 부호를 만나면 괄호를 열 수 있다. 숫자 앞에 열려있는 괄호가 홀수개면 (-) 홀수개가 있으므로 빼기, 짝수개면 더하기. 숫자 연산이 끝나면 열려있는 괄호 c개 중 0~c개를 닫을 수 있다... 2024. 4. 23. [파이썬] 백준 14728 : 벼락치기 (골드5) [파이썬] 백준 14728 : 벼락치기 (골드5) https://www.acmicpc.net/problem/14728 풀이 방향성 생각 냅색 기본문제 상한선이 주어진 무언가가 있을 때 최댓값을 찾는 문제 전체코드 N,T = map(int,input().split()) dp = [[0]*(T+1) for _ in range(N+1)] # T시간 썼을 때 얻을 수 있는 점수 최대값 for i in range(1,N+1): t,s = map(int,input().split()) for j in range(T+1): if j >= t: # max(현재 문제를 풀지 않는 경우 / 현재 문제를 푼 경우) dp[i][j] = max(dp[i-1][j],dp[i-1][j-t]+s) else: # 문제를 풀지 못하는 경.. 2024. 4. 8. [파이썬] 코드트리 : 코드트리 코딩 대회 (골드1) [파이썬] 코드트리 : 코드트리 코딩 대회 (골드1) https://www.codetree.ai/training-field/search/problems/codetree-coding-contest/description?page=33&pageSize=20 풀이 방향성 생각 모든 케이스를 탐색하기에는 힘들어보임. 경우의 수를 줄이기 위해서 리스트 -> dict 사용 (누가 풀었는지는 중요 x, 순서고려 x) dict 정보를 바탕으로 DFS로 탐색 전체코드 from collections import defaultdict as dd N,M = map(int, input().split()) infos = list(map(int, input().split())) # 최대 집중력보다 크면 x if max(infos) .. 2024. 4. 2. [파이썬] 백준 2186 : 문자판 (골드3) [파이썬] 백준 2186 : 문자판 (골드3) 2186번: 문자판 (acmicpc.net) 문제 풀이 방향성 생각 내리막길이랑 비슷한 문제. 전형적인 DFS + DP 현재 노드를 결정하는데 3가지 요소가 있다. x,y좌표, 현재 몇 번째 단계인지. 3차원 DP로 작성한다. 중복 경로를 체크해줘야한다. 방문 안했으면 -1, 방문 했는데 도달하지 못하면 0, 도달 가능하면 1 이상의 숫자로 카운팅 전체코드 H,W,K = map(int,input().split()) arr = [list(input()) for _ in range(H)] target = input() L = len(target) visit = [[[-1]*W for _ in range(H)] for _ in range(L)] dire = [(1.. 2024. 3. 18. 이전 1 ··· 4 5 6 7 8 9 10 ··· 18 다음
