오블완13 [BOJ] Python 백준 상자넣기(1965) https://www.acmicpc.net/problem/1965 부분 수열 dp 문제와 매우 유사한 문제이다. 제일 긴 부분 수열 문제처럼 dp 테이블에 1씩 더해주면서 값을 늘려주고 최댓값을 찾으면 된다. 하지만, 마지막 본인 수까지 포함해야함으로 마지막에 max값에 +1을 해준다.import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))dp = [0] * Nfor i in range(N): for j in range(i): if s[j] 회고.부분 수열문제를 최근에 풀어 바로 풀 수 있었던것 같다. 만약 2개월 지난 후 본다면 풀 수 있을까 의문이다... 2024. 11. 26. [BOJ] Python 백준 가장 큰 증가하는 부분 수열(11055) https://www.acmicpc.net/problem/11055 DP의 대표적인 문제라고 할 수 있다. 여기서 주의할 점은 갯수가 아닌 값을 더해서 최댓값을 찾는 것이다.우선 dp 테이블을 s와 동일하도록 구성해주고, j 부터 i까지 가는 도중에 s[j] import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))dp = s[:]for i in range(N): for j in range(i): if s[i] > s[j]: dp[i] = max(dp[i], dp[j]+s[i])print(max(dp)) 회고.처음에 가장 큰 증가하는 부분 수열을 dp테이블 초기화 과정에서.. 2024. 11. 24. [BOJ] Python 백준 주사위 쌓기(2116) https://www.acmicpc.net/problem/2116 제한된 조건 내에 최대 값을 찾는 완전 탐색 문제이다.백트래킹으로 탐색을 진행했는데 이 코드에서 유심히 봐야할 코드는 조건문이다.조건에서 0와 5은 서로 반대편이므로 total 값에 사용될 수 없다.마찬가지로 [1, 3 ] [2,4]는 만약 위,아래 값을 마추는 주사위로 사용되었으면, 사용이 불가능한 인덱스가 되어버린다.즉, 이전 재귀함수에서 보내준 주사위 윗값이 같은 인덱스를 찾고 그 인덱스와 연관된 ([1, 3 ] [2,4], [0,5]) 값일 경우를 제외한 모든 값중 가장 큰값을 더한 후 다음 재귀로 넘겨주면 된다.import syssys.setrecursionlimit(10**5)input = sys.stdin.readlineN =.. 2024. 11. 22. [Progammers] Python 프로그래머스 모의고사(42840) https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 백트래킹을 이용한 완전 탐색 문제라고 생각했다.방문할 수 있는 던전의 최대값을 백트래킹을 통해 확인해본 뒤, 가장 큰 값을 반환하는 문제이다.max_value = 0def solution(k, dungeons): length = len(dungeons) visited = [False] * (length) def dfs(n, now, cnt): global max_value max_valu.. 2024. 11. 18. 이전 1 2 3 4 다음