ttobaegi / coding-test Goto Github PK

• 하나 하나 다 탐색하면서 답에 도달하지 못하거나 도달하지 못할 거 같으면 다시 검색이 덜 끝난 지점으로 돌아와서 답이 나올 때까지 계속 진행한다.
• 모든 경우의 수를 고려하는 방법, 완전 탐색을 하는 알고리즘에 가지치기/메모이제이션을 통해 탐색 시간을 단축한다.

공간복잡도

• 주어진 메모리 공간을 고려해야한다.
• 스택은 계산하기 어려우므로 변수는 전부 전역변수로 하고 재귀함수는 1000번 이상 호출하지 않도록 한다.
• 변수별 메모리크기를 고려
• int 형은 4바이트, 1,000 = 4kb, 1,000,000 = 4mb, 10,000,000 = 40mb. 보통은 백만이하로 할당한다.
  • 2차원 배열일때는 [1000][1000] 이하로 한다. [10000][10000] 은 400mb 이기 때문이다.
• long long 은 8바이트, char, bool 은 1바이트 이다.

시간복잡도

• 주어진 입력을 토대로 루프나 재귀를 얼마나 쓸수있는지 추측해야 한다.
• 보통 1억번을 계산하는데 1초가 걸림
• Big-O 표기법을 이용해 O(~) 로 표현함
• O(1), O(N), O(NlgN), O(N^2), O(N^3), O(2^N), O(N!) 순으로 복잡도가 증가한다.
• 1초당 가능한 연산수(대략 외우기 쉽게)
• O(1)
  • 배열 접근
• O(N) : 1억
  • 단순계산, 배열구간합 계산시
• O(lgN) : 많이할수있다(1억을 넣어도 26.57 정도가 나옴)
  • N을 절반으로 계속 나눔
• O(NlgN) : 5백만
  • N을 절반으로 계속 나누지만 각 depth 별 계산합이 N을 유지할때, 머지소트
• O(N^2) : 1만
  • 2중 for 문
• O(N^3) : 500
  • 3중 for 문
• O(2^N) : 25
  • 부분집합(포함하거나 안하거나)
• O(3^N) : 15
  • 각 요소별로 상태가 2개 이상인 부분집합
• O(N!) : 11
  • 크기가 N 인 순열
• 재귀호출 계산방법
• T(N) = aT(N/b) + N^k*lg^p N
  • a 와 k 중에 어떤것이 더 영향이 있는가?, 한번 호출될때마다 k가 얼마나 영향이 있는가?
  • b 가 클수록 a는 영향력이 약해지고, k 는 강해진다.
  • a 와 b^k 의 관계가 존재
    • a > b^k : a 의 영향력이 크다. k 의 영향은 무시됨 -> N^logb a
    • a = b^k : 둘다 고려해 주어야 한다. -> N^logb a * lg^p+1 N
    • a < b^k : k 의 영향력이 크다. -> N^k * lg^p N
• MH 문제에서는 N^2 까지는 시간복잡도가 나올 수 있으나 그 이상은 안나오는 것으로 보인다.

포기할 줄 알기

30분동안 고민해보고 모르겠으면 모법답안을 보자.

많이 풀어볼 수록 감이 온다.

• MH 문제를 최소 10문제 이상 풀어서 유형을 확인한 후 도전하도록 하자. (난이도 편차가 큼)
• 약한 유형의 문제는 백준온라인저지 사이트에서 찾아서 감이 올때까지 풀어본다.

오답노트를 만들자.

문제 접근 방법

1. 무식하게 풀수있는 방법으로 생각해보자
2. 무식하게 풀었을 때의 시간복잡도를 계산해보자
3. 풀 수 있으면 쉽게 코딩할 수 있는 방법을 고민해보자.
   1. 진법을 활용할 수 있는가?
   2. 누적합을 활용할 수 있는가?
   3. 몇 차원 배열을 쓰는 것이 좋을까?
4. 무식하게 풀 수 없을 때는 시간복잡도를 줄일수 있는 방법을 고민해보자
   1. 캐시를 만들 수 있는가?
   2. 더 이상 확인하지 않고 리턴할 수 있는가?
   3. 정렬을 쓸 수 있는가?

동적 프로그래밍

큰 문제를 작은 문제로 나누고 작은 문제의 결과를 사용해 큰 문제를 푸는 문제 해결 방법

• 작은 문제의 결과를 반복해서 구하는 것을 피하기 위해 메모이제이션(memoization) 을 사용한다.
  • 재귀와는 달리, 작은 문제의 결과를 저장한 것을 불러오는 것으로 메모리는 사용하지만, 실행 속도에서 매우 큰 장점을 가진다.
• 최소/최대, 경우의 수를 구하는 문제인 경우, 거의 DP로 해결 가능하다.

동적 프로그래밍 구현 방식 : Bottom-up, Top-down

1. 크루스칼(Kruskal) 알고리즘