**코딩테스트 합격자 되기 파이썬편 1주차 스터디 내용을 정리해본다! 코딩 테스트 합격자 되기 - 파이썬 편
시간복잡도
보통 시간복잡도와 공간복잡도는 알고리즘의 성능을 나타내는 지표로써 쓰인다. 이때 공간복잡도보다도 시간복잡도가 주로 고려되야 할 사항인 것 같다.
시간복잡도는 보통 연산 횟수와 관련이 있어서, 나는 1번 연산이 들어갈 때 (변수에 값 할당, 또는 연산) 시간복잡도가 1이 늘어난다고 생각하며 계산한다. 따라서 내가 짠 코드에서 최대 n번 연산이 들어갈 때 시간복잡도를 O(n)이라고 표현한다. (빅오 표기법)
보통은 시간복잡도를 최악의 상황에서 도는 빅오 표기법을 사용하지만, 빅-세타 표기법(평균적인 경우)과 빅-오메가 표기법(최선의 경우) 또한 존재한다. 이것은 시간복잡도 계산 방식 자체는 비슷하고, 최선의 경우와 평균 경우를 고려하여 시간복잡도를 계산하면 된다.
빅오 표기법
빅오 표기법은 최악의 상황을 고려하기 때문에 계산이 간결해지는 경향이 있다. 만약 시간복잡도가 O(1n^2+2n-1)이라면 이 시간복잡도는 O(n^2)과 동일하다. 빅오는 최악의 상황을 고려하기 때문에, n이 무한히 커지는 상황(최악의 상황)을 고려한다. 따라서 무한히 커지는 n이 있을 때, 최고차항만 남기고 나머지 차수는 버려도 되는 것이다.
이는 아래 빅오 표기법의 수식을 보면 알 수 있다.
특정 x 시점 이후부터 항상 \(f(x) ≤ C * g(x)\)를 만족
C는 상수
따라서 \(n^2+2n-1<=C*n^2\)가 특정 n에서 만족되기 때문에 (여기서는 n=1부터 만족된다) 시간복잡도를 단순히 O(n^2)이라고 표현할 수 있다.
코딩 테스트 필수 문법
빌트인 데이터 타입
정수형(int), 부동소수형(float), 문자열 타입이 있음. 산술연산, 비교연산, 비트연산, 논리연산이 모두 가능함. 심지어 c에서는 math.h include 해야 가능한 abs도 가능함.
부동소수형에서는 엡실론을 주의해야함. 부동소수를 이진법으로 표현하는 과정에서 오차가 발생하기 때문인데, 이 오차 때문에 문제 통과를 못하는 경우도 있으므로 주의해야 한다.
컬렉션 데이터 타입
리스트(list), 튜플(tuple), 딕셔너리(dictionary), 셋(set), 문자열(string) 등이 있음. 특히 나는 리스트에서 중복 원소 제거할 때 for문 돌면서 막 지우지 말고 그냥 set변환 한번 했다가 다시 리스트로 변환하곤 했음.!
뮤터블 객체는 리스트, 튜플, 셋임. 따라서 뮤터블 객체를 다른 변수에 담고 수정하면 함께 수정이 됨. 따라서 .copy() 같은 걸 이용해서 복사해서 넣어줘야 같이 동시에 수정이 안됨. 이 외에 이뮤터블 객체들은 복사해서 넣어주지 않아도 동시에 수정이 안됨.!
리스트 슬라이싱, 딕셔너리 사용법은 내가 대충 알고 있으므로 따로 자세히 정리하지는 않겠음. !!튜플은 삽입, 삭제가 안됨.
리스트의 시간복잡도
- list.append() : 맨 뒤에 그냥 넣으면 되므로 O(1)
- list.insert(i, num) : i번째까지 가야하므로 O(n)
- list.pop() : 맨 뒤에 그냥 제거하면 되므로 O(1)
- list.remove(num) : num을 list에서 찾아내는데 걸리는 시간 O(n), 삽입 시간 O(1) => O(n)
- list.extend([list2]) : 맨 뒤에 list2 원소들을 하나씩 append 하므로 O(1)이 k번 => O(k)
- list[k] : 접근 자체는 상수 시간 O(1) (연결리스트는 O(n)으로 알고 있는데 그 리스트가 아닌 것 같다.?)
- list1+list2 : list.extend는 기존 리스트에 append하므로 O(k)였지만 얘는 새로 빈 리스트에 list1, list2원소를 모두 append하기 때문에 O(n+m)
- list(set(list)) : 시간복잡도가 O(n)
- k in list : k를 찾아서 존재여부를 리턴하므로 탐색 시 걸리는 O(n)
딕셔너리의 시간복잡도
딕셔너리는 리스트와 달리 탐색에 걸리는 시간이 모두 상수시간이다.
따라서 dic.get[key], dic[key], dic.pop(key) 모두 O(1).
셋의 시간복잡도
set은 add, remove, discard는 모두 O(1) 상수시간에 이루어진다. 나머지는
- set1.union(set2): O(len(set1)+len(set2)) (셋 안에 모든 요소를 흩으므로)
- set1.intersection(set2): O(min(len(set1), len(set2)))
- set1.difference(set2) : O(len(set1))
- list(set(set1)) : O(len(set1)) (모든 요소를 list에 append)
- k in set1 : 탐색은 O(1)
문자열의 시간복잡도
문자열은 내가 잘 모르는 문법도 있어서 좀 정리를 해보겠다. (ㅠ)
- str1 + str2 : O(str1+str2) 두 문자열을 더함
- delimiter.join(string_list) : O(총 문자열 길이) string list를 delimiter로 연결
- str.replace(old, new) : O(n) 특정 문자를 찾아 변경
- str.split(sep) : O(n) sep 기준으로 문자열 split (리스트 리턴)
- str.startswith(prefix) : O(len(prefix)) prefix로 문자열이 시작하는지 체크
- str.endswith(suffix) : O(len(suffix)) suffix로 문자열이 끝나는지 체크 (뒤에서부터 탐색)
람다식(함수)
람다식은 다음처럼 정의함! c에는 못 본 거라 내가 잘 쓸 줄 모름(ㅠ)
1 | |
람다로 간단하게 함수를 위처럼 정의하고 변수에 담아서 부를 수도 있고, 아니면 인수로 람다식을 넘기는 방법도 있다. 두번째를 오며가며 더 많이 본 것 같다..?
