• 목록
  • 아래로
  • 위로
  • 3
  • joyfuI
  • 조회 수 146

알고리즘 수업 과제인데 으으 너무 어려웠네요. 근데 어제 새벽에 겨우 끝냈습니다. 성공하니까 희열이 장난아닙니다.(역시 이맛에 과제하지ㅎㅎ)



과제내용


n개의 서로 다른 양의 정수가 주어져 있음
각각의 집합의 합이 같도록 두개로 쪼갬
예를 들어 1,2,3이 있으면 1,2랑 3으로 쪼갬


두개의 집합으로 파티셔닝할 수 있는 경우의 수 출력
그리고 파티셔닝한 거 아무거나 한 개 출력

없으면 0 출력


예를 들어 입력이 {1,2,3,4,5,6,7}이면

경우의 수는

 {1,6,7}, {2,3,4,5}
 {2,5,7}, {1,3,4,6}
 {3,4,7}, {1,2,5,6}
 {1,2,4,7}, {3,5,6}
로 총 4개


정수의 개수는 1 <= n <= 1000

정수의 크기는 1 <= n <= 1500



처음엔 어떤 부분집합의 합이 전체의 절반이면 나머지 원소의 합도 전체의 절반이 된다는 점에서


재귀함수를 이용해 모든 부분집합을 구하고 그 합이 전체의 절반이 되는지 카운트하는 방식으로 만들었는데


시간복잡도가 2^n이라 숫자가 30개만 되도 30초나 걸리고 속도가 느려터졌더라고요.


결국 처음부터 다시 짜는데 교수님이 동적계획법을 사용하라는 힌트를 주셨어서 어제 하루종일 공부한 끝에 성공했습니다.


대신 램은 2GB나 먹는게 함정..ㅎㄷㄷ



짜잔~ 2초이내로 계산이 끝납니다.


어 근데 이제 과제가 몇 개 남았지

팀플 하나, (이것도 역대급 난이도) 과제 하나..., 이번 주에 팀플 하나 더 추가될 예정이고, 다음 주에 과제 2개 추가예정...

우웨에엑ㅠㅜ

댓글 3

BVC_Liper_Okbul
profile image

역시 코딩은 성공하면 엄청난 희열이...

안되면 열심히 고통을...

comment menu
2019.05.06. 15:01

신고

"BVC_Liper_Okbul님의 댓글"

이 댓글을 신고 하시겠습니까?

title: 황금 서버 (30일)humit
profile image

solve(index, N) 을 index부터 배열의 마지막까지의 원소를 활용해 N을 만들 수 있는 경우의 수라고 정의하면 solve(index, N) = solve(index + 1, N) + solve(index + 1, N - arr[index])가 되고 이 식을 동적계획법으로 구현하면 되지요. 물론 출력을 위해서 숫자의 사용내역을 추가로 저장을 하고요.

근데 숫자가 너무 크긴 하네요... 보통 n을 100 정도로만 주는데 말이지요.

comment menu
2019.05.06. 19:20

신고

"humit님의 댓글"

이 댓글을 신고 하시겠습니까?

joyfuI 작성자 → humit

넵 거기에 사용 내역도 추가 저장 필요없이 solve에 저장된 값들을 이용해서 추정 가능하더라고요.

comment menu
2019.05.06. 20:14

신고

"joyfuI님의 댓글"

이 댓글을 신고 하시겠습니까?

권한이 없습니다.
번호 제목 글쓴이 날짜 조회 수
공지 [1차 해결 및 추가] 서버 접속 불가 문제 안내 14 마스터 마스터 24.06.20.15:22 1207
공지 [작업 완료] 설 명절 맞이 서버 업데이트 안내 3 마스터 마스터 24.02.11.17:21 3227
공지 [중요] 호스팅 만료와 관련하여 일부 수칙이 변경됩니다. 4 마스터 마스터 23.01.14.02:23 6958
공지 낚시성 불법도박 홍보 게시글을 주의하세요. 9 image 네모 네모 22.08.09.18:13 1724
공지 슬기로운 포인트 벌이를 하는 법 (22.10.11 업데이트) 64 네모 네모 18.06.17.20:25 16385
1944 포인트 3만을 넘은적이 어쩜 없을까요? ㅋㅋ 11 모니터 모니터 18.03.01.13:04 215
1943 새로 들어오신 건 좋은데요... 8 국내산라이츄 국내산라이츄 18.03.30.00:35 215
1942 톈공-1 추락 7 title: 은메달도다 18.03.30.17:32 215
1941 독감입니다ㅠ 18 네모 네모 19.01.12.22:55 215
1940 정말 이번 생엔 연애하긴 글렀습니다. 15 국내산라이츄 국내산라이츄 19.02.07.23:05 215
1939 문제가 많은 회사 후기 14 국내산라이츄 국내산라이츄 19.12.27.00:05 215
1938 어우 지쟈쓰 새벽에 식겁했습니다. 10 국내산라이츄 국내산라이츄 23.03.08.23:41 215
1937 랭킹의 넘사벽 2 하루살이 title: 황금 서버 (30일)하루살이 16.07.15.18:27 216
1936 힉 잘보니 제가 포인트 1등이네요 5 하루살이 title: 황금 서버 (30일)하루살이 16.07.26.10:00 216
1935 사용 설명서 만들고 있습니다. 6 file 마스터 마스터 16.08.26.01:54 216
1934 드럽게 힘드네.. 9 에듀 title: 맛스타의 자물쇠에듀 17.03.12.16:40 216
1933 흠.. 아직 하루지만.. 이용 후기? 13 모니터 모니터 17.09.15.18:37 216
1932 와.. 오늘 가위 바위보는 정말.. 8 동그니동동 17.10.15.00:12 216
1931 오늘도 스포어 출첵은 정말로 아슬아슬합니다. 9 image Seia Seia 17.11.08.00:02 216
1930 스팀 연쇄 할인마의 유혹을 참지 못하고.. 16 image NoYeah NoYeah 17.11.26.17:04 216
1929 아, 드디어 출석 체크 순위권안에 들 수 있을거 같네요.. 11 Hanam09 Hanam09 17.12.01.23:49 216
1928 네 여러분 덱이 왔습니다 ㅇㅅㅇ 6 image 국내산라이츄 국내산라이츄 17.12.21.01:53 216
1927 코인하는 분들은 돈을 빼야 재산이 되는 건데.. 10 image NoYeah NoYeah 18.01.20.22:52 216
1926 128mb vps를 어디다 쓰죠 12 abnoeh abnoeh 18.03.30.11:07 216
1925 잠금장치를 변경했습니다! 13 image 네모 네모 18.05.03.17:33 216