송우석의 코딩 테스트 공부 블로그

• Big-O : 최악일 때 연산 횟수

  시간 복잡도

  파이썬은 1초에 2000만 번 ~ 연산을 수행

  O(logn) 여기서 log는 log2임 : log 100만 = log(1,000,000) = 19.9 < 20

  O(n)

  O(nlogn) → 20,000,000 < 2천만

  O(n^2)

  O(2^n)

  1,000,000 * log(1,000,000) = 19900000

  log(1,000,000) = 19.9

  • 사칙 연산 뿐 아니라 비교 연산도 한 번의 연산으로 취급한다.
  • 시간 제는 코드
    • import time
    • strart = time.time()
    • end = time.time()
    • end- start

• 출제 유형 파악

  구현, 그리디, dfs/bfs 가 가장 많이 나옴

  그 다음이 다이나믹프로그래밍, 정렬, 이진탐색

• 온라인 개발환경 리플릿 구축

  깃허브 연동

  

• greedy

  한 번 다시 풀어볼 것은 밑줄로 표시한다

  1,2,3,4

• 구현

  완전탐색 : 모든 경우의 수를 주저없이 다 계산하는 방법

  시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

  1(1), 1(2), 2, 3

• 메모리 제약사항

  • Pypy3 언어가 가능하면 python3보다 연산 속도가 빠르기 때문에 사용하자. python으로 제출해도 채점은 pypy로 하고 문법도 똑같다.

  128~512 MB

  int 자료형 데이터 갯수에 따른 메모리 사용량

  데이터 갯수(리스트 길이)	메모리 사용량
  1000	4KB
  1,000,000	4MB
  10,000,000	40MB

• continue 사용법

  • if 문 만족하면 해당 i에 대한 for문이 끝나고 다음 i로 넘어감
  • if 문 만족 안하면 밑에 print 실행함

  

• ord 함수 사용법

  문자열을 숫자로 바꿀 때 ord(’a’)