[알고리즘 코딩캠프 1일차] 뮤터블, 얕은 복사, 문자열, 딕셔너리, 시간복잡도, 입력, 출력, 팁, 파이써닉 - 리스트 컴프리헨션, 패킹, 언패킹, enumerate, Counter

제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.

목차 :

• 뮤터블 vs 이뮤터블
• 할당 vs 얕은 복사 vs 깊은 복사
• 문자열
• 딕셔너리
• 시간복잡도
• 입력
• 출력
• 팁
• 파이써닉
  • 리스트 컴프리헨션
  • 패킹, 언패킹
  • enumerate
  • Counter

---

주의사항

mutable과 immutable의 차이

- 파이썬은 모든 게 객체

- 3이 어디에 있고 걔를 가리키는 주소값이 있는 느낌

- 리스트는 뮤터블이라 뭘 추가해도 똑같은 객체를 가리킴

- 문자열은 이뮤터블이라 새로 객체 생성 후 포인터가 변경 → 원래 놈은 참조가 사라지니 가비지 콜렉터가 수거해갈 예정

할당 vs 얕은 복사 vs 깊은 복사

#1 할당

a = [1,2,3]
b = a

b[0] = 4
print(b) # [4, 2, 3]
print(a) # [4, 2, 3]


#2 얕은 복사

a = [1, 2, 3]
b = a[:]
# b = list(a)
# b = [i for i in a] # list comprehension

b[0] = 4
print(b) # [4, 2, 3]
print(a) # [1, 2, 3]

# 깊은 복사가 필요한 이유
a = [[1, 2, 3], [4, 5, 6]]
b = a[:]
b[0][0] = 9

print(a) # [[9, 2, 3], [4, 5, 6]]
print(b) # [[9, 2, 3], [4, 5, 6]]
# => 깊은 복사가 필요하다!!
# 이거 그림 구해와서 보면 이해 더 쉬움.


# 3. 깊은 복사

# 이중 for문 돌면서 일일이 반복할 수도 있지만,
# copy 모듈의 deepcopy 함수를 쓸 수도 있음.
from copy import deepcopy
a = [[1, 2, 3], [4, 5, 6]]
b = deepcopy(a)
b[0][0] = 0

print(a) # [[1, 2, 3], [4, 5, 6]]
print(b) # [[9, 2, 3], [4, 5, 6]]
# deepcopy를 3중, 4중 쫙쫙 복사해줌.
# 이제는 [1, 2, 3] 얘네따리 
# 따로 포인터가 되기 때문에.

이거 그림 보고 이해해야 더 쉬운데, 

아래 글에 도식화가  잘 돼 있어서 참고해도 좋을듯?

https://velog.io/@kkamyang/Python-%EC%96%95%EC%9D%80-%EB%B3%B5%EC%82%AC-%EA%B9%8A%EC%9D%80-%EB%B3%B5%EC%82%AC-shallow-copy-deep-copy

[Python] 할당과 복사 / 얕은 복사, 깊은 복사 (shallow copy, deep copy)

---

문자열

이걸 알려주는 이유 :
백준에서 입력으로 주어지는 놈을, 내가 본격적으로 다룰 놈으로 바꾸기 위해
데이터 전처리를 할 때 당황하지 말고 이런 식으로 하라고.

목차)

1. split
2. join
3. replace

# 1. split

numbers = '1@2@3@4@5' # 백준에서 입력이 이런 식으로 들어온다고!!
print(numbers.split('@')) # ['1', '2', '3', '4', '5']

sentence = '12345'
# list comprehension을 쓸 수도 있지만...
print(list(sentence)) # ['1', '2', '3', '4', '5'] - 이렇게 하자!

string_numbers = ['1', '2', '3', '4', '5']
print(map(int, string_numbers)) # 이상한 거 나옴
# map은 iterable 객체인 map 객체를 반환하기 때문.
# 오른쪽 매개변수의 하나하나 요소들에 왼쪽 함수를 적용해준다.

print(list(map(int, string_numbers))) # [1, 2, 3, 4, 5]
# map 객체를 list로 변환해줌.


# 2. join

string_numbers = ['1', '2', '3', '4', '5'] # -> '12345' 로 만들고 싶음.
joined_number = ''.join(string_numbers)
# 주의사항 : join의 매개변수로 들어온 놈 안의 요소가 다 문자여야함.
print(joined_number) # '12345'

numbers = [1, 2, 3, 4, 5] # -> '12345' 로 만들고 싶음.
joined_number = ''.join(map(str, numbers))
# map 객체도 이터러블 이라서(for문으로 돌릴 수 있는 놈이라) 사용 가능
print(joined_number)


# 3. replace

sentence = 'hello python'
sentence.replace('python', 'java')
print(sentence) # 'hello python'
# 얘는 원본을 못 바꿈! 이뮤터블이니까.

numbers = [4, 1, -1, 0]
numbers.sort() 
print(numbers) # 얘는 되는데?
# => 되는 이유 : 쟤는 뮤터블이니까 list.sort()가 저걸 직접 바꿔주기 때문(반환값은 None).

# 따라서, 아래처럼 재할당을 해줘야 함. 새로 문자열 생성 후, 포인팅만 바꿈.
sentence = sentence.replace('python', 'java')
print(sentence) # 'hello java'

sentence = sentence.replace('java', '')
print(sentence) # 'hello ' # 이렇게 지울 수도 있음.

---

딕셔너리

- `딕셔너리`는 key와 value가 따로 있는 거고

- `집합`은 key와 value가 같은 것.

- 둘 다 hash로 구현되어 있음.

 

- key는 이뮤터블만 가능

- 뮤터블을 쓰면 key가 유니크한 저 value를 가리켜줄 수 없음. 리스트같은거 생각해보면 같은 값으로 다른 리스트 가리킬 수 있잖음.

- 그래서 집합에도 마찬가지로 이뮤터블만 들어갈 수 있음.

목차)

1. get
2. keys, values, items

# 1. get

users = {'kyle': 20, 'alex': 30, 'ken': 40} # key: value 자료형
print(users['kyle'])
print(users.get('kyle')) 

# 2개의 차이점?

# 1) 존재하지 않는 key를 조회할 경우
print(users['justin']) # error가 발생
print(users.get('justin')) # None을 반환

# 2) 존재하지 않는 key 조회 시 0이 나오게 하려면
# 아래처럼 할 수도 있지만
if 'justin' in users:
	print(users.get('justin'))
else:
	print(0)

# get의 두 번째 인자는 defalut value이기 때문에, 
# 아래처럼 default value를 지정해줄 수도 있음.
print(users.get('justin', 0))

# 이 두 개가 사실상 동일.
print(users.get('justin', None))
print(users.get('justin')


# 2. keys, values, items

for key in users.keys(): # users.keys() : key만 들어있는 객체
	print(key)
	
for key in users: # 여기선 .keys()가 생략돼있다고 보면 됨. key를 기반으로 조회를 한다.
	print(key)
	
for value in users.values(): # users.values() : value만 들어있는 객체
	print(value)
	
for key, value in users.items(): # users.items() : (key, value) 튜플을 요소로 가지는 객체 -> 언패킹
	print(key, value)
	
# 아래처럼 C 스타일로 짜지 말자! 파이써닉하게 짜자.
for key in users:
	print(key, users[key])

---

시간복잡도

시간복잡도(Time Complexity)란, 문제를 해결하는데 걸리는 `시간과 입력의 함수 관계` 를 말함.

좋은 알고리즘 = 같은 기능을 더 짧은 실행 시간으로 수행하는 놈.

 

실행 시간은 단위연산의 횟수를 가지고 비교함.

`단위연산` : 단위시간 1이 소요되는 연산(할당, 산술, 비교, 반환, ...)

 

우리는 가장 `단위연산`이 많이 일어나는 경우인, 최악의 입력인 n개가 들어온다고 가정한다.

입력 n개에 따른 소요 시간 = 시간복잡도

 

실제 문제는 초 단위. 어림짐작 하는 법을 배워야 함.

보통 `1초에 1억 번 연산`으로 계산을 함.

시간제한 1초면 너가 1억 번 이상 연산하면 시간 초과다!!

이 시간제한을 보고, 반복문을 몇 중으로 써야 할 지 등 어떤 시간복잡도의 풀이까지 써도 될 지 생각해야함.

 

 

ex. 1부터 n까지 더해라 - 시간제한 1초, 입력인 n은 `1 ≤ n ≤ 10억`의 범위를 가짐.

그냥 다 더하면 10초 걸릴 것으로 예상. `O(n)`임.

 

어케할까?

→ 가우스의 합 공식 사용 : (n(n+1))//2

→ 단위연산 딱 3번 일어남. `O(1)`임.

 

 

각 함수, 메서드들도 시간복잡도가 다 있음.

그래서 for을 한 번만 썼다고 무조건 O(n)인게 아님.

=> 이거 나중에 각 함수, 메서드 별 시간복잡도 확인해 볼 가치 있을듯.

시간복잡도 종류

상수 시간복잡도 : O(1)

• 입력 크기에 상관없이 실행 시간이 일정하다.
• 예시 : 배열에서 특정 인덱스의 요소에 접근

로그 시간복잡도 : O(logN)

• 실행 시간이 입력 크기의 로그에 비례하여 증가한다.
• 예시 : 이진 탐색 알고리즘

선형 시간복잡도 : O(N)

• 실행 시간이 입력 크기에 비례하여 증가한다.
• 예시 : 리스트 또는 배열에 대한 반복문 알고리즘

선형 로그 시간복잡도 : O(NlogN)

• 실행 시간이 N과 logN의 곱에 비례하여 증가한다.
• 일반적으로 O(logN)의 시간이 걸리는 로직을 N번 반복할 때 걸리는 시간복잡도이다.
• 예시 : 효율적인 정렬 알고리즘(퀵소트, 머지소트)

제곱 시간복잡도 : O(N2)**

• 실행 시간이 입력 크기의 제곱에 비례하여 증가한다.
• 예시 : 이중 반복문을 사용하는 알고리즘

지수 시간복잡도: O(2n)**

• 설명 : 실행 시간이 입력 크기에 대한 지수 함수로 증가하는 알고리즘이다.
• 예시 : 재귀함수를 활용한 피보나치 수열 구현

컨테이너 자료형 시간복잡도 정리

리스트

 

Index	l[i]	O(1)
Store	l[i] = 0	O(1)
Length	len(l)	O(1)
Append	l.append(5)	O(1)	대부분 O(1); ICS-46에서 자세한 내용 확인 가능
Pop	l.pop()	O(1)	l.pop(-1)과 동일, 끝에서 요소 제거
Clear	l.clear()	O(1)	l = []와 유사
Slice	l[a:b]	O(b-a)	예: l[1:5]는 O(4), l[:]는 O(N)
Extend	l.extend(...)	O(len(...))	확장하려는 길이에만 의존
Construction	list(...)	O(len(...))	반복 가능한(iterable) 객체의 길이에 따라 다름
Check ==, !=	l1 == l2	O(N)
Insert	l[a:b] = ...	O(N)
Delete	del l[i]	O(N)	i에 따라 달라짐, 최악의 경우 O(N)
Containment	x in/not in l	O(N)	리스트를 선형적으로 검색
Copy	l.copy()	O(N)	l[:]와 동일, O(N)
Remove	l.remove(...)	O(N)
Pop	l.pop(i)	O(N)	최악의 경우: l.pop(0)은 O(N)
Extreme value	min(l)/max(l)	O(N)	리스트를 선형적으로 검색
Reverse	l.reverse()	O(N)
Iteration	for v in l:	O(N)	최악의 경우: 루프에서 return이나 break 없음
Sort	l.sort()	O(N Log N)	key/reverse는 복잡도에 거의 영향을 주지 않음
Multiply	k * l	O(k N)	5 * l은 O(N), len(l) * l은 O(N**2)

 

집합

Length	len(s)	O(1)
Add	s.add(5)	O(1)
Containment	x in/not in s	O(1)	리스트나 튜플과 비교하면 O(N)
Remove	s.remove(...)	O(1)	리스트나 튜플과 비교하면 O(N)
Discard	s.discard(...)	O(1)
Pop	s.pop()	O(1)	임의의 값이 선택되어 제거됨
Clear	s.clear()	O(1)	s = set()과 유사
Construction	set(...)	O(len(...))	반복 가능한(iterable) 객체의 길이에 따라 다름
Check ==, !=	s != t	O(len(s))	길이가 다르면 O(1)에서 False 반환
<= / <	s <= t	O(len(s))	issubset
>= / >	s >= t	O(len(t))	issuperset; s <= t == t >= s
Union	`s	t`	O(len(s) + len(t))
Intersection	s & t	O(len(s) + len(t))	교집합
Difference	s - t	O(len(s) + len(t))	차집합
Symmetric Diff	s ^ t	O(len(s) + len(t))	대칭 차집합
Iteration	for v in s:	O(N)	최악의 경우: 루프에서 return이나 break 없음
Copy	s.copy()	O(N)

 

딕셔너리

 

Index	d[k]	O(1)
Store	d[k] = v	O(1)
Length	len(d)	O(1)
Delete	del d[k]	O(1)
Get/Set Default	d.get(k)	O(1)
Pop	d.pop(k)	O(1)
Pop Item	d.popitem()	O(1)	임의의 값이 선택되어 제거됨
Clear	d.clear()	O(1)	d = {}와 유사
View	d.keys()	O(1)	d.values()도 동일
Construction	dict(...)	O(len(...))	(key, value) 튜플의 개수에 따라 다름
Iteration	for k in d:	O(N)	키, 값, 또는 항목(iteritems)에 모두 적용 가능. 최악의 경우: return/break 없음

 

---

입력

# input, readLine

# n = int(input()) # 숫자 하나를 입력받음
# print(n)

import sys
line = sys.stdin.readline() # 한 줄을 통으로 읽어옴
print(line)

# 이걸 알려주는 이유 :
# 백준에서 어려운 문제는 input() 써서 시간초과가 날 때가 있는데,
# 사실 input() 함수가 좀 느림. 내부적으로 가공이 좀 들어가 구현돼 있음.

# 따라서, 백준에선 무조건 아래처럼 sys.stdin.readline() 써서 입력받자!!!!
# 보통은, 아래처럼 함. 함수 자체를 변수에 할당해버림. 암기.
input = sys.stdin.readline
n = int(input())
print(n)


word = input() # 'hello'
print(list(word)) # ['h', 'e', 'l', 'l', 'o', '\n']

word = input().rstrip() # 문자열의 오른쪽에 있는 공백, 개행문자 등을 지워줌.
print(list(word)) # ['h', 'e', 'l', 'l', 'o']

# 문자열 입력을 받을 땐 위와 같이 개행문자를 지워줘야 함.

word = input() # str.split()을 쓸 거면 얘가 알아서 지워주니 str.rstrip() 안 써도 됨.
print(word.split()) # ['h', 'e', 'l', 'l', 'o']

# Quiz. 1 2 3 4 5를 입력받고 [1, 2, 3, 4, 5] 숫자 리스트를 출력하는 코드를 짜 봐라.
# 1 2 3 4 5 -> [1, 2, 3, 4, 5]

import sys
input = sys.stdin.readline

print(list(map(int, input().split())))

# 콘솔 없이 실행은 아래처럼
# input_str = '1 2 3 4 5'
# print(list(map(int, input_str.split())))

# 백준 1000번 A + B

import sys
input = sys.stdin.readline

# 1 2 -> (1 + 2 값)
a, b = map(int, input().split())
# map도 이터러블이라 다중 할당이 가능.

print(a + b)

https://www.acmicpc.net/problem/1000

# 백준 10950번 A + B - 3

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    print(a + b)

https://www.acmicpc.net/problem/10950

---

출력

# Output

print('hello')

print('hello', 'python', '!')
# print는 인자가 여러개면 공백을 넣어 출력해준다.

print('hello', end = '')
# end 옵션으로 문자열 끝의 개행 대신 다른 문자를 출력해줌.
print('hello', end = '\n') 
# 이게 default.


# 아까 '공백을 넣어' 라고 했는데, 그 '구분자'를 뭘로 넣을까에 대한 옵션이 sep임.
# default: sep = ' '
print('hello', 'python', '!', sep=' ')
print('hello', 'python', '!', sep='\n')

numbers = [1, 2, 3]
print(*numbers, sep = '\n')
# 1
# 2
# 3
# => 리스트 요소 세로 출력할 때, for문으로 짜던 거 한 줄로 짤 수 있음.
# 다음 시간에 또 가르침.


# f-string
print('안녕하세요 ' + name + '입니다.') # 문자열 덧셈을 이용한 포맷팅
print(f'안녕하세요 {name}입니다.') # f-string 포맷팅
# f-string은 알고리즘에선 딱 요정도 수준만 알고 가자.

---

백준 및 코테 팁

- 백준에서의 안좋은 꼼수이긴 한데, PyPy3는 기존 Python3 컴파일러에서 메모리 사용량을 늘리고 속도를 빠르게 한 컴파일러라서, Python3으로 일단 하고 느리면 PyPy3으로 제출해보는 방법이 있음. PyPy3으로까지 했는데 안 되면 내 알고리즘 고칠 수밖에.

→ 근데 이 꼼수는 그냥 안 쓰는 게 나을듯.

 

- 코딩테스트 패스를 위해선 골드1~2정도 티어가 되면 된다는 듯?

---

파이써닉 - 파이썬을 파이썬 답게 코딩하자.

목차)

1. 리스트 컴프리헨션
2. 패킹, 언패킹
3. enumerate
4. Counter

# 1. 리스트 컴프리헨션
# C나 자바에는 없는, 정말 파이써닉한 방식.

numbers = []
for i in range(1, 6):
	numbers.append(i)
print(numbers)

numbers = [i for i in range(1, 6)]
# 방금 4줄에 걸쳐 수행한 작업을 한 줄로 끝냄.

even_numbers = [i for i in range(1, 6) if i % 2 == 0]
print(even_numbers) # [2, 4]

tupled_numbers = [(i, j) for i in range(1, 6) for j in range(1, 6)]
print(tupled_numbers) # [(1, 1), (1, 2), (1, 3), ..., (5, 4), (5, 5)]



# 2. 패킹, 언패킹

# 파이썬은 기본적으로 아래와 같은 다중 할당이 가능함.
a, b = 1, 2
# 아래와 같이 스왑이 그 자리에서 바로 됨. 이것도 다중 할당. (내부적으론 아마 임시 저장소 할당?)
a, b = b, a
# 근데, 위에 이건 사실상 언패킹이기도 함.
# 언패킹을 알기 위해 패킹부터 알고 가자.


# 패킹

# * : 묶어서 넣는다. 리스트로 만들어줌.
a, *b = 1, 2, 3, 4
print(a) # 1
print(b) # [2, 3, 4]

*a, b = 1, 2, 3, 4
print(a) # [1, 2, 3]
print(b) # 4

*a, b, c = 1, 2, 3, 4
print(a) # [1, 2]
print(b) # 3
print(c) # 4


# 언패킹

numbers = [1, 2, 3]
a, b, c = numbers
print(a) # 1
print(b) # 2
print(c) # 3

a, *b = numbers
print(a) # 1
print(b) # [2, 3]

# 다시 보면, 아래의 코드도 사실 튜플의 괄호가 생략된 거임.
# 다중 할당은 튜플을 언패킹하는 것.
a, b = 1, 2
a, b = (1, 2)
# 참고로 이거 동시 할당이라서 문제없음.


# 1 2 3 출력하고 싶음

print(numbers[0], numbers[1], numbers[2])
# 위는 C스러운 코드. 언패킹을 사용해 파이써닉하게 짜면 아래처럼 됨.
print(*numbers) 
# 이미 패킹이 된 자료형에 붙이면 얘는 언패킹하라는 의미가 됨. 
# 괄호 벗겨서 안에 요소를 여따가 다시 넣어라!
print(*numbers, sep = '\n')
# 아까 봤던 위 코드도 이런 원리였던 거임. 



# 3. enumerate
# 파이썬 코딩의 기술 이란 책이 있는데, 거기 나온 파이써닉 100가지 중 7번째에 소개되는 내용.
# range 대신 enumerate를 사용해라.

# C스럽게 리스트 요소 세로로 출력하면 다음과 같음.
numbers = [1, 2, 3, 4, 5]
for i in range(len(numbers)):
	print(numbers[i])

# 만약 인덱스도 같이 출력하라 하면?
for i in range(len(numbers)):
	print(i, numbers[i])
	
# 근데, 이거 가독성이 낮다는 거임. 파이써닉하지 않으니 웬만하면 이렇게 하지 마라!
# 대신, enumerate를 적극적으로 활용해라!

for i, number in enumerate(numbers): # (index, 원소) 튜플을 가지는 enumerate 객체를 반환
	print(i, number)
	
	
# 추가) 저거 이제 인덱스, 요소를 각각 세로로 묶는 방법?
print(list(zip(*enumerate(numbers)))) # [(0, 1, 2, 3, 4), (1, 2, 3, 4, 5)]
# 이거 다는 아는데 왜 이해를 못할까 우리가.
# 위처럼 우리가 짤 수 있다면 정말 파이써닉한 코드를 짤 수 있는 사람이 된 거임.

# enumerate(numbers) # (0, 1), (1, 2), ...
# *enumerate(numbers) # 저거 하나하나 원소를 언패킹함.
# zip # 같은 index 놈끼리 묶어줌
# 그걸 다시 list로 묶어줌



# 4. Counter

# Quiz. 리스트 내 key의 개수를 세는 코드를 순수 dict로 구현한다면?
numbers = [1, 3, 4, 1, 2, 2, 3, 2, 2]
counter = {}
for number in numbers:
	if number in counter: 
		counter[number] += 1 # 있으면 +1 해줌
	else:
		counter[number] = 1 # 없으면 1개로 설정
print(counter)
# 이거 defaultdict() 쓰면 초기 조건문 안나눠도 됨.


# 근데, 저걸 파이써닉하게 한 줄로 바꿔 쓸 수 있다!!! 가 핵심.
# 코테에서 개꿀이다!!!


from collections import Counter
numbers = [1, 3, 4, 1, 2, 2, 3, 2, 2]
counter = Counter(numbers)
print(counter) # Counter({2: 4, 1: 2, 3: 2, 4: 1})
# 끝났음 크크크 아름다움!!!
# 딕셔너리는 아니고 카운터 객체를 반환하긴 하지만, 
# 딕셔너리와 동일한 문법을 적용받기 때문에,
# 그냥 딕셔너리라고 간주하고 문제풀면 됨. (메서드들 동일함)

print(counter.keys())
print(counter.values())
print(counter.items())
# 메서드들 다 사용 가능.

print(counter.most_common()) # [(2, 4), (1, 2), (3, 2), (4, 1)] 
# 빈도 순 정렬해 튜플을 요소로 가지는 리스트를 반환해줌.
# 안정 정렬 적용됨. 
# 이거 Counter 안 썼으면 sort()에 value 다뤄야 하니 람다 쓰고...


# 가장 많이 등장하는 숫자를 출력하라고 하면?
print(counter.most_common()[0][0]) # 2

---

과제 및 풀이 정리

<리스트>

https://cuffyluv.tistory.com/131

https://cuffyluv.tistory.com/132

<해시>

https://cuffyluv.tistory.com/133

https://cuffyluv.tistory.com/134

https://cuffyluv.tistory.com/135

https://cuffyluv.tistory.com/136