Notice
Recent Posts
Recent Comments
Link
목록2023/06/05 (1)
HJW's IT Blog
Algorithm: 문제풀이 1
Subset Sum # n 개의 서로 다른 숫자가 주어져 있다. # 이 중 k개를 더했을 때, 정확하게 합이 S 가 되는것이 있는가 방법 1> Brute force 로 모든 조합을 해본다면 O(n^k *k) 시간이 걸린다 방법 2> n개의 숫자를 모두 정렬 >> 가장 큰 수와 작은수를 더했을 때 합을 구해본다 if (min + max S): max index - 1 방법3> 배열 D 생성 (D[n][k]) >> D[i][j]: 만약 정확하게 i개의 수를 가지고 그 합이 j가 되게할 수 있다면 1, 아니면 0 >> 다음 조건을 만족하는 a가 있다면 1 - D[i-1][j-a] = 1 이고 D[..
알고리즘
2023. 6. 5. 17:32