코딩 테스트 응시언어를 Java로 바꿔보겠다고 다짐한지 얼마 되지 않아
다시 Python으로 돌아가야겠다는 생각을 하게 되었다.
사실 현생을 열심히 사느라, 코딩테스트 준비를 제대로 하지 않고 있었다.
최근, 나의 최측근인 친오빠(前 Android개발자, 現 Back-End개발자)와의 면담(?)을 통해
진지한 고민을 동반한 심경의 변화가 있었고 다시 본격적으로 코딩테스트를 시작하기로했다.
친오빠에게 한 고민상담 중 하나가 코딩테스트 응시 언어에 대한 선택이었다.
오빠의 대답은 "Python으로 준비해도 아무 상관없다." 였다.
"안드로이드 직무는 Java 혹은 Kotlin으로 언어가 제한되어 있는 기업이 꽤 많지않느냐"는 나의 반격에,
"언어가 제한되어 있다는 뜻은 일반적인 알고리즘을 묻는 코딩테스트가 아니라, 안드로이드 기술과 관련한 테스트일 것이다." 라는 대답을 들었고, 설득당해버렸다....
(실제로 Python으로 코테를 준비하던 시절, 한 기업에서 안드로이드 직무는 언어가 Java/Kotlin으로 고정되어있는 바람에 Python으로 응시가 가능한 데이터분석 직무의 코딩테스트를 응시한 적이 있었다. 오빠가 말한대로 코딩테스트라고 하기엔 데이터를 분석하는 코드를 짜는 테스트였던 기억이 있다.)
그렇게 나는 다시 Python으로 코딩테스트 준비를 시작하기로 결심했다.
다시 Python으로 코딩테스트를 응시하기로 결정한 이상, 코딩테스트를 준비하는데 있어 소소한 팁들에 대해 정리해봤다.
1. 리스트 초기화 시, 리스트 컴프리헨션을 활용하자.
# 1차원 리스트
array = [0] * 3
# 결과 : [0,0,0]
# 2차원 리스트 N * M
N, M = 3, 2
array = [[0]*M for _ in range(N)]
# 결과 : [[0,0], [0,0], [0,0]]
# 잘못된 예시
array = [[0] * M] * N
# 이유 : [0]*M의 리스트를 임의의 주소값을 갖는 객체로 인식하여, N의 길이만큼 참조하여 복사된 주소값을 갖게됨2. 시간복잡도를 숙지해두자.
- 먼저, 시간복잡도의 표기에 대해서 알아보자. 빅오 표기법(Big-O Notation)이란 가장 빠르게 증가하는 항만을 고려하는 표기법으로, 차수가 가장 큰 항만 남긴다.
- (성능 좋음) O(1) - O(logN) - O(N) - O(NlogN) - O(N^2) - O(N^3) - O(2") (성능 안좋음)
- 시간제한이 1초인 문제를 만났을 때의 일반적인 기준
- N의 범위가 500인 경우 : 시간복잡도 O(N^3) 이하
- N의 범위가 2000인 경우 : 시간복잡도 O(N^2)
- N의 범위가 100000인 경우 : 시간복잡도 O(NlogN)
- N의 범위가 10000000인 경우 : 시간복잡도 O(N)
- 리스트 관련 함수의 시간복잡도
| 함수명 | 사용법 | 설명 | 시간 복잡도 |
| append() | 변수명.append() | 리스트 원소를 하나 삽입할 때 사용한다. | O(1) |
| sort() | 변수명.sort() | 기본 정렬 기능으로 오름차순으로 정렬한다. | O(NlogN) |
| 변수명.sort(reverse=True) | 내림차순으로 정렬한다. | ||
| reverse() | 변수명.reverse() | 리스트의 원소의 순서를 모두 뒤집어놓는다. | O(N) |
| insert() | insert(삽입 위치 인덱스, 값) | 특정한 인덱스 위치에 원소를 삽입할 때 사용한다. | O(N) |
| count() | 변수명.count(특정 값) | 리스트에서 특정한 값을 가지는 데이터의 개수를 셀 때 사용한다. |
O(N) |
| remove() | 변수명.remove(특정 값) | 특정한 값을 갖는 원소를 제거할 때, 값을 가진 원소가 여러 개면 하나만 제거한다. | O(N) |
3. 입력 받는 방법의 여러가지로 익혀두자.
a = input() # 문자열 형태로 입력
b = int(input()) # int 형태로 입력
c = list(map(int, input().split())) #공백을 기준으로 입력
a, b, c = map(int, input().split()) #입력이 3개로 주어진 경우
# 입력을 빠르게 받는 경우
import sys
sys.stdin.readline().rstrip()
#입력 문자의 '\n' 줄바꿈 제외하고 입력
import sys
sys.stdin.readLine().rsplit()[0] #또는
sys.stdin.readLine().strip() #양쪽 공백 제거4. 유용한 표준 라이브러리를 알아두자.
- itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능 제공 (순열, 조합 라이브러리)
#permutations, combinations는 클래스이므로 객체 초기화 이후에는 리스트 자료형을 변경해야 함
#순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나타냄 nPr
#조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택함 nCr
#순열
from itertools import permutations
permutations(arr, 3)
#중복순열
from itertools import product
product(arr, repeat=2) #2개를 뽑는 모든 순열 구하기(중복 허용)
#조합
from itertools import combinations
combinations(arr, 2)
#중복조합
from itertools import combinations_with_replacement
combinations_with_replacement(data, 2)- heapq : 힙(Heap) 자료구조 제공 (일바적으로 우선순위 큐 기능 구현에 사용)
#우선순위 큐를 구현하는데 PriorityQueue 라이브러리보다 빠름
#파이썬에서 힙은 Min Heap이므로 O(NlogN)에 오름차순 정렬 가능
import heapq
def heapsort(iterable):
h = []
result = []
#모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, value)
#힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
#결과 : [0,1,2,3,4,5,6,7,8,9]- bisect : 이진탐색(Binary Search) 기능 제공
#정렬된 배열에서 특정 원소를 찾을 떄 효과적
from bisect import bisect_left, bisect_right
#bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 때 가장 왼쪽 인덱스 구하기
nums1 = [0, 1, 2, 3, 4, 5, 6, 7]
nums2 = [4, 5, 5, 5, 5, 5, 5, 6]
print(bisect_left(nums1, 5)) #5
print(bisect_right(nums1, 5)) #6
print(bisect_left(nums2, 5)) #1
print(bisect_right(nums2, 5)) #7- collections : 덱(deque), 카운터(Counter) 등 포함
#리스트 자료형은 삽입, 삭제에 O(N)이 걸리나 deque는 O(1)만에 해결
#pop, popleft, append, appendleft 제공
#Counter는 등장 횟수를 세어줌
from collections import Counter
Counter("hello world").most_common() #하면 딕셔너리형태로 ('이름', '빈도')순으로 내림차순 정렬됨
#결과 : [('l',3), ('h',1), ...]- math : 필수적인 수학적 기능 제공 (팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수, 상수 포함)
5. 그 외
num = "1"
print(num.isdigit()) #True #해당 문자가 숫자인지 아닌지 판별
alpha = "abc"
print(alpha.isalpha()) #True #해당 문자가 영문자인지 아닌지 판별
join() : '\n'.join(list) 하면 한줄씩 띄어쓰기하여 출력 ('구분자'.join(리스트) 형태로 사용)
#람다표현식(Lambda Express)
nums = [1, 2, 3, 6, 8, 9, 10, 11]
list(filter(lambda x : x%2==0, nums)) #filter(함수, 리스트)
map(lambda x : x**2, nums)
#[과 ,를 빼고 출력
arr = [[1,2], [3,4], [5,6]]
print(*arr) #결과 : [1,2] [3,4] [5,6]
#딕셔너리를 key, value 기준으로 내림차순 정렬
_dict = {"a":1, "n":12, "b":5, "c":3, "z":2}
sorted(_dict.items(), key=lambda x: x[0], reverse=True) #key기준
#결과 : [('z',2), ('n',12), ('c',3), ('b',5), ('a',1)]
sorted(_dict.items(), key=lambda x: x[1], reverse=True) #value기준
#결과 : [('a',1), ('z',2), ('c',3), ('b',5), ('n',12)]
#두가지 기준으로 정렬
list = [[3,4], [1,1], [1,-1], [2,2], [3,3]]
list.sort(key=lambda x: (x[0], x[1]))
#1 -1 / 1 1 / 2 2 / 3 3 / 3 4
참고사이트
'코딩테스트' 카테고리의 다른 글
| 코딩테스트 언어를 Kotlin으로 바꾼 이유(찐 최종) + 소소한 팁 (1) | 2023.08.10 |
|---|---|
| 코딩테스트 사이트, 그리고 알고리즘 공부 순서 (0) | 2022.09.05 |
| 코딩테스트 언어를 Java로 선택한 이유 + 소소한 팁 (0) | 2022.09.05 |