Algorithm problems, coding test/이코테(책)
[이코테][Chapter 4] Implementation
정수열
2022. 5. 22. 03:35
구현(Implementation)은 말 그대로 "주어진 설명대로 프로그램을 작성할 수 있냐"는 문제이다. 사실 모든 알고리즘 문제, 코딩 테스트 문제가 이렇다.
사실 딱히 덧붙일 설명은 없는데, 자주 나오는 유형 하나가 상당히 골치 아프다. 순열과 조합이다.
순열과 조합
실제로 문제를 풀 때, 가장 먼저 파이썬의 itertools 라이브러리를 사용하여 간단하게 구현해본다.
그러나 삼성전자 코딩테스트의 경우에는 사용이 불가능하고, 실제로 itertools로 문제를 풀다가 시간초과(...)가 뜰수도 있고, 변수가 상당히 많다.
만약 문제가 발생할 경우, 순열과 조합을 만드는 코드를 따로 적어서 사용한다.
itertools를 이용한 순열, 조합
import itertools
arr = [1,2,3]
for i in itertools.permutations(arr, repeat=2):
print(i) #1,2,3의 순열 결과가 tuple로 하나씩 나온다.
for i in itertools.combinations(arr, repeat=2):
print(i) #1,2,3의 조합 결과가 tuple로 하나씩 나온다.순열
def permutations_2(array, r):
for i in range(len(array)):
if r == 1:
yield [array[i]]
else:
for next in permutations_2(array[:i]+array[i+1:], r-1):
yield [array[i]] + next
출처: https://juhee-maeng.tistory.com/91조합
def combinations_2(array, r):
for i in range(len(array)):
if r == 1: # 종료 조건
yield [array[i]]
else:
for next in combinations_2(array[i+1:], r-1):
yield [array[i]] + next
출처: https://juhee-maeng.tistory.com/91