완전탐색 ) 1초 제한시간 기준을 통한 적용 여부 판별

작성일 In Views: Disqus:

코딩테스트 대부분의 문제에서 주어진 자료를 순회하여 답을 도출하는 경우가 많습니다. 이 때 어떠한 알고리즘으로 순회를 하여 문제에 접근하는 것이 좋을지 1초의 제한 시간 기준을 통해 판별하는 방법을 정리한 글입니다.

▪︎ 시간 복잡도를 고려한 기준 적용

대부분의 코딩테스트 시험의 시간 제한 조건은 1초~5초 내외입니다. 따라서 실행 시간을 1초 내로 줄이는 것을 목표로 문제에 접근하는 것이 코딩테스트를 준비하는 데 있어 합리적입니다.

테스트를 하는 각 서버의 CPU에 따라서 같은 코드라도 실행 시간이 천차 만별이므로 “엄격하게 시간 복잡도를 몇으로 해야된다”라고 규정하는 것은 어렵습니다. 그러나 관행적으로 10^8 이내의 시행 횟수를 1초 내외의 제한 시간을 통과한 것으로 인정하고 그에 맞게 설계를 하는 편입니다.

데이터를 순회하여 정답을 도출해야하는 문제에서는 제일 먼저 완전 탐색(Brute Force)을 고려합니다. 이 때 전체적인 풀이의 흐름을 그려보고 시행 횟수를 빠르게 판단해보는 것이 좋습니다. 10^8 이내의 시행 횟수로 정답 도출이 가능하다면 완전 탐색을 적용하고, 불가능하다면 다른 알고리즘을 고려해보아야 합니다.

▪︎ Example of Apply

Untitled

▫︎ 문제 접근

이 문제에서 우리는 총 3번의 순회가 필요합니다.

  1. 2번의 반복문을 통한 멘토 학생과 멘티 학생이 매칭
  2. 1번의 반복문을 통한 테스트 결과 순회

가장 먼저 완전 탐색을 고려하여 10^8 이내의 시행 횟수로 정답 도출이 가능한지 확인합니다. 제시된 입력 설명에서 최악의 시행 횟수 경우를 산정해보면 202010 입니다. 따라서 다른 알고리즘의 고려 없이 바로 완전 탐색을 적용 가능합니다.

▫︎ 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function solution(test) {
  let answer = 0;

  for (let i = 1; i <= test[0].length; i++) {
    for (let j = 1; j <= test[0].length; j++) {
      if (i === j) continue;

      let isMatched = true;
      for (let k = 0; k < test.length; k++) {
        if (test[k].indexOf(i) > test[k].indexOf(j)) {
          isMatched = false;
          break;
        }
      }

      if (isMatched) answer += 1;
    }
  }

  return answer;
}

▫︎ 시간복잡도가 충분하지 않다면

  1. 포인터 두 개로 두번의 순회를 한번으로 줄일 수 있다면 ⇒ 투포인터 사용
  2. 순회 내에서 배열의 조작 메서드의 O(n)의 시간복잡도를 그 이하로 낮추려면 ⇒ 자료구조 사용
    • 우선순위 큐 / 연결리스트
  3. 배열 탐색을 O(1)로 하고 싶다면 ⇒ 해시 (Map 함수) 사용
  4. 정렬된 데이터를 기준으로 답을 찾을 수 있을 것 같다면 ⇒ 이진 검색 사용

위의 예시들은 제가 코딩테스트에서 완전 탐색으로 접근할 때 시행횟수가 크다면 고려하는 다음 접근들입니다. 각 케이스 별 정리와 예시 문제 풀이는 알고리즘 카테고리 내 포스팅에서 확인하실 수 있습니다.