[알고리즘] 복잡도(Complexity)와 알고리즘 문제 해결 과정

복잡도

• 알고리즘의 성능을 나타내는 척도
• 시간 복잡도 vs 공간 복잡도
  • 시간 복잡도
    • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미
    • 시간 복잡도 측정으로 필요한 연산의 횟수 얻을 수 있다.
    • 코딩테스트는 보통 시간 제한이 있으므로 효율적인 프로그램 작성이 필요하다.
  • 공간 복잡도
    • 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메로리를 차지하는지 의미
    • 공간 복잡도 측정으로 필요한 메모리의 양을 얻을 수 있다.
    • 코딩테스트는 다수의 데이터에 대한 효율적 처리를 요구하기 때문에 대부분 리스트(배열)을 사용해야함.
• 복잡도의 표기법
  • 빅오 표기법(Big-O Notation)

알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

결론

• 최대한 복잡도가 낮게 프로그램 작성할 것.
• 별 다른 언급 없으면 복잡도는 시간 복잡도를 의미함.

---

'이것이 취업을 위한 코딩 테스트다 with 파이썬' study

https://github.com/ndb796/python-for-coding-test

ndb796/python-for-coding-test