logo image
메인
기술
HOME
기술

알고리즘 생각, 여행사에서 여행 팀에대한 버스배분문제.

목록
#weblang
  • N개의 팀이 있음, 각 팀의 사람 숫자는 다를 수 있음
  • 하나의 버스는 최대 45명까지 탑승가능
  • 최소 필요한 버스수 B = 모든 사람수/45
  • 가능하면 같은 팀은 같은 버스에 타게하고싶음.

  • N개의 팀의 사람수 목록을 구한다.
    N[0]=3
    N[1]=12
    ...
    생긴 목록을 L이라고 한다.(L은 연관배열)
  • L을 사람수의 내림차순으로 정렬한다.
    N[1]=12
    N[0]=3
    ...
  • 이제 팀을 버스에 태우는데,
    L의 순서대로 팀을 버스에 태운다
    순서대로 각 버스에 한팀씩 순서대로 태운다.
    L[0]->B[0]
    L[1]->B[2]
    L[3]->B[3]
    L[4]->B[0]
    L[5]->B[2]
  • 이렇게 계속하다가 사람의 수가 넘치는 경우가 생긴다.
    그러면 그 버스의 다음 버스에 해당 팀을 태운다.
    모든 버스를 체크했지만 해당 팀이 들어갈 수 없을 경우
    해당팀을 잘라서 처리한다.
    하지만 사람수로 내림차순 정리하였기 때문에 이럴 가능성이 적어진다.
    L의 후반부의 팀들은 사람수가 적기 때문에 좀더 유연하게 버스 선택이 가능하다.

예
  • N = [20,3,2,30,10,8,8,12,9,9,8,7]
    총 인원 126명
    필요 버스수 = ceil(126/45) = 3대
  • B = array(45,45,45); // 버스 123호 각각 45명의 자리
  • L = [30,20,12,10,9,9,8,8,8,7,3,2] //사람수로 내림차순 정렬
  • 분배 알고리즘 동작
    • 버스1호에 30명이 탈 수 있다. B=[15,45,45]
    • 버스2호에 20명이 탈 수 있다. B=[15,25,45]
    • 버스3호에 12명이 탈 수 있다. B=[15,25,33]
    • 버스1호에 10명이 탈 수 있다. B=[05,25,33]
    • 버스2호에 09명이 탈 수 있다. B=[05,14,33]
    • 버스3호에 09명이 탈 수 있다. B=[05,14,24]
    • 버스1호에 08명이 탈 수 없다. B=[05,14,24] SKIP!
    • 버스2호에 08명이 탈 수 있다. B=[05,06,24]
    • 버스3호에 08명이 탈 수 있다. B=[05,06,16]
    • 버스1호에 08명이 탈 수 있다. B=[05,06,16] SKIP!
    • 버스2호에 08명이 탈 수 있다. B=[05,06,16] SKIP!
    • 버스3호에 08명이 탈 수 있다. B=[05,06,08]
    • 버스1호에 07명이 탈 수 있다. B=[05,06,08] SKIP!
    • 버스2호에 07명이 탈 수 있다. B=[05,06,08] SKIP!
    • 버스3호에 07명이 탈 수 있다. B=[05,06,01]
    • 버스1호에 03명이 탈 수 있다. B=[02,06,01]
    • 버스2호에 02명이 탈 수 있다. B=[02,04,01]
    • END
추가
  • 버스를 순서대로 돌리지 않고 그때 가장 자리가 많은 버스에 손님을 태우는 쪽이 더 효율적일 것 같다.
  • 분배 알고리즘 동작
    • [버스1호] 30명이 탈 수 있다. B=[15,45,45]
    • [버스2호] 20명이 탈 수 있다. B=[15,25,45]
    • [버스3호] 12명이 탈 수 있다. B=[15,25,33]
    • [버스3호] 10명이 탈 수 있다. B=[15,25,23]
    • [버스2호] 09명이 탈 수 있다. B=[15,16,23]
    • [버스3호] 09명이 탈 수 있다. B=[15,16,14]
    • [버스2호] 08명이 탈 수 있다. B=[15,08,14]
    • [버스1호] 08명이 탈 수 있다. B=[07,08,14]
    • [버스3호] 08명이 탈 수 있다. B=[07,08,06]
    • [버스2호] 07명이 탈 수 있다. B=[07,01,06]
    • [버스1호] 03명이 탈 수 있다. B=[04,01,06]
    • [버스3호] 03명이 탈 수 있다. B=[04,01,02]
    • END
코드로
  • N = array([~~~~~~~~~~~~~~~~]);
  • N_total = array_sum(N);//총 사람수
  • L = arsort(N); //php에서는 본래 반환값이 없지만 그냥.. 보기 쉽도록)
  • B = array();
  • for(i=0,m=ceil(N_total/45);i<m;i++){
    • B[]=45; //45명 탈 수 있는 버스를 추가
  • }
  • for(i=0,m=count(L);i<m;i++){
    • arsort(B);
    • temp_B = B[0]; //최고로 자리가 많은 버스의 자리수
    • if(temp_B>L[i]){
      • B[0]-=L[i];
    • }else{
      • countinue; //이 팀은 하나의 버스에 탈 수 없다.//에러 배열에 넣고 나중에 예외처리를 한다.
    • }
  • }

  • 복잡도.. 맞는가 모르겠지만
  • 6+{ceil(N_total/45)}+{count(L)*4}
  • 움.. 맞는건가.. 뭐 책뒤져볼 용기는 없고.
목록
댓글
  • / /
  • No Nickname
    No Comment
  • 권한이 없습니다.
    {{m_row.m_nick}}
    -
목록형 📷 갤러리형
제목
[기본형] HTML (with 부트스트랩5.3 , jquery 3.7, vue.js)
유용한 리눅스(LINUX) 명령어
[공지] 기술 게시판
일
월
화
수
목
금
토
4.28
4.29
4.30
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
swiper 에서 부모가 보이고 안보이고 할 때 슬라이드가 이상해지는 것 현상 방지 옵션.
5.11
5.12
5.13
5.14
css animation 테스트용
5.15
5.16
5.17
5.18
5.19
5.20
5.21
5.22
5.23
5.24
5.25
5.26
5.27
5.28
5.29
5.30
5.31
6.1
tag