본문 바로가기

728x90

알고리즘 문제 풀이/DP19

[백준] 2xn 타일링 1, 2 https://www.acmicpc.net/problem/11726 https://www.acmicpc.net/problem/11727 세트처럼 생긴 두 문제를 풀어보았다.쉬운 DP 문제라고 해서 덤볐는데 생각보다 빨리 못풀었다. 두문제 다 내가 몇년전에 다른 언어로 풀었던기 기록이 있던데그땐 어떻게 풀었나 모르겠다 ㅎㅎ 우선 두 문제 모두, 문제 풀이 방법은 못풀고 고민했던 시간이 아까울 정도로 아주 간단했다. n=1일 때부터 경우의 수를 모두 따져보고 점화식을 세우기만 하면 된다. 2xn 타일링의 경우,모든 경우의 수를 따져보면 이렇다.n=1 : 1가지n=2 : 2가지n=3 : 3가지 (= 1 + 2)n=4 : 5가지 (= 2 + 3)n=5 : 8가지 (= 3 + 5)...피보나치와 동일한 규칙이다... 2024. 11. 13.

[백준]10211번: Maximum Subarray https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 🐥 브루트포스로 푸는 방법도 있지만, 문제를 보자마자 DP가 떠올라서 DP 풀어보았다. - 지금까지의 부분배열의 최대 합을 저장할 dp배열을 만든다. - dp[0] = arr[0]으로 초기화한다. - dp[1] ~ dp[n]까지 채운다 - 매 인덱스마다 다음 두 가지 선택지가 생긴다. 1) 현재까지의 최대 합(dp[i-1])에 현재값(arr[.. 2023. 10. 18.

[프로그래머스]호텔 대실 https://school.programmers.co.kr/learn/courses/30/lessons/155651# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 어떤 방에서 마지막 손님이 퇴실 후, 청소까지 끝난 시간을 그 방의 available time이라고 하자. 각 방의 available time을 기록하기 위해 rooms 리스트를 만들었다. 손님이 들어갈 수 있는 객실이 있으면, 그 객실의 available time을 새로운 손님의 시간으로 update해준다. 없다면, 새로운 객실을 추가하고 available time을 기록한다. python .. 2023. 6. 22.

[프로그래머스]땅따먹기 https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(land): n = len(land) dp = [[0 for j in range(4)] for i in range(n)] for i in range(4): dp[0][i] = land[0][i] for i in range(1, n): dp[i][0] = land[i][0] + max(dp[i-1][1], dp[i-1][2], dp[i-1][3]) dp[i][1] = land.. 2023. 6. 10.

[프로그래머스] 멀리 뛰기 https://school.programmers.co.kr/learn/courses/30/lessons/12914# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 보자마자 dp로 풀었는데 제출하고 나서 다른 분들 풀이를 보니까 재귀로 푼 분들이 훨씬 많았다. 재귀로도 풀어봤는데 대부분의 테케에서 시간초과가 떴다. 문제 조건이 바뀌었나? 바뀌기 전에는 재귀로 풀어도 통과가 됐었나봄 제출 코드 (dp) def solution(n): dp = [0]*n dp[0] = 1 #1칸 if n >= 2: dp[1] = 2 #1칸 또는 2칸 for i in range(.. 2023. 5. 31.

[백준]1149번: RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 오랜만에 dp 문제! 문제 풀면서 dp라는건 알았지만,,, 자꾸 안 풀려서 다른 분들 풀이를 참고했다. 난 왜 이렇게 어렵지 ㅠㅠㅠ 풀이 ✅ dp 배열에 i번째 집이 빨간색인경우, 초록색인 경우, 파란색인 경우의 최소 누적 비용을 저장한다. 🐥 i번째 집이 빨간색인 경우 최소 누적 비용 = (i번째 집을 빨강으로 칠하는 데 드는 비용 ) + min( i-1번째 집이 초록색인 .. 2023. 5. 27.

이전 1 2 3 4 다음

728x90

티스토리툴바