DP
-
[프로그래머스] - 풍선 터트리기Algorithm/프로그래머스 2022. 9. 21. 01:54
문제 [프로그래머스] - 풍선 터트리기 https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으..
-
[프로그래머스] - 거스름돈Algorithm/프로그래머스 2022. 9. 15. 16:21
문제 [프로그래머스] - 거스름돈 https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러..
-
[프로그래머스] - 등굣길Algorithm/프로그래머스 2022. 9. 7. 15:42
문제 [프로그래머스] - 등굣길 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 ..
-
[Algorithm] - LIS(최장 증가 부분 수열)Algorithm/Algorithm 2022. 9. 5. 13:57
LIS 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열 E.g) [3, 5, 7, 9, 2, 1, 4, 8] 부분 수열 -> [3, 7, 9, 1, 4, 8] / [3, 5, 7, 8] / [1, 4, 8] 길이가 길면서 원소가 증가하는 최장 부분 수열-> [3,5,7,8] 알고리즘 1. DP 각 원소를 돌면서 현재 원소보다 작은 값들(DP) 중 가장 큰 값에다가 연결 각 원소를 돌때마다 하위 원소들에 대해서 완전 탐색이 필요하여 O(N^2) 시간 복잡도 #Init dp = [0]*(n+1); for i in range(n) : for j in range(i) : dp[i] = max(d..
-
[Algorithm] - DPAlgorithm/Algorithm 2022. 9. 1. 22:30
DP(Dynamic Programming) 동적 프로그래밍으로, 큰문제를 작은 문제로 나누어 푸는 문제이다. Devide & Conquer과 비슷하지만, DP는 작은 문제로 나누어 반복되는 것을 이용해가면서 푸는 것이다. 반복되는 작업을 푸는 것은 Recursion으로 풀이가 가능하지만, 반복되는 작업을 또 하기보다 값을 저장하여 두고 다시 재사용하는 방식으로 푸는 것이 특징. ( Memoization) 대표 문제 Fibonacci / Knapsack problem 아래 그림과 같은 형태로 재귀로 풀이가 가능하지만, 매번 재귀로 풀이시 동일한 값을 또 사용할 수 있다. BOJ 2293번 각 Data에서 단계를 나누어 가능한 경우의 수를 늘려준다. idx 0 1 2 3 4 5 6 7 8 9 10 (k) d..
-
[프로그래머스] - 피보나치 수Algorithm/프로그래머스 2022. 7. 19. 23:07
문제 [프로그래머스] - 피보나치 수 https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = ..
-
[BOJ] 2482번 - 색상환Algorithm/BOJ 2022. 6. 13. 22:15
[BOJ] 2482번 - 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 연속되어 있는 색은 추가가 불가능 단계별 갯수를 세가면서 추가 -> DP DP를 나타낼 때 DP[i][j] 시 i는 색의 갯수 / j는 색을 고를 수 있는 경우이다. 1. i가 1인 경우에는 모두 n의 갯수에 맞추어 증가한다. 2. 후에 i가 2부터는 경우의 수를 나타내다 보면 DP[i][j] = DP[i-1][j-2] + DP[i][j-1] 로 계산식이 되는 것을 알 수 있다...
-
[BOJ] 11660번 - 구간 합 구하기 5Algorithm/BOJ 2022. 6. 11. 14:00
[BOJ] 11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 알고리즘 구간 합을 미리 DP로 구하여 둔 다음에 해당되는 행 영역의 합을 구하여준다. 계산상 편의를 위해 2차원은 N+1로 적용하였다. 코드 #BOJ 11660번 import sys input = sys.stdin.readline answer = [] n , m = map(int,input().split()..