# dynamic programming
[백준] 1912 - 연속합
문제 풀러가기 주의 공부를 한 이후 스스로 풀이한 것을 적어둔 게시물입니다. 치팅 행위에 대한 책임을 지지 않습니다. 풀이 가장 큰 연속합을 구하는 알고리즘을 구하는 문제다. 문제에서 제시한 조건은 > 1개 이상의 수를 무조건 포함하기 > 수열의 원소 개수 n은
(Swift) Programmers 가장 큰 정사각형 찾기
코딩테스트 연습 - 가장 큰 정사각형 찾기 문제 풀이 아이디어 🚫 Brutal Force 맨 처음에 문제를 풀 때는 row, column의 최댓값이 1,000 정도이므로 아래와 같은 코드로 정사각형을 최대 크기부터 하나하나 찾으면서 푸는 방법을 사용했는데요. 정
백준 1956
문제Floyd-Warshall 알고리즘 사용간선이 양방향일 수 있다.또, INF 값이 크기 때문에 2번 더하면 int 범위 상 음수되어버림예외처리 필요 (거리가 INF인 간선일 때는 최단거리 갱신하지 않도록)처음에는 disti에 0을 저장한 뒤 나머지 dist의 요소를
10844: 쉬운 계단 수
문제를 보고 맨 뒷자리 수를 기준으로 2차원 dp table로 해결해야겠다고 생각함dpi는 i자리 계단 수의 맨 뒷자리수가 j인 경우의 수이고, i자리 계단 수가 성립되는 경우의 수는 for j in range(10): dpi += dpi이다.맨 뒷자리 수가 0인 경우
15990: 1, 2, 3 더하기 5
1차원 table로는 규칙이 전혀 보이지가 않음예를 들어 4를 1, 2, 3 세 수의 합으로 표현 -> 1+2+1, 1+3, 3+1같은 수가 연속해서 올 수 없으며, 덧셈의 순서를 구분함같은 수가 연속해서 올 수 없기 때문에 덧셈 표현에서 끝나는 수에 초점을 맞춘다면
백준 11404
문제다익스트라 알고리즘은 하나의 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이것을 확장시켜,모든 두 지점 간의 최단 경로를 모두 구하고 싶을 때Floyd-Warshall 알고리즘을 쓸 수 있다고 함.모든 두 노드 간의 최단 경로를 구해야하므로 DP로 사용
16194: 카드 구매하기 2
dpi가 카드 i개 살 때의 최소 금액이라고 두고 규칙을 구해보면,dpi = min(dpi. dpi-j + card_packj)의 점화식을 구할 수 있음dp table을 max(card_pack)으로 초기화기저 -> dp0 = 0; dp1 = card_pack1
11052: 카드 구매하기
처음에 짠 코드각 카드팩의 weight 값을 가격에 (N / i)를 곱하는 방식으로 구함weight값이 가장 큰 카드팩을 살 수 있는만큼 모두 구매 (N // 카드팩에 들어있는 카드의 개수. 이하 max_index + 1)N을 N % (max_index + 1)로 up
11727: 2*n 타일링 2
규칙을 찾아보면 dpi = dpi-1 + dpi-2\*2의 점화식을 구할 수 있음bottomup 방식으로 코드를 작성함기존에는 dp table을 1001까지 0으로 초기화해서 생성했는데, 이렇게 하니까 런타임 에러 (indexError)가 발생함python list에선
백준 1949
문제'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.선정되지 못한 마을에 경각심을
(Swift) Programmers 스티커 모으기(2)
코딩테스트 연습 - 스티커 모으기(2) 문제풀이 아이디어 문제의 유형 자체는 DP에서 많이 본 문제입니다. i번째까지의 스티커를 떼었을 때의 최대값을 dp를 통해 0부터 구하고 마지막 스티커의 최댓값까지 구했을 때 그 값을 리턴하면 됩니다. i번째 스티커까지의 최댓
백준 2533
문제깊이 우선 탐색(DFS)으로 DP를 계산DP에는 해당 노드까지의 최소 얼리어답터 수를 저장한다.그러면 각각의 노드에서는, 무조건 아래의 두 경우 중 하나이다.1) 해당 노드가 얼리어답터일 경우 무조건 자식 노드가 얼리어답터2) 해당 노드가 얼리어답터가 아닐 경우 자
백준 2213
문제어떠한 트리의 임의의 노드 정점은(풀이에서는 간편함을 위해 첫 번째 노드라 함)최대 독립집합에 포함되거나, 안되거나 무조건 두 경우 중 하나포함을 1, 미포함을 0으로 나타냄1번째 노드부터 깊이우선탐색(DFS)dpi : i번째 노드를 루트노드로하는 서브트리에서, 최
프로그래머스 연속 펄스 부분 수열의 합
오답 어디가 잘못된걸까? 정리해보자. 입력 리스트를 받아서 1에서 시작하는 펄스를 곱한 값을 pulse에 저장한다. itertools 모듈의 accumulate 함수를 사용해서 누적 합을 구하고, 그 중 가장 큰 값의 인덱스와 값을 저장한다. 구한 인덱스까지 다시
세상에서 가장 쉬운 알고리즘 정리 4.동적프로그래밍 방법(Dynamic programming)
주요용어 동적 프로그래밍(dynamic programming) : 문제의 크기가 작은 소문제에 대한 해를 테이블 저장해 놓고 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법 최적화 문제(optimization problem) : 주어진
백준 15681
문제R을 루트노드로 갖는 트리에서,N + 1 번째 노드를 루트노드로 가지는 서브트리의 정점의 개수 저장(인덱스를 0부터 썼기 때문에 +1을 해주었다)node + 1 번째 노드를 루트노드로 갖는 트리의 각 정점들에 대해 각 정점을 루트노드로 갖는 서브트리의 정점의 개수를
