NMF
NMF 음수미포함 행렬분해
다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.
관련 문제)
문제 설명
문제에서 숫자의 개수(N)는 최대 100 입니다.
쉽게 떠오르는 풀이는 각 연산의 자리에 + 혹은 - 를 넣을지 결정하여 2^(n-2) 번의 연산을 모두 하는 것입니다.
연산의 결과가 마지막 숫자의 값과 같은 경우의 수를 모두 Count 하면 됩니다.
그러나 이 방법은 시간 복잡도가 O(2^(n-2)) 이므로 시간 안에 모두 풀 수가 없는 풀이 방법입니다.
DP 방법을 이용하여
d[i][j]는 i번째 숫자까지 고려하였을 때 j가 되는 모든 연산 경우의 수
라고 정의하여 봅시다.d[i][j] = d[i-1]j-a[i]] + d[i-1]j+a[i]]
d[i][j] = (i-1의 결과에서 a[i]를 더하여 j가 되는 경우의 수) + (i-1의 결과에서 a[i]를 빼서 j가 되는 경우의 수)
따라서 이 방법을 사용하면 전체 시간복잡도는 K=20일 때
위의 점화식의 정의에 따라 Bottom-Up 방식으로 코드를 구현하여 보겠습니다.
구현 과정
n = int(input())
# N개의 숫자를 1~N 인덱스에 저장
a = [0]+list(map(int, input().split()))
d = [[0]*(20+1) for _ in range(n)]
# 1번째 숫자는 항상 고정으로 자기 자신이므로 1로 초기화
d[1][a[1]] = 1
# 2번째 숫자부터 N-1번째 (N번째 결과값 제외) 까지 연산 진행
for i in range(2, n):
for j in range(0, 20+1):
# + 연산
if j-a[i] >= 0 and d[i-1][j-a[i]] > 0:
d[i][j] += d[i-1][j-a[i]]
# - 연산
if j+a[i] <= 20 and d[i-1][j+a[i]] > 0:
d[i][j] += d[i-1][j+a[i]]
print(d[n-1][a[-1]])
문제의 설명이 잘 이해가 되지 않는다면 비슷한 구조의 코드를 가진 평범한 배낭(Kanpsack 알고리즘) 문제를 먼저 한 번 풀어보세요.
관련 문제 및 포스트)
전체 구현 코드
import sys
def input(): return sys.stdin.readline().rstrip()
n = int(input())
a = [0]+list(map(int, input().split()))
d = [[0]*(20+1) for _ in range(n)]
d[1][a[1]] = 1
for i in range(2, n):
for j in range(0, 20+1):
# +
if j-a[i] >= 0 and d[i-1][j-a[i]] > 0:
d[i][j] += d[i-1][j-a[i]]
# -
if j+a[i] <= 20 and d[i-1][j+a[i]] > 0:
d[i][j] += d[i-1][j+a[i]]
print(d[n-1][a[-1]])
NMF 음수미포함 행렬분해
PCA 주성분 분석(차원 축소)
주요 주제)
다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.
다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.
다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.
다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.
다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.
삼성역량테스트에서 출제되는 코테문제들의 경우 2차원 배열을 특정한 기준을 통해 회전시키는 문제가 자주 출제됩니다.
Introducing Python 처음 시작하는 파이썬[2판] 을 읽으면서, 몇 가지 헷갈리거나 새롭게 알게된 문법, 함수, 메소드들을 정리하려고 합니다.
f-문자열
Introducing Python 처음 시작하는 파이썬[2판] 을 읽으면서, 몇 가지 헷갈리거나 새롭게 알게된 문법, 함수, 메소드들을 정리하려고 합니다.
Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...
Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...
Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...
Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...
Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...
Component-Driven User Interfaces