[1주차 - Day03] 파이썬을 무기로, 코딩테스트 광탈을 면하자! (1)

Step 1. 해시(Hash)

---

번호로 값에 접근할 수 있는 배열 대신 문자열로 값에 접근할 수 있는 해시를 이용

-> Python에서 dict 자료형을 이용하여 해시를 사용할 수 있다.

 

 

Step 2. 탐욕법(Greedy)

---

알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택

현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용 가능

 

즉, 앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality)에 영향을 주지 않음

 

 

 

+) mutable 과 immutable

mutable(뮤터블)

• 변경이 가능한 객체
• 최초 생성 이후에 자유롭게 값의 변경, 추가, 삭제 등이 가능하다.

Ex) int, float 등의 기본 변수, list, 사용자 정의 클래스

 

mutable(뮤터블) 한 객체들은 =으로 값을 재정의 할 수 있다.

num = 1    
print(num)    # 1

num = 2    
print(num)    # 2

이와 같이 변경이 가능

 

 

immutable(이뮤터블)

• 변경이 불가능한 객체
• 최초 생성 이후에 값을 변경할 수 없다.

Ex) tuple, string, dictionary의 key, 이 외에 내장 타입인 숫자, 불리언 등이 포함된다.

 

immutable(이뮤터블) 한 객체들은 =으로 변경이 불가능

string = "abc"    
print(string)    # abc

string[-1] = "z'    
print(string)    # Error 발생

즉, str 객체에는 특정 아이템의 할당이 불가능하다는 것이다. (tuple도 마찬가지)

 

dictionary인 경우는 key에는 immutable한 형식만 들어갈 수 있고, value는 이와 관계없이 들어갈 수 있다.

dictionary = dict()
dictionary["q"] = (1, 2, 3)    
print(dictionary)    # {'q' : (1, 2, 3)}

dictionary[1] = "1입니다."    
print(dictionary)    # {'q' : (1, 2, 3), 1 : '1입니다'}

dictionary[[1,2,3]] = 1     # Error 발생

위 코드에서 Error 발생 원인은 key에 mutable한 객체를 넣을려고 했기 때문에 발생한 것이다.

 

추가로 1은 int로 key가 될 수 없지 않을까라는 의문이 생기는데,

1은 파이썬 내장 타입인 number로 취급이 되므로, immutable한 성질을 가지고 있다.

 

 

mutable vs immutable

 

mutable인 경우 값 조작에 편의성이 좋다.

랜덤하게 들어온 숫자들의 정렬이라던가 내가 만든 클래스라던가 값의 변형과 조작을 편하게 할 수 있다.

 

immutable인 경우 변화하지 않을 값을 보호하는 것에 좋다.

특정 값을 변화없이 써야 될때 immutable 성질을 가지는 객체로 저장을 하고 사용하는 것이 좋다.

 

 

mutable 과 immutable의 빠르기 비교

결론부터 말하자면 mutable이 더 빠르다.

arr = [1, 2, 3]
arr[0] = 100
print(arr)    # [100, 2, 3]

string = "abc"
string.replace("a", "z")
print(string)    # abc
string = string.replace("a", "z")
print(string)    # zbc

list의 경우 특정 위치의 요소를 변경하는 것에 문제가 없고, 또한 변경한 내용을 arr에 따로 넣어주지 않아도 자동으로 값이 변경된다.

 

그러나 string인 경우 문자열 abc를 replace 함수로 변경한 후 print 했을 때 변경되지 않았다.( # abc)

그 밑 코드와 같이 string에 다시 넣어주어야만 값이 변경된다.

 

즉, mutable한 객체는 특정 요소가 변경되지만, immutable한 객체는 값이 새로 생성되는 것이다.

즉, mutable은 특정 부분을 치환. immutable은 전체를 복사하여 특정 부분만 다른 새로운 객체로 만드는 것

이 차이로 인해 속도에서 차이가 나게 되는 것이다.