자유게시판

와아 역대급 과제 하나 끝냈습니다.

joyfuI2019.05.06 11:07조회 수 109댓글 3

  • 1
    • 글자 크기

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



과제내용


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개 추가예정...

우웨에엑ㅠㅜ

  • 1
    • 글자 크기
안녕하세요. 반갑습니다~ (by 비누) 안녕하세요 알로라이츄를 연성했습니다 (by 허니버터뚠뚜니라이츄)
  • 역시 코딩은 성공하면 엄청난 희열이...

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

  • 2019.5.6 19:20

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

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

  • @humit
    joyfuI글쓴이
    2019.5.6 20:14

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

댓글 달기

번호 제목 글쓴이 날짜 조회 수
공지 호스팅 신청이 다시 가능합니다.15 마스터 2019.04.18 773
공지 회원 전용 페이지가 생겼습니다.15 마스터 2018.03.20 6642
공지 슬기로운 포인트 벌이를 하는 법43 네모 2018.06.17 1878
4725 핏쨔15 네모 2019.05.11 97
4724 모나미에서 선물 받게 생겼습니다 ㅎㅎ34 협스 2019.05.10 199
4723 99 bottles of beer 응용버전-코끼리와 거미줄8 title: 커피허니버터뚠뚜니라이츄 2019.05.10 70
4722 github user search를 간단하게 구현해봤습니다.2 도토리묵 2019.05.10 72
4721 하루가 멀다하고 자꾸 계정이 막히네요ㅠㅠ17 슬기 2019.05.10 116
4720 갑자기 잡담11 협스 2019.05.09 113
4719 저는 HTML을 접한지가 생각보다 오래 되었습니다.7 title: 커피허니버터뚠뚜니라이츄 2019.05.09 95
4718 확실히 데이터 용량을 외부로 링크하니2 슬기 2019.05.09 102
4717 아구 트위터 계정 정지되니 멘붕오네요ㅠㅠㅠㅠ6 슬기 2019.05.08 135
4716 개인 다이어리 (하루만에 또) 근황6 title: 커피허니버터뚠뚜니라이츄 2019.05.08 135
4715 도박으로 포인트를 잃은 사람의 글입니다.4 혜임 2019.05.08 106
4714 식사20 네모 2019.05.07 204
4713 개인 다이어리 근황 title: 커피허니버터뚠뚜니라이츄 2019.05.07 95
4712 뭔가 쓰고 싶은데 쓰고 싶은 글이 없네용8 도토리묵 2019.05.07 105
4711 웹서버 해킹!6 유키시로 2019.05.07 127
4710 으어어 코감기...2 title: 커피허니버터뚠뚜니라이츄 2019.05.06 80
4709 안녕하세요. 반갑습니다~9 비누 2019.05.06 95
와아 역대급 과제 하나 끝냈습니다.3 joyfuI 2019.05.06 109
4707 안녕하세요 알로라이츄를 연성했습니다2 title: 커피허니버터뚠뚜니라이츄 2019.05.06 93
4706 고3이라고 대체휴일에도!2 유키시로 2019.05.05 125
이전 1 2 3 4 5 6 7 8 9 10... 238다음
첨부 (1)
이미지 2.png
29.9KB / Download 7
서버에 요청 중입니다. 잠시만 기다려 주십시오...