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

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이 있는데 알면 빨리 풀고 모르는 고생하는

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

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

   알아야 풀지요.)

 

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