[기술면접] 알고리즘

1. Dynamic Programming이란? 장점은?

DP 란?

• 주어진 문제를 여러개의 부분 문제들로 나누어 푼 다음, 겹치는 부분은 메모이제이션 기법을 사용하여 주어진 문제를 푼다. 한마디로 분할정복 + 메모이제이션 기법이라고 할 수 있다.

DP 장단점

• DP 장점: 모든 가능한 경우를 확인하기 때문에 정확한 값을 얻을 수 있다.
• DP 단점: 모든 가능한 경우를 확인하기 때문에 시간복잡도가 크다 .

DP 구현 (피보나치)

탑다운(재귀)
가독성이 좋지만, 재귀 호출의 과정에서 스택 메모리가 발생

d = [0] * 100
def fibo(x):
	if x == 1 or x == 2:
		return 1
	if d[x] != 0:
		return d[x]
	d[x] = fibo(x-1) + fibo(x-2)
	return d[x]

바텀업(반복)
함수를 따로 부르지 않아서 시간과 메모리를 절약할 수 있습니다.

x = 99
d = [0] * 100
d[1] = 1
d[2] = 1
for i in range(3, x+1):
	d[i] = d[i-1]+ d[i-2]
print(d[x])

2. 배열 nums에 [0, n]범위의 n개의 양의 정수가 담겨있습니다. [0, n]범위 수 중에서 배열에 빠져있는 수 하나를 반환하는 가장 효율적인 알고리즘을 작성하세요.

answer1 : 해시셋 이용 -> 파이썬의 defaultdict 사용
시간 복잡도 : O(n)
공간 복잡도 : O(n)

from collections import defaultdict
n = 10
arr = [1, 6, 4, 3, 5, 2, 8, 9]
lst = defaultdict(int)
for i in arr:
	lst[i] = 1
for i in range(n):
	if lst[i] == 0:
		print(i)

answer2 : 1에서 n까지의 합 이용 -> n까지의 합 - 배열의 합
시간 복잡도 : O(n)
공간 복잡도 : O(1)

n = 9
arr = [0, 1, 6, 4, 3, 5, 2, 8, 9]
tmp = (n * (n+1)) // 2
print(tmp)
sumTmp = 0
for i in arr:
	sumTmp += i
print(tmp - sumTmp)

3.배열의 숫자를 활용해서 만들 수 있는 가장 큰 숫자를 반환하세요.

1 <= nums.length <= 100, 0 <= nums[i] <= 109
입력: nums = [10,2]
출력: "210"
입력: nums = [3,30,34,5,9]
출력: "9534330"

답안 람다 비교 : 한자리씩 비교하고 같으면 다음자리 비교 , 비교됐으면 바로 종료 그래서 문자열의 길이가 달라도 괜찮음

nums = [3,30,34,5,9]
nums = list(map(str, nums))
# 한자리씩 비교하고 같으면 다음자리 비교 비교 되면 종료
nums.sort(key=lambda x: x*3, reverse=True)
print(''.join(nums))