알고리즘 문제를 풀 때 내가 갖추어야 할 자세

알고리즘 설계기법

• BruteForce
• Greedy
• BackTracking
• Divide & Conquer
• DP ( Dynamic Programming )

 

어떻게 풀까?

1. 문제를 보고 어떤 부류의 문제인지 파악
2. 시간복잡도를 생각해서 얼마나 걸릴지 파악
3. 연산 21억정도(int형 최대)면 1초안에 완전탐색이 가능하다.

 

삼성 역량테스트 (소프트웨어 검정 시험)

•   -  IM 1문제 1차원 배열, 단순 시뮬레이션
• A형 AD 2문제(3시간) 시뮬레이션 (최적화까지는 생각 안해도됨)
• B형 Pro
• C형 Expert

 

AD는 어떻게 나오나?

• BruteForce
• Greedy
• BackTracking
• Divide & Conquer

시뮬레이션 문제

재귀함수

DFS

BFS

멱집합 PowerSet (A라는 집합의 모든 부분집합을 구해라) : 반복문, 바이너리카운팅(가지치기 어려움), 재귀함수

순열

조합

이진탐색

정렬

문자열

트리

서로소 집합

등…

 

 

문제 풀이 순서

1. 어떤식으로 풀 것인지 절차를 작성

   해보는 것이 도움이 된다.

   처음에는 자세히 쓰더라도 어느정도 짬이 생기면 나만의 기호, 그림으로 간소화할 수 있다. 그러니 꼭! 꼭! 하자.

   • 입력은 어떻게 할 것인가?

   • 탐색은 어떻게 할 것인가?

   • 출력은 어떻게 할 것인가?

   • 다 정했다면... 그것과 관련된 코드는 모두 기억하고 있어야 한다! 자동으로 나와야 함

2.  절차 작성을 하고나면 그것을 코드로 옮길때 실수하는 공통되는 부분을 자주 발견할 수 있다.
   오답노트를 기록해 놓자.

3. 문제풀이 후 다른 사람과 아이디어 공유. 더 좋은 방법은 없나? 같은 생각을 꼭 해볼 것.
   얼른 풀었다고 끝내지 말고, 나와 다른 아이디어로 푼 사람의 풀이를 확인해보면서 경험을 쌓자!
   특히, BackTracking 문제를 풀 때 이런 것이 도움이 된다.