프로그래머스 인공지능 데브코스 3기 수업내용 정리 #3(코딩테스트 연습)

파이썬을 무기로, 코딩테스트 광탈을 면하자!

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가지

1. reserve를 기준으로 탐색 -> O(x<n)
   reserve 기준 탐색은 정렬이 필요하기 때문에 -> O(xlogx)
2. lost를 기준으로 탐색 -> O(x<n)
   lost 기준 탐색 또한 정렬이 필요하다 -> O(xlogx)
3. 전체 학생을 모두 탐색 -> 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)의 시간 복잡도를 가지게 된다.