파이썬을 무기로, 코딩테스트 광탈을 면하자!
1. 해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수
문제는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/42576
자료구조와 알고리즘의 선택
- 만약 이름 대신 번호가 주어졌다면?
-> 선형 배열(linear array)
사람의 이름은 문자열이기 때문에 배열은 너무나 많은 크기의 공간이 필요하다. 참가자의 이름이 20개 이하의 알파벳 소문자이기 때문에 최악의 경우 26^20의 배열을 필요로 할 수가 있기 때문이다(?)
해시(Hash)
- key와 value를 연결해주는 함수를 hash function이라고 하며 각각의 key와 value의 연결을 담고 있는 저장위치를 hash table이라고 한다. 또한 서로 다른 key가 같은 value를 가리키는 경우를 충돌collision이라고 부른다.
문제의 풀이 및 알고리즘의 구상
- participant = ['mislav', 'stanko', 'mislav', 'ana']
completion = ['stanko', 'ana', 'mislav']
return = 'mislav' - participant의 원소들을 키 값으로 등장한 숫자를 카운트 한 밸류를 연결한 해시를 만들어주고 competion의 원소들의 키 값이 등장할때마다 앞선 해시의 밸류 값을 빼주다보면 해시의 원소들 중 단 하나만이 밸류가 1이 남게된다.
코드 작성
def solution(participant, completion):
d = {}
for x in participant:
#dict.get(key, default=None)
#key에 해당하는 value가 있으면 그대로 리턴하고
#없으면 지정값을 리턴한다.
d[x] = d.get(x, 0) + 1
for x in competion:
d[x] -= 1
#did not finish리스트를 컴프리헨션으로 만든다
dnf = [k for k, v in d.items() if v != 0]
answer = dnf[0]
return answer알고리즘의 시간 복잡도
x를 탐색하는 for 구문 2개 모두 전수조사이기 때문에 O(n)의 시간 복잡도를 가진다. dnf 또한 전수조사이기에 O(n)의 시간 복잡도를 가진다. 따라서 전체의 시간 복잡도는 O(n)이다.
2. 탐욕법(Greedy)문제풀이 : 체육복
문제는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/42862
자료구조와 알고리즘의 선택
<예제 분석>
n = 5
reserve = [1, 3, 5]
lost = [2, 4]
return 5
탐욕법(Greedy Algorithm)
- 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
탐욕법으로 최적해를 찾을 수 있는 경우는 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때이다.
탐욕법의 아이디어를 적용해보자
- 이 문제는 lost가 최대의 reserve를 받을 수 있어야 하기 때문에 임의의 연결이 아닌 정해진 순서에 따라 순서대로 연결이 이어지는 알고리즘으로 접근을 해야한다.
알고리즘의 구상
- 가능한 접근의 경우의 수 3가지
- reserve를 기준으로 탐색 -> O(x<n)
reserve 기준 탐색은 정렬이 필요하기 때문에 -> O(xlogx) - lost를 기준으로 탐색 -> O(x<n)
lost 기준 탐색 또한 정렬이 필요하다 -> O(xlogx) - 전체 학생을 모두 탐색 -> O(n)
- 알고리즘을 작성하기 전에 어떤 접근이 좀더 효율적일지를 생각해볼 수 있다. 모든 학생의 체육복 수를 계산하고 하나하나 탐색하며 나아갈지, reserve가 있는 학생수만을 고려하여 정렬 뒤 lost와 연결해줄지는 다양한 상황 속에서 생각해보아야 한다.
3번의 접근을 이용한 코드 작성
def solution(n, lost, reserve):
u = [1] * (n + 2)
for i in reserve:
u[i] += 1
for i in lost:
u[i] -= 1
for i in range(1, n+1):
if u[i-1] == 0 and u[i] == 2:
u[i-1:i+1] = [1,1]
elif u[i] == 2 and u[i + 1] == 0:
u[i:i+2] = [1,1]
return len([x for x in u[1:-1] if x > 0])알고리즘의 시간 복잡도
모든 학생수를 탐색하는 순회식의 알고리즘이기 때문에 시간 복잡도는 O(n)이다.
1번의 접근을 이용한 코드 작성
def solution(n, lost, reserve):
s = set(lost) & set(reserve)
l = set(lost) - s
r = set(reserve) - s
for x in sorted(r):
#번호가 작은 학생을 살펴보고
if x - 1 in l:
l.remove(x - 1)
#이후에 번호가 큰 학생을 살펴본다.
elif x + 1 in l:
l.remove(x + 1)
return n - len(l)알고리즘의 시간 복잡도
sorted(r)은 log(rlogr)만큼의 시간 복잡도를 가진다.
3. 정렬 문제풀이 : 가장 큰 수
문제는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/42746
문제의 해결방법(알고리즘 구상)
- 1.빈 문자열로 수를 초기화한다.
2.가장 크게 만들 수 있는 수를 고른다.
3.그 수를 현재 수에 이어 붙인다.
4.모든 수를 다 사용할 때까지 반복한다.
예제에 적용
- [3, 30, 34, 5, 9]이 주어진다면
9,5,34,3,30 순으로 이어붙이는게 최선이다.
다만 매번 가장 큰 수를 계산한다면 알고리즘이 비효율적이므로 알고리즘의 구상을 수정할 필요가 있다. - 1.빈 문자열로 수를 초기화한다.
2.수의 목록을(크게 만드는 것 우선으로) 정렬한다.
3.순서대로 현재 수에 이어 붙인다.
4.모든 수를 다 사용할 때까지 반복한다.
정렬의 기준을 정하기(패턴의 탐색)
- 숫자의 크기는 0이상 1000이하인 자연수이므로 어떤 수를 가져오든 4번을 반복한 수로 변환한 값으로 서로의 크기를 비교한다면(ex. 23 -> 23232323) 앞선 '크게 만드는 것 우선'을 만족하는 기준을 만들 수 있게 된다.
코드 작성
def solution(numbers):
#모든 숫자를 문자열로 변환해주기
numbers = [str(x) for x in numbers]
#변환한 숫자를 4번 반복한 값으로 정렬하기
numbers.sort(key=lambda x : (x*4)[:4], reverse=True)
#숫자가 0인 경우를 걸러주기
if numbers[0] == '0':
answer = '0'
else:
answer = ''.join(numbers)
return answer알고리즘의 시간 복잡도
시간 복잡도를 지배하는 구문은 numbers.sort(key=lambda x : (x*4)[:4], reverse=True)이다.
이 값에 따라 시간 복잡도가 달라진다.
4. 탐욕법 문제풀이 : 큰 수 만들기
문제는 다음과 같다.
https://programmers.co.kr/learn/courses/30/lessons/42883
문제의 해결방법(알고리즘 구상)
- 앞 자리에 큰 수가 오는 것이 전체를 크게 만든다. -> 큰 것을 우선해서 담을수 있어야 한다.
알고리즘 설계
- 주어진 숫자로부터 하나씩 꺼내어 모으되 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다. -> 이렇게 모은 숫자들을 자리수 맞추어 반환한다.
- 알고리즘의 복잡도
가장 단순한 방법은 가능한 모든 조합을 나열하고 그 중에서 가장 큰 값을 구하는 것이다. 이것은 숫자의 자리수가 커질 경우 최악의 시간 복잡도를 보인다. 아래는 파이썬의 툴인 조합을 사용해서 구현한 코드이다. 효율성 테스트를 통과하지 못한다.
from itertools import combinations
def solution(number, k):
answer = ''
num_list = list(number)
com_list = list(combinations(num_list, len(number)-k))
com_list.sort(reverse = True)
for number in com_list[0]:
answer += str(number)
return answer탐욕법으로 해결하기
- 앞 단계에서의 선택(앞 자리에 큰 수)이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않는다.
코드 작성
def solution(number, k):
collected = []
for i, num in enumerate(number):
while len(collected) > 0 and collected[-1] < num and k > 0:
collected.pop()
k -= 1
if k == 0:
collected += list(number[i:])
break
collected.append(num)
collected = collected[:-k] if k > 0 else collected
answer = ''.join(collected)
return answer알고리즘의 시간 복잡도
알고리즘이 2중 반복문으로 구성되어있기 때문에 n^2의 시간 복잡도를 가질 수 있다고 생각할 수 있지만 while문은 최악의 경우에도 1번 실행이 되기 때문에 for문이 가지는 n 즉, 전체로서는 O(n)의 시간 복잡도를 가지게 된다.
