재귀 (3) 썸네일형 리스트형 백준 합분해 2 13707 (c++) 문제 https://www.acmicpc.net/problem/13707 13707번: 합분해 2 첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다. www.acmicpc.net 오랜만에 c++로 문제 풀려고 풀어봤다. dp로 풀었기 때문에 점화식만 구하면 쉽게 풀 수 있는 문제였다. 재귀로 풀어서 좀 오래 걸린 것도 있고, 다른 사람들 코드 보니까 더 간단하게 풀기도 했다. 점화식은 다음과 같다. arr [k][n]으로 놓고 k개를 사용해서 n을 만들 수 있는 경우의 수를 구하면 된다. arr [k][n] = arr [k-1][0]+ arr [k-1][1].... arr [k-1][n] 이런 식으로 되는데 더하는 경우가 각각 마지막에 n, n-1, n-2..... asm (생각나는 대로 정리중) ZF, CF 등 여러 상태가 있는데 ZF는 연산 결과가 0이면 1이고 0이 아니면 0이 된다. CF는 연산 시 비트 올림이나, 비트 내림 발생 시 CF가 1로 set 됨 cmp는 두 operand의 차를 사용해서 비교하는 명령어 연산 결과는 저장 안 됨 차가 0이 되면 ZF가 1로 set 됨 test 명령어는 두 operand AND연산하는 거임 그래서 0인지 판별할 때 많이 함 똑같이 0이면 ZF가 1로 세팅됨 cmp는 두 operand가 완전히 같은지 판단할 수 있고 test는 두 operand가 모두 0인지 판단할 수 있다. test의 경우에는 두 operand가 0이 아닌 경우를 제외하고는 값을 단정 지을 수 없기 때문에 test eax eax 같은 형태로 사용하여 값이 0이 아닌지 파악할 때 씀.. 백준 2098 외판원 순회(python) 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 2 문제와 다르게 시간과 메모리 조건이 달랐기 때문에 비트 마스크 개념과 dp개념을 사용하여 접근한 문제입니다. 순회하면서 방문하는 노드의 상태를 비트의 형태로 표현해 주었습니다. 과정은 다음과 같습니다. 순회하면서 메모이제이션할 값들을 현재의 노드와 상태를 기준으로 저장해 주었습니다. 순회하면서 기존에 저장한 값이라면 dp 리스트에 저장된 .. 이전 1 다음