프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #17

지난편까지 점부터 3차원 공간의 기본 문제를 소개했다면

이제 조금 복잡하게 모든 경우릐 수를 구하는 것에 대해 생각해 봅니다.

 

1. 장기에서 차가 2번 움직일 수 있는 경우의 수는 몇가지 인가. 

 

2. A그룹에 4명, B그룹에 4명, C그룹에 4명이 있다.

   그룹을 섞어서 3명을 뽑아서 팀을 만드는 조건은

 

3. 10개의 직사각형 거울중 3개를 거는 방법은 몇가지 인가?

   (거울은 가로/세로로 걸 수 있다.)

 

문제는 일단, 전처리 + 모든 경우의 수 + 조건 만족 확인 로 푸는 경우가 많은데

지금까지는 계속 모든 경우의 수를 찾는 연습을 하고 있습니다.

 

1. 궁쪽을 빼면 상하로 10칸 좌우로 9칸을 움직일 수 있네요.

    일단 막혀 못갈 수 도 있지만 일단 움직일수 있는 경우가 좌우/상하가

    따로 있다고 생각하지 말고 19π2 중복 순열로 한번에 계산 하는 것이 훤씬 편합니다.

 

    상,하,좌,우 중 하나 또 한번 상,하,좌,우 중 하나 를 고르면 너무 복잡해집니다.

    19π2를 의 모든 조건을 구하고 1~10까지는 상하의 좌표, 11~19까지는 좌우의 좌표로 생각

    차가 움직일때는 순서와 관련있으니 순열(중복)

 

2. 각 그룹을 따로 생각하지 말고 1~4까지는 A그룹, 5~8까지는 B그룹 이렇게 생각하고

    12C3의 모든 경우를 생각하면 되고, 한그룹에서 2명이나 3명이 나오면 안된다는 조건이 있으면

    일단 구한 12C3에서 해당 조건을 빼면 되고

 

3. 10C3을 고르면 될 것 같지만 직사격형 거울을 돌려서 거는 경우가 있으니 아예 거울의 형태가

    2가지라고 생각하면 쉽습니다. 그래서 20C3을 하여 모든 경우를 구하고

    1~10까지는 세로형태, 11~20까지는 가로형태, 1과 11은 하나의 거울을 거는 형태만 다르니

    함께 뽑을 수 없습니다.

    20C3까지 뽑은것에서 위의 경우를 따져서 빼주는 것이 각 거울을 가로 세로 따지면서

    뽑는 것 보다 훤신 쉽습니다.

   

 

기본 경우의 수는 공식으로 쉽게 뽑히는데 이런식으로 그룹을 만들어 놓으면

쉽게 보이지 않습니다. 이런 것을 잘 구분하는 것을 전편에서 사신의 눈이라고 표현했습니다.

 

#삼성_소프트웨어_역량_테스트