시간/공간 복잡도

자료구조란 자료를 어떻게 넣는가. 자료를 어떤 구조에 넣냐에 따라서 효율적일수도있고 아닐수도 있다. 효율성을 고려하지 않으면 답을 못찾는것과 같을 수 있다.

시간복잡도

이코드가 얼마나 빠르게 실행되는가?

#시간복잡도 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. 함수내에 다른 함수를 호출하였을 경우 발생하는 **암시적인 공간 복잡도**도 고려해야한다.

(파이써닉하다는것은 파이썬 문법적 슈가를 잘쓰는것)

프로그래밍 문제 접근법

(면접관의) 고려사항

  1. 코드가 답을 내는가?
  2. 코드가 효율적인가?
  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

단어 패턴



results matching ""

    No results matching ""