본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

시간 복잡도

• 정의 : 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미
  컴퓨터 1초 연산량 3-5억개(물론, 단순연산과 복잡한 연산과의 횟수 차이가 있기에 주의)
  -> 시간 제한이 1초라고 하면 "프로그램이 3-5억 번의 연산 안에 답을 내고 종료되어야 한다"
  
  
  -> 정렬이 되어있다면 가운데 사람의 이름을 물어봐서 반으로 쪼개다 보면 답을 찾을 수 있다. logN에 비례한다.

• 기준이 절대적인 것은 아니다.

공간 복잡도

• 정의 : 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

크기 N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)
메모리 제한이 512MB일 때 int 변수를 대략 1.2억개 정도 선언할 수 있다는 것

---

파이썬에만 해당

입출력

  from sys import stdin, stdout
  input = stdin.readline 
  print = stdout.write

배열

• 2차원 배열 받기

MAP = [list(map(int,input().split())) for _ in range(int(input()))]

진법

• 2진수 : bin(num) -> 반대 : int('0b111100', 2)
• 8진수 : oct(num) -> 반대 : int('0o74', 8)
• 16진수 : hex(num) -> 반대 : int('0x3c', 8)

itertools 활용 조합

from itertools import combinations  
print(list(combinations([1, 2, 3, 4], 3)))

순열

from itertools import combinations  
print(list(combinations([1, 2, 3, 4], 3)))

얕은 복사(shallow copy)와 깊은 복사(deep copy)

원본 배열을 복사할 때 얕은 복사와 깊은 복사가 있다. 무작정 복사(a=b) 등으로 복사를 하면 원본 객체가 핸들링되어 데이터가 변경되어서 큰 문제를 야기할 수 있기 때문에 주의해야 한다.
파이썬에서 변수는 자체 저장 공간을 할당받지 않으며 객체를 가리키는 개념이다.
여기서 Mutable(가변)과 Immutable(고정)의 개념이 나온다.

대부분 우리가 알고리즘에서 사용하는 객체는 mutuable한 객체이다.

하지만 str은 immutable한 객체이며 변수에 첫 글자 변경 시도하면 에러 발생한다. s에 다른 값을 할당하면, id가 변경됩니다. 재할당은 애초에 변수를 다시할당하는 것이므로 mutable과 immutable과는 다른 문제입니다. list또한 값을 재할당하면 id가 변경됩니다.

• mutuable한 객체의 변수 간 대입.
  list를 얕은 복사해서 b에 a를 할당하면 값이 할당되는 것이 아닌 같은 메모리 주소를 바라보고 b를 변경시 a도 바뀐다. mutuable한 객체 또한 같은 현상이 일어난다.

>>> a = [1, 2, 3]
>>> b = a # shallow copy
>>> b[0]= 5
>>> a
[5, 2, 3]
>>> b
[5, 2, 3]
>>> id(a)
4396179528
>>> id(b)
4396179528

• immutable한 객체의 변수간 대입
  문자열의 얕은 복사를 확인해보자. b를 a에 할당하면 같은 메모리 주소를 바라보게 된다. 하지만 b에 다른 값을 할당하면 재할당이 이루어져 메모리 주소가 변경되고 다른 값을 가진다.

>>> a = "abc"
>>> b = a
>>> a
'abc'
>>> b
'abc'
>>> id(a)
4387454680
>>> id(b)
4387454680
>>> b = "abcd"
>>> a
'abc'
>>> b
'abcd'
>>> id(a)
4387454680
>>> id(b)
4396456400

얕은 복사(shallow copy)

>>> a = [1,2,3]
>>> b = a[:]
>>> id(a)
4396179528
>>> id(b)
4393788808
>>> a == b
True
>>> a is b
False
>>> b[0] = 5
>>> a
[1, 2, 3]
>>> b
[5, 2, 3]

슬라이싱 또한 얕은 복사에 해당된다. mutuable객체 안에 mutuable 객체인 경우 문제가 된다.
id(a) 값과 id(b) 값은 다르게 되었지만, 그 내부의 객체 id(a[0])과 id(b[0])은 같은 주소를 바라보고 있다.
a[1] 에 값을 변경하면 b[1]도 따라 변경된다.

>>> a[1].append(5)
>>> a
[[8, 9], [3, 4, 5]]
>>> b
[[1, 2], [3, 4, 5]]
>>> id(a[1])
4396389896
>>> id(b[1])
4396389896

copy 모듈의 copy 메소드 또한 얕은 복사이다.

>>> import copy
>>> a = [[1,2],[3,4]]
>>> b = copy.copy(a)
>>> a[1].append(5)
>>> a
[[1, 2], [3, 4, 5]]
>>> b
[[1, 2], [3, 4, 5]]

깊은 복사 (deep copy)

내부에 객체들까지 모두 새롭게 copy된다.

>>> import copy
>>> a = [[1,2],[3,4]]
>>> b = copy.deepcopy(a)
>>> a[1].append(5)
>>> a
[[1, 2], [3, 4, 5]]
>>> b
[[1, 2], [3, 4]]

출처
https://blog.encrypted.gg/923
https://covenant.tistory.com/143