코딩테스트를 위한 컨닝페이퍼. Python Coding Test 시 유용한 자료구조 요약 및 활용 사례
자꾸만 망각하게 되는 코딩테스트 유형들. 자료구조 기준으로 요약을 정리하고, 활용 사례 및 예제를 정리해 보자. 코딩테스트 하루 전에 숙지해야할 내용들을 정리해 본다.
해시 (Hash)
Key-Value 쌍을 이용한 빠른 탐색
해시를 사용하는 대표적인 자료구조는 Dictionary 이다. 키-값 (Key-Value)를 사용하여 자료를 저장하는 해시(Hash) 중에서 Python에서는 Ditionary를 편하게 다루기 위해서 `Counter`, `defaultdict` 등의 라이브러리를 제공한다.
다음은 주어진 `단어배열` (Array of Words)에서 각 단어의 수를 세는 예제이다.
Counter()를 이용하면 아래와 같이 단순히 `Counter(array): --> dict`로 그 수를 세어 저장할 수 있다.
Counter() 는 Dictionary로써 뿐만 아니라 산술연산을 지원한다. 따라서 동일한 Key에 대한 산술이 가능하므로, 아래와 같이 Key값의 빈도수에 대한 차이를 `a-b`만으로 구할 수 있다.
from collections import Counter
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
a, b = Counter(input_val), Counter(input_val[:4])
print(a-b)
# Counter({'Python': 1, 'Code': 1, 'Test': 1, 'with': 1})
[ defaultdict ]
경우에 따라서는 `Counter()`가 아니락 직접 dictionary를 다루어야 할 때가 있다. 이 경우, dictionary를 생성하여 value를 계산하는데, 기본적으로 dictionary는 type이 지정되지 않기 때문에 `키-값 셋` (Key-Value 셋)의 초기화가 되어 있지 않다. 위처럼 단어수를 세는 예제의 경우 아래처럼 단순히 덧셈(Add)를 하여 처리 할 수 있다.
from collections import defaultdict
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
d = defaultdict(int)
for w in input_val:
d[w] = d[w]+1
print(d)
defaultdict를 사용하지 않고 Key값에 대한 초기화 없이 `dictionary[key]`를 사용하면 `Key Error`를 발생하게 될것이다. 이러한 경우 값이 없는 경우 초기화 해주는 코드를 추가해 주어야 하는데, defaultdict는 이 과정을 내부처리하도록 dictionary를 Class화 해둔 것이다. 편의성을 높이고, 에러발생율을 줄일 수 있다.
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
d = dict()
for w in input_val:
d[w] = d[w]+1
print(d)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-6-3c2a402366b9> in <module>()
2 d = dict()
3 for w in input_val:
----> 4 d[w] = d[w]+1
5 print(d)
KeyError: 'Hello'
[ No Library ]
만약 collection library들을 사용할 수 없고, 순수 Python만을 사용해야 한다면 다음과 같이 초기화 처리를 해 주어야 한다.
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
d = dict()
for w in input_val:
d[w] = d[w]+1 if w in d.keys() else 1
print(d)
# {'Hello': 2, 'World': 1, 'Python': 2, 'Code': 1, 'Test': 1, 'with': 1}
딕셔너리(Dictionary)는 Key들의 순서가 없기 때문에 Index로 접근할 수 없다. Key로만 접근 할 수 있기 때문에, dict.keys()를 사용해서 전체 Key값을 List화 할 수 있다. 그러나, 어느 문서에서는 `dict.keys()`를 사용하지 말고, [w for w in d] 형태를 사용할것을 권고하기도 한다. dict.keys() 대신 dict변수이름 자체를 사용하면 key값을 반환한다.
그러나 위 예제에서 `w in d.keys()`는 list로 변환한다. 이 이야기는 해시의 장점인 Key-Search를 사용하지 않고 Full Search를 사용했다는 이야기가 된다. 즉 복잡도 O(n)이 추가 되는 과정이므로 위 전체 연산은 O(n^2)이 되어 버린다. 해시를 사용한 의미가 없다. 따라서, 위와 같은 예제는 해시의 키 값을 바로 사용하도록 아래와 같이 수정되어야 한다.
# Hash의 Key 초기화 : w in d.keys() ==> List로 변경되기 때문에 Hash Key Search를 사용하지 못하는 예
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
d = dict()
for w in input_val:
d[w] = d[w]+1 if w in d else 1
print(d)
# {'Hello': 2, 'World': 1, 'Python': 2, 'Code': 1, 'Test': 1, 'with': 1}
line 5 : `d[w] = d[w]+1 if w in d else 1` 으로 Hash Key 사용. 전체 Full Search 보다는 복잡도 감소
dict.get()
해시 키를 검사하는 `w in d` 와 유사하게, dictionary의 함수 get()을 활용할 수도 있다.
# Hash의 Key 초기화 : dict.get() 사용
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
d = dict()
for w in input_val:
d[w] = d.get(w,0)+1
print(d)
# {'Hello': 2, 'World': 1, 'Python': 2, 'Code': 1, 'Test': 1, 'with': 1}
dict.get(key, default) : dictionary에 key값을 반환한다. key값이 없으면 default를 반환한다.
[ 추가 문제 ]
각 단어별로 위치의 Index들을 저장하는 Dictionary를 반환하라. : dictionary ==> {word : [ index 1st , index 2th, ... ] } ex) {"Hello": [0, 3] , "Python" : [2, 7] , ... }
from collections import defaultdict
input_val = ["Hello", "World", "Python", "Hello", "Code", "Test", "with", "Python"]
d = defaultdict(list)
for i,w in enumerate(input_val):
d[w].append(i)
print( d )
# {'Hello': [0, 3], 'World': [1], 'Python': [2, 7], 'Code': [4],
# 'Test': [5], 'with': [6]})
스택/큐 (Stack/Queue)
스택 (Push/Pop), LIFO/FIFO, 큐 (Queue)
DeQueue
from collections import deque
dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산
프로그래머스 스택/큐 - 기능개발 문제 풀이
def solution(progresses, speeds):
answer = []
dq, s = [x for x in progresses], speeds
while( len(dq)>0 ):
r = 100-dq[0]
div, remainder = r//s[0], r%s[0]
nTimes = div if remainder==0 else div+1
# update deploy of all functions
dq = [x + nTimes*s[ti] for ti, x in enumerate(dq) ]
# check if finish of each dev. and save the result into stack
stack = []
for ti,x in enumerate(dq):
if x >= 100:
stack.append(ti)
else:
break
c = len(stack)
answer.append( c )
dq, s = dq[c:], s[c:]
return answer
힙 (Heap)
Heap은 이진트리 구조로써, 최소값 최대값을 쉽게 구하기 위하여 특정 조건이 적용된 트리이다. Heap 을 이용한 우선순위 큐
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.
A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
매칭된 갯수가 동일 (max치가 여러개)일 때 인덱스로 정렬하여 제출하는 것만 유의하면 크게 문제될것이 없다.
def solution(answers):
answer = []
n = len(answers)
s1 = [1, 2, 3, 4, 5] * (n//5+1)
s2 = [2, 1, 2, 3, 2, 4, 2, 5] * (n//8+1)
s3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * (n//10+1)
s = [s1[:n], s2[:n], s3[:n] ]
c = [0,0,0]
for i,x in enumerate(answers):
c = [ c[j]+1 if x-s[j][i]==0 else c[j] for j in range(3)]
m = max(c)
d = [x for x in zip(c, [1,2,3])]
e = [x[1] for x in d if x[0]==m]
return sorted(e)
이분 탐색 (Binary Search)
python
완전탐색은 너무 오래걸려. 효율적으로 값을 찾아보자.
깊이/너비 우선 탬색 (DFS/BFS)
python
탐색 방식 : 깊이 우선? 너비 우선?
( 작성중 )
탐욕 알고리즘 (Greedy Algorithm)
로컬 최적이 전체 최적이 되는 경우
로컬에서 주어진 데이터에서 최적을 선택을 하고, 전체로 확대 한다.
이 때 주어진 list 등에서 추가(Insert)하거나, 제거 (remove)하면, 전체 List가 변하기 때문에, 반복문에 영향이 가지 않도록 유의 해야 한다. 대표적으로, 다음과 같은 명령어가 있다고 하면,
for x in y:
if x>5: y.remove(x)
for문이 y의 원소인데 중간에 y의 원소를 추가 삭제하면, Loop가 정상적으로 동작하지 않는다.
체육복이 도난당함. 체육복을 보유한 학생만 수업에 참석 가능. 최대 수업참석 학생수를 구하는 문제
n : 전체 학생수
lost : 체육복을 잃어버린 학생 인덱스(array)
reserve: 여벌의 체육복 보유 학생의 인덱스 (array)
여벌의 체육복이 있는 학생들이 빌려줄 수 있음. 여벌의 체육복이 있는 학생 (reserve)는 자신의 앞번호/뒷번호만 빌려줄수 있음
여벌의 체육복을 보유한 학생이, 또다른 한벌을 도난당했을 수도 있음. 이 경우 다른 사람에게 빌려줄 수 없음
def solution(n, lost, reserve):
answer = 0
lost.sort()
reserve.sort()
lost_self =[]
rs = reserve.copy()
for r in rs:
if r in lost:
lost.remove(r)
reserve.remove(r)
for r in reserve:
if (r-1 in lost):
lost.remove(r-1)
continue
elif (r+1 in lost):
lost.remove(r+1)
continue
return n-len(lost)
동적 계획법/다이나믹 프로그래밍 (Dynamic Programming)
반복되는 계산은 줄인다....
동적 계획법이 활용될 수 있는 경우는, 수열로 표현이 되는 경우이다.
즉, `X(t) = X(t-1) + X(t-2)` 등과 같이 반복적으로 표현 되는 경우라 할 수 있다.
대부분 Recursive 형태로 표현이 가능한 경우, 동적 계획법을 사용하면 효과적이라 볼 수 있다.
기본적으로 동적 계획법은 동일한 연산이 반복 되기 때문에, 1) 이러한 연산을 미리 저장 (Memoization) 해 놓고 이를 참조해서 사용하는 방법, 2) 혹은 Recursion을 사용하는 방법으로 나뉜다.
다음은 프로그래머스의 동적계획법 (Dynamic Programming) 문제중, "정수 삼각형" 문제의 풀이이다.
아래로 한칸씩만 이동할 수 있다. 즉, 바로 아래 왼/오른쪽 숫자 둘중 하나로만 이동이 가능하다.
아래와 같은 삼각형을 표현할 때 입력을 Array: [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
정삼각형의 꼭대기에서 바닥까지 이어지는 경로중 최대값 찾기 문제 (동적계획법)
이 문제는 다음과 같은 식으로 표현이 가능하기 때문에 동적계획법을 사용하기에 최적 문제이다.
r행, c열 위치에서 최대값은, r+1행의 c열과, r+1행 c+1열의 값에 의존한다. 현 위치의 값인 triangle[r][c]는 고정된 상수이다.
따라서, r행 c열에서의 최대값은 다음과 같이 정의할 수 있다. t[r][c] = triangle[r][c] + max( t[r+1][c] , t[r+1][c+1] )
단, 초기 값은 설정을 해 주어야 한다. t[ 마지막행] [ 각 열 ] = triangle[마지막행] [ 각 열]
따라서, 위 내용을 코드로 표현하면 다음과 같이 표현 할 수 있다. 차이점이 있다면, 삼각형의 밑변부터 위로 올라오며 계산한 부분만 차이라 할 수 있겠다.
def solution(triangle):
answer = 0
t = [ [0]*len(x) for x in triangle ]
nRows = len(triangle)
for r in range(nRows)[::-1]:
# print(f' - {r}th : {t}')
for c in range(r+1):
if r==nRows-1:
t[r][c] = triangle[r][c]
else:
t[r][c] = triangle[r][c] + max(t[r+1][c], t[r+1][c+1])
return t[0][0]
댓글 영역