IT/알고리즘 (9) 썸네일형 리스트형 [DP]집합의 분할 인적성을 공부하는 친구가 단체 톡방에 노가다 말고 순열공식이 없냐고 물어봤다. 해당 문제는 자연수의 분할 문제이다. 문득 작년 알고리즘 경진대회에서 집합의 분할 / 자연수의 분할 문제를 못풀어서 부들부들했던 기억이 새록새록 났다. 동적 계획법(DP)문제인 건 알았지만 끝내 점화식을 세우지 못했다. 1. 집합의 분할(partion of set)이란? 위의 문제는 같은 종류의 쿠키 10개를 나누는 문제이다. 하지만 집합의 분할은 서로 다른 쿠키 10개를 나누는 문제와 같다. 예를 들어 {1,2,3}은 다음과 같이 총 5개의 분할이 생긴다. 1|2|3 1|2,3 1,2|,3 2|1,3 1,2,3 이를 기호로 표현하면 S(n,k) n개의 원소를 k개의 집합으로 분류한 수를 의미한다. 저 위의 집합을 기호로 표현.. 이전 1 2 다음
