코딩테스트 엣지 케이스 - 완전 탐색

코딩 테스트에서 "완전 탐색(Brute Force)"이 불가능한 경우를 어떻게 알까?

➡ 시간 복잡도를 기반으로 연산 횟수를 계산하면 알 수 있습니다.

💡 핵심:

• 컴퓨터는 1초에 약 10^8 ~ 10^9(1억 ~ 10억)번 연산을 수행 가능
• 따라서 "최악의 경우 연산 횟수" 를 계산하여 1억을 넘으면 비효율적인 알고리즘이라고 판단할 수 있음
• 완전 탐색(Brute Force) 이 가능한지 시간 복잡도를 계산하여 결정해야 함

- 삼성 제외 일반적인(?) 코테 문제들의 시간 제한은 1초이기 때문에 1억이내(10^8)의 연산으로 끝내야 함

- 1억 이상의 완전 탐색을 요구하지 않음

 

🚀 1️⃣ 연산 횟수에 따른 알고리즘 선택 기준

연산 횟수	시간 복잡도	알고리즘
N ≤ 10	O(N!) (팩토리얼)	완전 탐색 가능 (순열, 백트래킹)
N ≤ 20	O(2^N) (지수)	백트래킹, 비트마스킹 가능
N ≤ 1000	O(N^3) (삼중 루프)	플로이드-워셜, DP 가능
N ≤ 100,000	O(N log N)	정렬, 세그먼트 트리 가능
N ≤ 10^7	O(N)	투 포인터, BFS/DFS 가능
N > 10^8	O(N^2) 이상	완전 탐색 불가능

🔎 예제:

• N = 10^5이면,
  • O(N^2) = (10^5)^2 = 10^10 → 불가능!
  • O(N log N) = 10^5 log(10^5) ≈ 10^6 → 가능!
  • O(N) = 10^5 → 가능!

---

🔍 2️⃣ 예제별 연산 횟수 계산 방법

💡 예제 1: O(N^2)인 경우 (N = 100,000)

N = 100000
count = 0
for i in range(N):  # O(N)
    for j in range(N):  # O(N)
        count += 1  # 총 N^2번 실행
print(count)  # 10^10 연산 → 시간 초과!

➡ 10^10 연산이면 1초에 절대 불가능 🚨
➡ **"이중 루프는 N이 10^5 이상이면 불가능"**을 기억!

---

💡 예제 2: O(N log N) (정렬)인 경우 (N = 100,000)

arr = [i for i in range(100000)]
arr.sort()  # O(N log N) = 약 10^6 연산 (정렬은 가능!)

➡ "정렬(O(N log N))은 N이 100,000이면 충분히 가능!" ✅

---

💡 예제 3: O(2^N) (백트래킹)인 경우 (N = 20)

def backtracking(idx, N):
    if idx == N:
        return
    backtracking(idx + 1, N)  # 2^N 연산

N = 20
backtracking(0, N)  # 2^20 = 약 10^6 (가능)

➡ 2^20 = 1,048,576 → 가능하지만, N=30이면 10^9이므로 불가능! 🚨

---

🎯 3️⃣ 코딩 테스트에서 실전 적용하는 방법

1. 입력 크기(N)를 확인한다.
   • N ≤ 10 → 완전 탐색(백트래킹, 순열) 사용 가능
   • N ≤ 100 → O(N^3)까지 가능
   • N ≤ 100,000 → O(N log N)까지 가능
   • N ≥ 10^8 → O(N^2) 이상이면 절대 불가능!
2. 시간 복잡도를 계산하여 최악의 경우 연산 횟수를 예측한다.
   • N = 100,000이면 O(N^2) = 10^10 → 불가능
   • N = 1,000,000이면 O(N log N) = 10^7 → 가능
   • N = 20이면 O(2^N) = 10^6 → 가능
3. 알고리즘을 선택한다.
   • O(N!), O(2^N): 백트래킹, 순열 (N ≤ 20)
   • O(N^3): 플로이드-워셜, DP (N ≤ 1000)
   • O(N log N): 정렬, 이분 탐색, 세그먼트 트리 (N ≤ 100,000)
   • O(N): BFS/DFS, 투 포인터 (N ≤ 10^7)

---

🎯 4️⃣ 실전 문제 예제

(예제 1) N = 100,000일 때, 어떤 알고리즘을 선택해야 할까?

• O(N^2)은 불가능 (10^10 연산)
• O(N log N) 또는 O(N) 알고리즘을 찾아야 함
  ✅ 정렬(O(N log N)), 이분 탐색(O(N log N)), 투 포인터(O(N)) 사용 가능

---

(예제 2) N = 10이면 완전 탐색 가능할까?

• O(N!) = 10! = 3,628,800 → 가능 ✅
• O(2^N) = 2^10 = 1024 → 가능 ✅
• N ≤ 10이면 "완전 탐색" 가능!

---

(예제 3) N = 1000일 때

• O(N^3) = 10^9 → 제한 시간이 1초면 위험 🚨
• O(N^2) = 10^6 → 가능 ✅
  ✅ 플로이드-워셜(O(N^3)), DP(O(N^2)) 가능!

---

✅ 결론: 연산 횟수 예측 & 시간 복잡도 활용

1. "1초 ≈ 10^8 연산 가능"을 기억!
2. "최악의 경우 연산 횟수"를 계산해서 판단
3. N이 크면 O(N log N), O(N), O(log N) 알고리즘을 찾아야 함
4. N이 작으면 (N ≤ 10, 20, 100) 완전 탐색(백트래킹, 순열) 가능

✅ 이제 코딩 테스트에서 "완전 탐색이 가능한지" 빠르게 판단할 수 있을 거예요! 🚀

 

나의 말:

T(-1,000,000,000 ≤ T ≤ 1,000,000,000) 이면?

 

ChatGPT의 말:

📌 T(-1,000,000,000 ≤ T ≤ 1,000,000,000) 이면 어떻게 판단할까?

---

🚀 1️⃣ T의 범위를 보고 연산 횟수를 예측

• T의 최대값이 10억(1,000,000,000 = 10^9)
• 즉, T는 최대 10억 개의 서로 다른 값을 가질 수 있음
• 따라서, 입력값이 아니라 "연산 횟수"를 고려해야 함

---

🔍 2️⃣ T에 대해 가능한 알고리즘 판단

시간 복잡도	최대 T 값	가능한가?	설명
O(T!)	N ≤ 10	❌ 불가능	10! = 3,628,800 (10억 초과)
O(2^T)	T ≤ 30	❌ 불가능	2^30 = 약 10억 (한계)
O(T^3)	T ≤ 10^4	❌ 불가능	10^12 연산 필요 → 불가능
O(T^2)	T ≤ 10^5	❌ 불가능	10^10 연산 필요 → 불가능
O(T log T)	T ≤ 10^7	❌ 불가능	log(10^9) ≈ 30 → 3 × 10^8 연산 필요 → 불가능
O(T)	T ≤ 10^8	❌ 불가능	10^9 연산 필요 → 불가능
O(log T)	T ≤ 10^9	✅ 가능	이진 탐색 (log_2(10^9) ≈ 30)

---

🔎 3️⃣ 결론: O(log T) 알고리즘을 사용해야 함

💡 T가 최대 10^9이므로 완전 탐색 (O(T), O(T^2), O(T log T))은 불가능
✅ 따라서 O(log T)인 "이진 탐색"이 유력한 해결 방법!

---

🎯 4️⃣ 실전 예제 적용

(예제 1) T 안에서 특정 값 X를 찾는 문제

❌ 완전 탐색: for T in range(-10^9, 10^9): → 10억 번 연산 → 시간 초과 🚨
✅ 이진 탐색: while left <= right: → log(10^9) ≈ 30번 연산 → 가능! 🎯

💡 코드 (이진 탐색 예제)

def binary_search(T):
    left, right = -10**9, 10**9
    while left <= right:
        mid = (left + right) // 2
        if mid == T:
            return True  # 찾음
        elif mid < T:
            left = mid + 1
        else:
            right = mid - 1
    return False  # 없음

T = int(input().strip())
print(binary_search(T))  # O(log T) = 약 30번 연산으로 해결 가능

✅ 10억 개의 범위를 탐색해야 할 때는 이진 탐색이 정답! 🚀

---

(예제 2) T 범위에서 최댓값을 찾는 문제

• 최댓값 찾기 문제 (O(N)) → 불가능! (10^9 연산 필요)
• 이진 탐색 (O(log N)) → 가능! (log_2(10^9) ≈ 30)

---

🎯 결론

✅ T가 10^9이면 O(log T) 이하의 알고리즘을 사용해야 함
✅ 즉, 이진 탐색 (Binary Search) 또는 로그 연산이 들어간 알고리즘이 필요
✅ 완전 탐색(Brute Force)은 절대 불가능! 🚨
✅ 이제 T ≤ 10^9 같은 조건이 나오면 바로 이진 탐색을 떠올릴 수 있음! 🚀