초보와 고수사이 넘사벽 중간쯤

지난편까지 점부터 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까지 뽑은것에서 위의 경우를 따져서 빼주는 것이 각 거울을 가로 세로 따지면서

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

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

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

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

휴가인데 평소보다 빨리 깬 아침이네요.

이번 편은 3차원 공간으로 표현된 문제에 대해서 이야기하겠습니다.

1. 3차원 공간의 단위 길이가 1인 6면체를 쌓고 막대를 꽂으면 막대가 지나간

   단위 6면체는 몇개인가?

2. 3차원 테스트리스 처럼 여러가지 다면체를 위에서 떨어뜨리면 최고 높이가 얼마가 될까?

3. 평면의 높이가 각각 다를 수 있는데 높이를 높이거나 낮출때 비용이 들어가는데

   갖고 있는 예산내에서 동일 높이가 되는 최대 정사각형의 넓이는?

4. 다면체 공간 표면상에서 특정 모양의 표면의 넓이나 특정 동작을 했을때 넓이나 위치는?

처음에는 같이 문제를 풀어보고 싶었는데 공간상, 시간상 할 수 없으니 이런 유사한 문제를

 온라인저지 사이트에서 찾아서 풀어보세요. 너무 어려운 것에 매달리지 말고

3차원 공간의 문제는 완전탐색도 중요하지만 공간상 생각하기가 쉽지 않기 때문에

2차원 문제보다 더 어렵게 생각할 수 도 있는데 이럴 때는 전개도로 펴서 보면 쉽게 풀수도 있습니다.

온라인 저지에 보면 많은 경우 대회용 문제라서 완전탐색으로 풀면 타임아웃이 나오니 너무 실망하지 말고

1. 부분점수만 받겠다라고 풀던가

2. 더 높은 수준으로 공부해서 Pass 하던가

3. 대회용이 아닌 문제만 풀던가

 입니다.

정말 고수가 되려면 2처럼 해야 하지만 목적에 맞는 공부를 하세요.

그래서 이 전편에서 이야기 한 것 처럼 보려고 하는 시험의 기출문제를 구해서

 유사?한 비슷한 수준을 공부하는 것이 중요합니다.

이게 딱 시험을 Pass 하는 방법이구요.

물론 압도적인 실력을 가지면 좋지만 그게 노력도 노력인데 너무 시간이 많이 걸려서 힘들지요.

어떤 분들은 매일 꾸준히 1문제라도 풀어야 한다고 하는 분도 있는데

방학때 한 동안은 하루종일 문제를 풀어 어느 수준을 넘는 것이 중요합니다.

뭐든 띄엄띄엄 시간이 쌓인다고 어느 레벨을 넘지는 못하는 것 같습니다.

몇 편인가에 엑셀에 정리하면서 풀라고 한 것 처럼 그 이후에는 가끔 손을 풀어주고

정리한 내용을 주기적으로 보면 실력이 어느 정도 유지 될 수 있을 것 같습니다.

전편에서 이야기한 완전탐색 도구코드(DFS/BFS/순열/조합)는 매일 한번씩 처보고요.

내가 전공이 전산이고 알고리즘과목도 우수한 성적으로 통과했고 텀프로젝트도 하고

동아리에서 안드로이드 프로그램도 짜서 얼마나 업무 역량이 높은데 떨어지겠어라고 생각하면

떨어집니다.

1. 온라인저지 시스템에 익숙하지 않고

2. 포장된 알고리즘 문제인 Problem Solving에 익숙하지 않으면

   손을 못댑니다.

그런 우수한 사람을 놓치면 회사도 아깝고

제 생각은 3시간 2문제 보다 1대1 면접이 훨씬 실력을 확실히 볼수 있고

온라인저지라면 쉬운 문제 부터 어려운 문제까지 더 긴 시간 동안 봐야 실력 검증이 확실할것입니다.

(당사자에게는 괴롭겠지만)

물론 신입사원에게 많은 것을 바라지는 않겠지만

다음편 부터는 어떤TIP들이 있나 생각해 보겠습니다.

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

2차원배열에서 완전 탐색을 한다면 어려가지 문제가 있을 수 있겠지만

1. NxN 배열의 좌상단에서 출발하여 우하단으로 도착할때

   갈 수 없는 길도 있고 아이템도 있어서 도착시에 최대 점수는

2. 배열에 0과 1이 흩어져 있을때 상하좌우로 붙어 있는 그룹은

   몇개로 분류할 수 있는가?

3. Cross Word 처럼 글자나 숫자가 있을때 행과 열을 선택했을때

   연결되는 단어가 단어 사전에 등록되어 있는 글자의 숫자는

4. 1초에 1명씩 옆의 사람에게 감염이 되는데

   특정 위치에서 감염이 시작한다면 모두 감염되는 시간은 몇초인가.

어렵지 않는 난이도이라도 문제는 정말 여러가지 만들 수 있습니다.

1번 문제는 고수들은 DP로 풀겠지만 초보는 순열/조합등으로 조금 높은 수준은

DFS로 풀수 있습니다.

2번은 DFS나 BFS로 풀수 있는데 꼭 BFS로 풀어야 합니다. DFS는 Stack 메모리를

계속 쓰기 때문에 N이 커지면 StackOverflow가 납니다. 그리고 이 문제는

Flood Fill이라는 알고리즘 주제와 연관이 됩니다.

3번은 행과 열에서 몇개씩 고르는 방법

4번 BFS의 여러가지 용도 (숙제, 인터넷 찾아보세요.)

결론적으로 13회에서 말씀드렸던 (중복)순열/(중복)조합에 DFS와 BFS는

자다가 깨서도 사용할 수 있어야 합니다.

(중복)순열/(중복)조합/DFS/BFS 를 하려면 재귀를 알야야 하는데

재귀로 다른 건 못해도 지금 말한 최대 6개의 코드는 꼭 외워야 합니다.

(이해가 아닙니다.)

아~ 그런데 그림과 상세 데이터도 없이 문제의 예를 설명하려니 힘든데

취준생들에게 도움이 되고 있는 것 맞나요?

재수생?들은 아실텐데 제가 바로 가고 있나요?

앞으로도 한동안 계속 연재?를 하겠지만 이것이 결론입니다.

완전탐색으로 표현할 수 있는 순열/조합/DFS/BFS 코드만 가지고도

수 많은 문제를 풀 수 있습니다.

그러니까 데스노트의 사신의 눈을 가지면 이름과 남은 생명이

보이는 것 처럼 문제를 보면 이것이 어떤 방법으로 하면 되겠다

라는 것이 보이는 눈을 갖는 훈련이 필요합니다.

+ 생각으로는 할 수 있는데 손이 안따라가는 경우가 많이 있습니다.

  생각으로 풀 수 있으면 손이 따라갈 수 있게 훈련

+ 각종 TIP이 있는데 알면 빨리 풀고 모르는 고생하는

+ 혹시 유명한 알고리즘의 예제를 보여 준다면 그것을 활용할 수 있는 능력

  (문제를 보고 주어진 문제가 어떤 유명한 알고리즘을 적용하면 되는지

   알아야 풀지요.)