[AI class day 3] 파이썬 코딩테스트 문제 풀이 TIL

* 3일차는 자료구조와 알고리즘 수업을 지나서, 프로그래머스 사이트나 입사용 코딩 테스트에서 많이 접하는 알고리즘 문제 풀이를 하는 동영상 강의를 들었다.

 

본 강의는 프로그래머스 사이트의 [Python/문제풀이] 파이썬을 무기로, 코딩테스트 광탈을 면하자!

 와 동일한 것 같다.

커리큘럼이 동일하다.

나처럼 코딩테스트 문제 풀이에 익숙하지 않거나, 문제는 어찌저찌 풀었지만 효율성 테스트에서 계속 실패하는 사람들은 문제에 어떻게 접근할 것인지 힌트를 얻기에 도움이 될 것 같다.

 

1. 해시(Hash) 대표 문제 풀이: "완주하지 못한 선수"

* 참고*

1. 문제의 데이터 크기를 잘 봐야 한다.

2. 문제의 제한 사항을 잘 읽어야 한다.

 

이 문제는 해시 Hash 자료 구조로 풀면 편리하다.

• 해시란? key - value 쌍으로 구성, key 가 배열의 index이기 때문에 검색, 저장의 평균 시간 복잡도가 O(1)임
• hash function : key-value 쌍을 할당하는 함수
• hash bucket : key-value 값이 할당되는 칸 하나 하나 . 이것이 크면 각 버켓에 하나씩만 들어갈 수 있게 hash function을 짤 수 있다
• hash table: hashbucket 들이 모인 table
• collision: 다른 key-value 쌍이 같은 hash bucket에 들어가 있는 경우 충돌 발생 -> 해결해야함

파이썬의 해시형 자료구조에는 사전(dictionary)이 있다. (set 도 있음)

 

*번외 파이썬 딕셔너리의 .get 메서드

• key를 통해 밸류값을 얻을 수 있는 메서드

 a = {'name':'James', 'phone':'010-1234-5678', 'email': 'hello@gmail.com'}
 a.get('name')

>> 'James'

만약, 딕셔너리 안에 찾으려는 Key 값이 없을 경우 미리 정해둔 디폴트 값을 대신 넣을 수 있다.

.get(x, '디폴트')

a.get('birthday', '1225')

 >>'1225'

a

 

이렇게 하면 저장이 안된다.

이렇게 key 지정해서 다시 해줘야 한다.

a['birthday'] = a.get('birthday', '1225')
a

>> {'name': 'James', 'phone': '010-1234-5678', 'email': 'hello@gmail.com', 'birthday': '1225'}

 

2.  탐욕법(Greedy) 대표 문제 풀이 : "체육복"

* 제한 사항이 아주 많은 문제*

특히 여벌 체육복을 가져왔는데도 체육복을 도난 당했을 수도 있다는 점을 고려해야 한다. 

--> 여벌 리스트에도 있고, 도난 리스트에도 있으면 --> 제자리다

 

이 문제는 탐욕법으로 해결할 수 있는 문제다

탐욕법(Greedy Algorithm)

• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하면 되는
• 탐욕법을 써도 되는 경우 : 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때

빌려줄 수 있는 학생들의 리스트를 해시를 적용해서 상수 시간에 처리하게 만들 수 있다.

--> set 데이터 타입 이용하기

 

* 파이썬의 데이터 타입 set

반복 가능하고, 가변적이며, 중복 요소가 없고, 정렬되지 않은 데이터 타입이다.

set : 해시 테이블로 구현되어 있다.

딕셔너리는 key-value 쌍으로 구성되어 있지만, set은 value 는 없고, 어떤 원소가 이 집합에 속해 있는지 아닌지만을 상관하는 자료 구조

중복을 허용하지 않기 때문에 집합의 연산을 간편하게 할 수 있다.

lost = [1,2,3,4]
reserve = [3,4,5,6]
s = set(lost) & set(reserve)

>> {3, 4}

 

*번외  파이썬의 내장함수 zip()

 

iterable한 객체를 parameter로 받고, 각 객체가 담고 있는 원소를 튜플 형태로 반환

lost =[2, 4, 5]
reserve =[1, 3, 5]
for pair in zip(lost, reserve):
    print(pair)

>> (2, 1) (4, 3) (5, 4)

 

두 리스트의 길이가 같지 않아도, 쌍이 있는 만큼 반환한다

lost =[2, 4, 5]
reserve =[1, 3, 5, 6]
for pair in zip(lost, reserve):
    print(pair)

>> (2, 1) (4, 3) (5, 5)

 

* 번외 두 리스트를 비교하여 같은 값만 반환하기

리스트 컴프리헨션으로 빨리 해결할 수 있다

lost =[2, 4, 5]
reserve =[1, 3, 5, 6]
lst = [i for i in reserve if i in lost]
lst

>> [5]

 

 

3. 정렬(Sort) 대표 문제 풀이 : "가장 큰 수 "

* 수의 대소관계, 사전 순서가 아닌 order로 정렬시켜 해결하는 문제

 

리스트의 원소들을 문자열로 만들어 이어붙이면 하나의 수로 만들 수 있는데,

 

키포인트는

1.

[30, 9]가 있을 때

309보다

930이 더 크다

 

즉 실제 수는 30 > 9 이지만 맨 앞에 오는 3과 9를 비교해서 9가 더 앞에 와야 한다.

--> 이것은 원소의 데이터 타입을 str으로 바꾼 다음 sort하면 쉽게 해결된다. (reverse = True)

 

2. 

[3, 30] 가 있을 때

330이

303보다 더 크다

 

즉, 첫째 자리의 수 크기가 같고, 전체 자리 수가 다를 때 어떤 기준으로 정렬해야 하는가? (내가 원하는 정렬 기준은 .sort 메서드에 key parameter 지정으로 해결한다)

--> 3 은 3333...으로 30은 3030...으로 만들어서 비교

 

 

4. 탐욕법(Greedy) 대표 문제 풀이 : "큰 수 만들기"

*큰수를 만드는 법의 원칙을 생각해야 한다.

1. 앞자리에 가장 큰 수가 와야 한다. --> 큰 수 위주로 뽑아야 한다 / 작은 수를 빼야 한다

2. 작은 수라도 앞에 있는 건 빼야 하지만 뒤에 있는 건 안빼도 된다.

     ex> 13415에서 2개를 빼야 한다면,

            맨 앞에 1과 3을 빼서 415을 만들어야 한다.

             1과 1을 빼서 345를 만드는 것 보다 더 크다.

  --> 이것을 어떻게 표현할 수 있을까?

  -->  1) 앞에서부터 담되 2) 새로 들어온 애보다 앞에 것이 작으면 뺀다 3)뺄 수 있을 때까지만,

3. 예외 

  역순 정렬로 구성된 경우에는 위와 같은 방법으로는 아무것도 뺄 수 없다 

   --> 제일 뒤에 있는 수들을 빼야 한다.

            

*탐욕법으로 접근해서 해결 가능한 문제

 - 앞 단계에서의 선택이 이후 단계에서의 동작에 의한 solution의 최적성에 영향을 주지 않음

--> 앞의 자리수에서 어떤 선택을 하는 것이 뒤의 자리수 동작에 영향을 미치지 않음

- 전체 조합을 다 찾은 다음 큰 수를 찾는 것 보다 각 자리수에서 가장 큰 것을 바로 고르는 방식으로 해결해도 답이 나온다. 

 

*참고 파이썬 내장 함수 enumerate()

• 배열의 인덱스와 값을 전달하는 함수
• 순서가 있는 자료 구조 (list, set tuple, dictionary, string)을 입력으로 받고
• 인덱스와 값을 가진 enumerate 객체를 리턴
• for 문과 함께 많이 쓰임 

data = enumerate([1,2,3,4])
print(data, type(data))

>> <enumerate object at 0x10a825080> <class 'enumerate'>

lst = [10, 20, 30, 40]
[k for k, v in enumerate(lst)]

>> [0, 1, 2, 3]

 

[v for k, v in enumerate(lst)]

>> [10, 20, 30, 40]

 

*번외 라이브러리 itertools를 활용해 순열, 조합 추출하기

순열

서로 다른 n개 중에 r개를 나열하는 경우의 수(순서 o) permutations 함수

result = list(itertools.permutations(([6, 10, 2]), 3))
print(result)

>> [(6, 10, 2), (6, 2, 10), (10, 6, 2), (10, 2, 6), (2, 6, 10), (2, 10, 6)]

중복 순열

중복가능한 n개 중에 r개를 나열하는 경우의 수 (순서 o) product 함수이며 repeat 파라미터 활용

result = list(itertools.product(([6, 10, 2]), repeat=3))
print(result)

>>[(6, 6, 6), (6, 6, 10), (6, 6, 2), (6, 10, 6), (6, 10, 10), (6, 10, 2), (6, 2, 6), (6, 2, 10), (6, 2, 2), (10, 6, 6), (10, 6, 10), (10, 6, 2), (10, 10, 6), (10, 10, 10), (10, 10, 2), (10, 2, 6), (10, 2, 10), (10, 2, 2), (2, 6, 6), (2, 6, 10), (2, 6, 2), (2, 10, 6), (2, 10, 10), (2, 10, 2), (2, 2, 6), (2, 2, 10), (2, 2, 2)]

조합

서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 x) combinations함수

result = list(itertools.combinations(([6, 10, 2]), 3))
print(result)

>>[(6, 10, 2)]