시간/공간 복잡도
자료구조란 자료를 어떻게 넣는가. 자료를 어떤 구조에 넣냐에 따라서 효율적일수도있고 아닐수도 있다. 효율성을 고려하지 않으면 답을 못찾는것과 같을 수 있다.
시간복잡도
이코드가 얼마나 빠르게 실행되는가?
#시간복잡도 1
a += 3
#시간복잡도 5
sum = 0
for i in [1,2,3,4]:
sum += i
def doNothing(nums):
return nums
# 시간복잡도 1
def doSomething(nums):
sum = 0
for num in nums:
sum += nums
return sum
# 시간복잡도 = N + 2(초기화, 리턴)
시간복잡도는 Big-O만 신경쓴다.(Big-0: 함수의 가장 높은 차수) 시간 복잡도가 중요한 이유는 어떤 코드에 어떤 인자가 들어가냐에따라서 프로그램 연산시간이 달라지기 때문이다.
입력값이 얼마나 크냐에 대한 시간복잡도를 알아야한다.
#예
1,000N = O(N)
2N^2 = O(N^2)
1일 경우
코드 1 = 1000
코드 2 = 2
1000일 경우
코드 1 = 1,000,000
코드 2 = 2,000,000
계산법
Rule 1. for/while loop가 한번 중첩 될때마다 O(N)이다.
#O(N)
for i in (len(nums)):
#O(N^2)
for i in (len(nums)):
for i in (len(nums)):
#O(N^3)
for i in (len(nums)):
for i in (len(nums)):
for i in (len(nums)):
Rule 2. 자료구조의 사용, 다른 함수 호출에는 각각의 O값이 존재한다.
# O(N)
nums = [2, 8, 19, 37, 4, 5]
if num in nums:
# O(1)
nums = {2, 8, 19, 37, 4, 5}
if num in nums:
# O(NlogN)
nums.sort()
Rule 3. 매번 절반씩 입력값이 줄어들면 O(logN)
----------------------
예시 : 이진탐색
N : 8
실행횟수 : log_2(8) = 3
----------------------
[2,4,9,11,15,17,19,21]
(1)
[15,17,19,21]
(2)
[15,17]
(3)
7
공간복잡도
이코드가 얼마나 많은 메모리를 사용하는가?
nums = [1,2,3,4,5] #O(1)
nums2 = [num * num for num in nums]
# [1,4,9,16,25]
#O(N)
nums2 = [[num * num for num in nums]for num in nums]
# O(N^2)
Rule 0 공간복잡도는 상대적으로 덜 중요함.(공간복잡도가 늘더라도 시간복잡도가 준다면 그걸 선택한다.)
Rule 1. 입력값의 복잡도 O(N)은 제외하고 생각
Rule 2. 각자료구조의 공간복잡도를 고려해야한다.
Rule 3. 함수내에 다른 함수를 호출하였을 경우 발생하는 **암시적인 공간 복잡도**도 고려해야한다.
(파이써닉하다는것은 파이썬 문법적 슈가를 잘쓰는것)
프로그래밍 문제 접근법
(면접관의) 고려사항
- 코드가 답을 내는가?
- 코드가 효율적인가?
- 코드가 실행가능하게 제대로 적혀졌는가?
경력과 코드를 잘짜는 능력은 별로 관계가 없다. 알고리즘을 잘하는법은 그냥 많이 하면 된다.
실습
가장 큰 두수의 차
이동시키기
#공간복잡도 O(N)
def moveZerosToEnd(nums):
index = 0
for i in range(len(nums)):
num = nums[i]
if num != 0:
nums[index] = num
nums[i] = 0
index += 1
return nums
def main():
print(moveZerosToEnd([0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0]))
배열의 회전
아나그램 탐지
def isAnagram(str1, str2):
list1 = list(str1)
list2 = list(str2)
# list1.sort()
# list2.sort()
# return list1 == list2
newHash = {}
for item in list1:
if item in newHash:
newHash[item] += 1
else:
newHash[item] = 1
for i in list2:
if i in newHash:
if newHash[i] == 0:
return False
else:
newHash[i] -= 1
else:
return False
return True
def main():
print(isAnagram('iamlordvoldemort', 'tommarvoloriddle')) # should return True
print(isAnagram('cat', 'cap')) #should return False
틀린문자 찾기
def findDifference(str1, str2):
list1 = list(str1)
newHash = {}
for item in list1:
if item in newHash:
newHash[item] += 1
else:
newHash[item] = 1
for item in list(str2):
if item not in newHash:
return item
else:
if newHash[item] == 0:
return item
else:
newHash[item] -= 1
return None
def main():
print(findDifference("apple","aplppe"))
세번째로 큰 숫자 찾아내기
# 시간복잡도 형(90점)
def thirdMax(nums):
newHash = { 1: 0, 2: 0, 3: 0 }
for item in nums:
if item > int(newHash[1]):
temp = newHash[2]
newHash[2] = newHash[1]
newHash[3] = temp
newHash[1] = item
elif item > int(newHash[2]):
temp = newHash[2]
newHash[2] = item
newHash[3] = temp
elif item > int(newHash[3]):
newHash[3] = item
return newHash[3]
# 공간복잡도 형 (90점)
def thirdMax(nums):
nums.sort()
return nums[-3]
# 시간&공간복잡도형
def main():
print(thirdMax([2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23])) # should return 34
단어 패턴