코딩 테스트 문제 분석 & 시간 복잡도 이해

오늘은 코딩 테스트 문제를 효과적으로 분석하는 방법과 시간 복잡도 개념에 대해 정리했다.

🔍 문제 분석 방법

1. 문제를 꼼꼼히 읽고 제약 사항과 테스트 케이스를 확인한다.
2. 입력 크기를 분석하여 적절한 알고리즘을 선택한다.
3. 핵심 키워드를 찾아 데이터 흐름과 극성을 파악한다.

💡 의사 코드 작성 연습

• 구현 전에 추상적인 수준에서 논리적으로 설계하는 습관을 들이기
• 문제 해결 과정을 순서대로 정리하는 것이 중요
• 예제) 성적이 60점 이상인지 판별하는 프로그램
  1. 입력받은 성적이 60점 이상인지 확인
  2. 60점 이상이면 "통과", 미만이면 "실패" 출력
  3. 충분한 테스트 케이스를 검토

⏳ 시간 복잡도 분석

• 알고리즘의 실행 속도를 정량적으로 평가하는 방법
• 시간 복잡도가 낮을수록 실행 속도가 빠름
• 절대 실행 시간 vs 시간 복잡도 측정 방법

📊 시간 복잡도별 최대 연산 횟수

시간 복잡도최대 연산 횟수 (N ≈ 1,000,000 기준)

O(N!)	거의 사용 불가 🚫
O(2^N)	약 200~300 정도까지 가능
O(N^2)	약 3,000~25,000 가능
O(N log N)	100만 이상 가능
O(N)	1000~2000만까지 가능 ✅
O(log N)	10억까지 가능 ✅

⏩ 제한 시간이 1초라면 연산 횟수가 2,000만을 넘으면 안 된다!

출처: https://hyungju-lee.github.io/hyungju-lee2022.github.io/computer_science/computer_science27/

 

✍️ 오늘의 깨달음

• 문제를 분석할 때 입력 크기를 먼저 확인하자.
• 의사 코드 작성 습관을 들이면 문제 풀이가 훨씬 쉬워진다.
• 시간 복잡도를 고려한 최적의 알고리즘을 선택하는 것이 중요하다.

🚀 앞으로 더 많은 문제를 풀면서 효율적인 문제 해결 능력을 키워야겠다!

 

📖 오늘 정리한 내용은 『프로그래머스 제공 100문제로 완벽 대비 코딩 테스트 합격자 되기 C++』을 참고하였습니다