읽기와 분석 (시간복잡도/공간복잡도 등)

읽기와 분석

• 문제를 읽을 때, 어떤 부분을 초점을 두고 읽어야 할까?
• 문제의 조건들을 추상화하는 연습
• 시간복잡도 / 공간복잡도 어림잡기

---

예제

1. 시간, 메모리 제한 확인
2. 입력의 범위 확인

---

시간복잡도

• 어떤 이유로 코드의 실행 시간이 오래 걸릴까? - 연산량
• 계산량은 어떤 값과 상관이 있을까? - 입력
• 입력을 보고 대충 시간을 계산할 수 있을까?

시간복잡도 2N

---

Time Complexity

• 연산에 따라 속도는 모두 같을까?
  • +연산, *연산은 같을까?
• 모든 연산을 Counting 할 수 있을까?
  • break 등의 생략은?
• 최악과 최선의 경우?
  • 수열과 정렬에서의 최악과 최선?
• Counting에 따른 실행시간은?
  • 서버와 컴퓨터의 속도차?

---

Big-O Natation

• 점근적 표기법 - 대충 계산
• 입력이 N일 때, 연산 횟수가 최악이 2N^2 + 4N 이라면
  N이 무한대로 커질 때, 증가에 미치는 영향은 가장 큰 항만 필요하다!
  계수를 다 떼기 / 뒤의 4N, 앞의 2
• O(N^2)

---

O(1) 예제

---

O(N) 예제

---

O(logN) 예제 - 이분탐색 (=업다운)

• 절반으로 쪼개서 본다. 3등분하여 본다.. 등 균등분을 볼 때 사용

---

표현법과 감

• Big-O notation은 점근적 표현법
• 시간과 공간 차원에서 각각 다를 수 있음 -> 시간복잡도, 공간복잡도
• 계산 + 시스템에 대한 감이 중요함
• 1초에 천만번 연산 까지는 대다수 가능, 1억 이상이면 불가능에 가깝다.

---

예제

• 1초 제한에 max(N)=10억 이므로, O(N)이상의 알고리즘은 모두 불가능

---

읽기와 분석 외전 - 본격적인 PS전 팁

입력과 초기화 팁

Map과 Comprehension

• 입력의 대표적인 사례
  • 수 / num = int(input())
  • 문자열 ( 문자 배열 ) / string = input() / char_list = list(input())
  • 배열 / lst = list(map(int, input().split()))
    
    • map(x,y) 는 x함수를 y원소에 모두 적용한 map 객체를 반환한다.
      나중에 char_lst 내용을 문자열로 만들고 싶다면 join 메서드 사용
• List 초기화는 comprehension 으로
  • comprehension - 파이썬에서 iterator 한 변수를 만들 때 사용
  • lst_1d = [0 for _ in range(N)]
  • lst_2d = [[0 for _ in range(N)] for j in range(N)]

---

에러 메세지

---

추상화와 기능분리

함수의 활용

---

가독성

조건문, 반복문, 함수 모두 줄일부분이 존재함

---

명명법

Snake(변수), Camel(함수), Pascal