[2강] 알고리즘 성능 평가

<이것이 취업을 위한 코딩 테스트다 with 파이썬>
강의를 듣고 정리하는 글입니다.

강의링크 2강. 알고리즘 성능 평가

---

📌 복잡도(Complexity)

• 복잡도 : 성능적인 측면에서의 복잡도
  - 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  - 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
  => 복잡도가 낮을 수록 좋은 알고리즘
  
  
  
  

📌 빅오 표기법(Big-O Notaiton)

• 가장 빠르게 증가하는 항만을 고려하는 표기법이기에 함수의 상한만을 나타나게 됨.
  - 극한의 개념으로 생각하면 더 쉬움.
  
  
  
  
  

📌 시간 복잡도 계산해보기 1

• 위 코드를 보면 array 배열에 들어 있는 값들을 모두 더해주는 계산이므로 배열의 값만큼 시간 복잡도가 생김.
  - 즉, 데이터의 개수 N(5개)에 비례할 것임.
  - 시간 복잡도 : O(N)
  
  
  
  

📌 시간 복잡도 계산해보기 2

• 모든 2중 for문의 시간 복잡도가 O(N^2)인 것은 아님.
  • 소스코드 내부적으로 다른 함수를 호출한다면 그것도 고려해야함.
• 어쨌든 통상적으로는 O(N^2)
  
  
  
  

📌 알고리즘 설계 TIP

• 채점 서버가 pypy를 지원하면 되도록이면 pypy로.
• pypy는 시간복잡도 측면에서 유리한데 때때로 c언어보다 빠르게 동작하는 경우도 있음.
  • 항상 그런 건 아님.
  • 파이썬 보다 느린 경우도 있기에 고려하면서 문제 풀자.
• 그래서 보통 파이썬으로 제출하고 시간, 메모리 초과가 되면 pypy로 해보는 방법으로 추천.
  
  

📌 🤔❓

O(N^3)의 알고리즘을 설계한 경우, N의 값이 5,000 넘는다면 얼마가 걸릴까?

• 5천을 3번 곱해서 나온 값 1250억이 연산 횟수.
  • 1초에 약 5천만번 정도의 계산을 처리할 수 있다고 하면 2500초 정도 걸림.
• 이런 식으로 어느 정도 시간을 예측해서 알고리즘을 설계하는 것이 중요함.
• 수행 시간 제한은 보통 1~5초 가량이라는 점을 유의하자.
  
  
  
  

📌 요구사항에 따른 적절한 알고리즘 설계

📌 수행시간 요구사항

• 데이터의 조건을 확인한 뒤에 수행 시간 제한 확인.
  • 즉, 수행시간 요구사항이 어느정도인지 정확히 캐치하는 것이 중요.
• 알고리즘을 설계하는 것은 많은 문제를 접해보면서 스스로 감을 찾아 가는 것이 좋음.
  
  
  
  

📌 알고리즘 문제 해결 과정

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

• 핵심 아이디어를 잘 캐치 하면 소스코드를 간결하게 작성할 수 있는 형태로 문제를 출제함.
• 소스코드를 먼저 작성하기 보다는 먼저 문제를 온전히 이해하고 어떤 식으로 코드를 작성해 나갈지까지 확실히 정리된 다음!!!! 코드를 작성하자.
  
  
  
  

문제를 처음 접했을 때, "나는 이 문제를 엄청 간결하고 창의적으로 풀 수 있다!!"고 스스로한테 확신을 가지고 문제를 푸는 것이 결과적으로 실수를 줄이고 실력이 빠르게 성장한다!!!!