이 문제 풀면서 궁금했던 점: 공유기 1개가 몇개까지 커버치는지가 궁금했는데 문제 방향이랑은 크게 상관이 없음 이분 탐색으로 풀어야겠다는 생각은 못하고 각 공유기의 지점을 포인터로 지정해야 하나 생각함 -> 근데 이래 버리면 포인터가 공유기 개수만큼 있어야 하니까 안됨 -> 완전 탐색으로 풀어야 하나 생각함 -> 시간이...?????????되나 ➡ N = 200,000, C = 200,000일 때,➡ 가능한 공유기 간 거리(gap)의 최대값은 1,000,000,000 (10억)➡ 완전 탐색(O(N * max_gap))으로 해결하려면 최악의 경우 200,000 * 10^9 = 2 * 10^13결론: 최대, 최소 거리 문제의 경우 시간복잡도를 계산해보고 완전 탐색 안될거 같으면 이진탐색으로 가자...for ..
코딩 테스트에서 "완전 탐색(Brute Force)"이 불가능한 경우를 어떻게 알까?➡ 시간 복잡도를 기반으로 연산 횟수를 계산하면 알 수 있습니다.💡 핵심:컴퓨터는 1초에 약 10^8 ~ 10^9(1억 ~ 10억)번 연산을 수행 가능따라서 "최악의 경우 연산 횟수" 를 계산하여 1억을 넘으면 비효율적인 알고리즘이라고 판단할 수 있음완전 탐색(Brute Force) 이 가능한지 시간 복잡도를 계산하여 결정해야 함- 삼성 제외 일반적인(?) 코테 문제들의 시간 제한은 1초이기 때문에 1억이내(10^8)의 연산으로 끝내야 함- 1억 이상의 완전 탐색을 요구하지 않음 🚀 1️⃣ 연산 횟수에 따른 알고리즘 선택 기준 연산 횟수시간 복잡도알고리즘N ≤ 10O(N!) (팩토리얼)완전 탐색 가능 (순열, 백트래킹..