개발자 아지트

파이썬에서 컴프리헨션은 컬렉션을 생성하고 초기화하는 간결한 방법을 제공하는 문법이다. 

*이때, 컬렉션은 프로그래밍에서 데이터를 모아서 저장하고 관리하는 방법을 제공하는 자료구조이다. 

* 주요 컬렉션 유형으로는 리스트(list), 튜플(tuple), 딕셔너리(dictionary), 집합(set), 문자열(string)등이 있다. 

컴프리헨션은 리스트, 딕셔너리, 집합, 제너레이터 등 다양한 종류가 있다. 

주로 리스트 컴프리헨션과 딕셔너리 컴프리헨션이 많이 쓰이니 해당 부분 먼저 숙지 해두면 좋다. 

리스트 컴프리헨션

리스트 컴프리헨션은 리스트를 생성하고 초기화할 때, 간결하게 하는 방법을 제공한다. 

[ 표현식 for 반복 수행 대상 in 반복 가능한 객체 (리스트, 튜플 집합, 문자열 등) if 조건 ]

예시

numbers = [1, 2, 3, 4, 5]
sqared_numbers = [x**2 for x in numbers if x % 2 == 0]

#결과: [4, 16]

딕셔너리 컴프리헨션

딕셔너리 컴프리헨션은 딕셔너리를 생성하고 초기화할 때, 간결하게 하는 방법을 제공한다. 

{키_표현식: 값_표현식 for 항목 in iterable if 조건}

{딕셔너리의 키를 계산하는 표현식 : 딕셔너리의 값에 대한 표현식 for 반복 수행 대상 in 반복가능 객체 if 조건}

예시

numbers = [1, 2, 3, 4, 5]
sqared_numbers = {x**2 for x in numbers if x % 2 == 0}
# 결과: {2: 4, 4: 16}

리스트에 대해 인덱스와 값 쌍 출력하기 위한 방법

• enumerate()

반복문에 enumerate(리스트명) 사용하면 인덱스와 리스트 값 쌍이 나옴

# 예시

for i, key in enumerate(words):
	print(i, ': ', key)

문자열로 이뤄진 리스트나 딕셔너리에서 특정 문자로 시작하는지 확인하기 위한 함수 

• startswith()

key.startswith(num)

리스트에서 특정 원소의 인덱스를 반환해주는 함수 

• index()

key.index(num)==0

인접 리스트

# defaultdict 클래스로 그래프를 인접 리스트로 변환 할 수 있다. 
# defaultdict 클래스는 키가 없을 때 기본값을 defaultdict 형태로 기본값을 지정한다. 

# defaultdict 자료형에서는 append()를 통해 값을 추가할 수 있다. 

• defaultdict()
• append() 

from collections import defaultdict

tmp_list = defaultdict(list)

예를들어서, defaultdict(list)라고 코드 작성시 기본값은 []와 같이 초기화 한다.

tmp_list[start].append(end)

집합

• set() 집합 생성함수
• add() 집합에 객체 추가 함수 
• get() 키값을 통해 value를 조회하는 함수 

visited = set()

visited.add(node)

for injeop in node_tree.get(node, []):
# node_tree의 node에 대해 값이 있으면 해당 값의 개수만큼 개수를 출력해준다. injeop으로.
# 만약 값이 없으면, 빈 [] 리스트를 출력해준다.

우선순위 큐(Heap Queue)

파이썬 내장 모듈인  'heapq'는 최소 힙(min heap)자료구조를 제공한다. 

최소 힙은 가장 작은 요소가 항상 루트에 위치해, 최소값을 빠르게 찾을 수 있는 자료구조이다. 

• heappush() 힙큐에 요소를 추가하는 함수
• heappop() 힙큐에서 가장 작은 요소(루트에 위치한 요소)를 제거하고 반환하는 함

import heapq

# 최소 힙 생성
queue = []
heapq.heappush(queue, 5)
heapq.heappush(queue, 3)
heapq.heappush(queue, 8)

# 가장 작은 요소 제거 및 반환
smallest = heapq.heappop(queue)
print(smallest)  # 출력: 3

딕셔너리

• items() 딕셔너리의 모든 (키, 값)쌍을 반환하는 함수 

자료구조 트리를 공부하면서 이진트리 탐색 구현 부분을 공부하고 있는데, 파이썬에서 클래스의 개념을 한번 짚고 넘어가야할 것 같아서 이 글을 쓰게되었다. 

클래스가 필요한 이유

클래스를 쓰지 않아도 프로그램을 만들 수 있지만, 클래스를 사용하면 개발자에게 좋은 점이 많다.

만약 하나의 프로그램에서, 간단한 요리를 만드는 프로그램을 만든다고 가정한다. 

첫번째 요리를 레시피대로 만드는 함수 1이 있다고 하고, 함수에 들어가는 재료와, 요리 결과물을 담는 결과(그릇)가 있다고 가정한다. 

만약 이때, 첫번째 요리를 함과 동시에 두번째 요리로 요리 재료를 조금만 바꿔서 또 다른 요리를 만든다고 했을때, 

프로그램에는 함수에 들어가는 또 다른 재료와, 재료가 바뀐 결과물을 담는 결과(그릇)가 하나 더 있어야 하고

동시에 요리를 하지만 두번째 결과물(그릇)에 요리를 담아야 하므로 요리를 레시피대로 만드는 함수 2가 더 필요하다. 

만약 이때, 하나의 프로그램에서 10가지 각각 다른 요리를 만들어야 한다면? 

요리에 필요한 함수와 결과(그릇)을 일일이 하나씩 만들어줘야 한다. 그리고 레시피도 조금씩 변경되면 더 복잡해질 것이다. 

이때 필요한 것이 클래스이다. 

cooking bowl1 = 0
cooking bowl2 = 0

def recepe1(num):   
    global cooking bowl1
    cooking bowl1 += num
    return cooking bowl1

def recepe2(num):  
    global cooking bowl2
    cooking bowl2 += num
    return cooking bowl2

print(add1(3))
print(add1(4))
print(add2(3))
print(add2(7))

클래스 사용전

class Cooking:
    def __init__(self):
        self.cookingBowl = 0

    def recepe1(self, num):
        self.cookingBowl += num
        cookingBowl self.cookingBowl
    
    # 기능 추가시 해당 위치에 함수 추가

cookingBowl1 = Cooking() # 객체
cookingBowl2 = Cooking()

print(cookingBowl1.recepe1(3))
print(cookingBowl1.recepe1(4))
print(cookingBowl2.recepe1(3))
print(cookingBowl2.recepe1(7))

클래스 사용후

클래스 내부 함수를 메서드라고 부른다. 

클래스로 만든 객체의 객체변수는 다른 객체의 객체변수에 상관없이 독립적인 값을 유지한다. 

class FourCal:
    def __init__(self, first, second): # 아래의 setdata와 똑같지만, 생성자이므로 객체 생성시 자동으로 호출된다는 차이가 존재함
        self.first = first
        self.second = second
        
    def setdata(self, first, second): # 메서드
        # 파이썬 메서드에서 첫 번째 매개변수 이름은 관례적으로 self를 사용한다. 
        # 객체 호출시, 호출한 객체 자신이 전달되므로 self를 사용한다. 
        self.first = first
        self.second = second

    def add(self):
        sum = self.first + self.second
        return sum
    
    def sub(self):
        sum = self.first - self.second
        return sum
    
    def mul(self):
        sum = self.first * self.second
        return sum
    
    def div(self):
        sum = self.first / self.second
        return sum


# 상속
    # FourCal 클래스를 상속하는 MoreFourCal클래스이다. 
    # 기존 클래스를 수정하지 않고 상속을 이용하는 이유는?
    # 기존 클래스가 라이브러리 형태로 제공되거나 수정이 불가한 상황일 때 사용한다. 

class MoreFourCal(FourCal):
    def pow(self):
        result = self.first ** self.second
        return result
    

class SafeFourCal(FourCal):
    def div(self):
        if self.second == 0:
            return 0
        else:
            return self.first / self.second

# 부모 클래스에 있는 메서드를 같은 이름으로 다시 만드는 것을
# 메서드 오버라이딩 이라고 한다. 
# 이럴 경우 기존 부모 클래스의 div함수가 아닌 오버라이딩한 메서드가 호출된다. 
        

class Friend:
        lastname = "배" # 클래스 변수: 클래스 안에 변수를 선언하여 생성

classVar = Friend()

name = classVar.lastname
print('name: ',name)

Friend.lastname = "이"
name = classVar.lastname
print('name: ',name)


# 객체 변수와 다르게 클래스 변수는 모든 객체에 공유된다.
# 클래스 변수와 같은 이름의 객체 변수 생성이 가능하다. 

classVar.lastname = "최"
name2 = classVar.lastname
print('name2: ', name2)

print('name: ',name)
# 기존의 classVar 클래스의 lastname과는 상관 없다. 
# 즉, classVar 클래스의 클래스 변수 lastname은 변하지 않았음


#a = FourCal() # 생성자를 만든 후에는 안에 인자를 넣어줘야 값이 전달된다. 

# a.setdata(4, 2) 
    
a = FourCal(4, 2) 

# 객체를 이용해 클래스의 메서드 호출 시 .연산자 사용
# FourCal클래스의 setdata메서드는 인자가 self, first, second로 3개임
# 그런데 왜 객체 a의 메서드 호출시에는 2개의 인자만 사용되어도 문제가 없는걸까?
# 객체 a가 setdata의 self로 자동으로 전달되기 때문이다. 


# 만약 객체 생성시 초기값을 설정 해주지 않고, 객체로 다른 메서드를 호출한다면
# 오류가 발생한다. 

# 이를 방지하기 위해 생성자를 구현해두는 것이 안전하다. 
# 생성자는 객체가 만들어질 때 자동으로 호출되는 메서드를 말한다. 

# 파이썬 메서드 명으로 __init__을 사용하면 해당 메서드는 생성자가 된다.

c = a.add()
print(c)

b = MoreFourCal(4, 2) # 클래스는 상속받은 FourCal 클래스의 모든 기능을 사용할 수 있다. 

d = b.add()
print(d)

순회 방법

• 전위 순회(preorder)
  • 현재 노드를 부모로 생각하고, 부모노드 부터 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 방문
  • 현재노드(부모)-> 왼자식 -> 오른자식
• 중위 순회(inorder)
  • 현재 노드를 부모로 생각하고, 왼쪽 자식노드 부터 부모노드, 오른쪽 자식 노드 순으로 방문
  • 왼자식-> 현재노드(부모)->오른자식
• 후위 순회(postorder)
  • 현재 노드를 부모로 생각하고, 왼쪽 자식 노드 부터 오른쪽 자식 노드, 부모 노드 순으로 방문 
  • 왼자식->오른자식->현재노드(부모)

해시는 해시 함수를 통해 변환한 값을 인덱스처럼 사용하고, 키와 값을 저장하여 데이터 탐색을 빠르게 할 수 있다. 

해시는 키를 사용해서 데이터 탐색을 빠르게 한다. 

값을 검색하기 위해서 활용하는 것은 키고, 키를 통해 해시값이나 인덱스로 변환할 때는 해시 함수를 통한다. 이때, 해시 함수는 키를 일정한 해시 값으로 변환 시킨다. 

해시의 특징

1. 해시는 키를 통해 값을 찾을 수 있지만, 값을 통해 키를 찾을 수는 없다. 

2. 키 자체가 해시함수를 통해 값이 포함된 인덱스이므로 값을 찾기 위한 과정이 필요 없다. 따라서 탐색은 O(1)의 시간복잡도가 걸린다. 

3. 값을 인덱스로 활용하기 위해서는 적절한 변환 과정을 거쳐야 한다. 

해시 테이블은 키와 대응한 값이 저장되어 있는 공간이고, 해시 테이블의 각 데이터를 버킷이라고 한다. 

해시 함수

해시 함수 구현시 고려 사항

1. 해시 함수를 통한 결과는 해시 테이블의 크기인 0~(N-1) 사이의 값을 내야한다. 

2. 해시 함수가 변환한 값의 충돌(중복 발생)은 최대한 작은 확률로 일어나게끔 해야한다.  (충돌 발생은 불가피함)

자주 사용하는 해시 함수

나눗셈법

나눗셈법에 소수가 아닌 수를 사용하면 충돌이 많이 발생한다. 

따라서 나눗셈법의 해시 테이블의 크기는 소수를 사용해야한다. 

이렇게 하면, 나눗셈법의 해시 테이블 크기는 K가 된다.

왜냐하면 K에 대해 나머지 연산(모듈러 연산)을 했을 때, 나올 수 있는 값은 0 ~ (K - 1)이기 때문이다. 

그러나, 매우 큰 소수를 구하는 방법 중 효율적인 방법은 없다는 점이 단점이다. 

곱셈법

곱셈법도 나눗셈법 처럼 모듈러 연산을 활용하지만 소수는 사용하지 않는다. 

곱셈법의 공식 

 h(x) = ((( x * A ) mod 1 ) * m)

m은 최대 버킷의 개수, A는 황금비이고 무한소수이지만, 소수부의 일부인 0.6183만 이용한다. 

1. 키에 황금비를 곱한다. 

2. 1번 결과에 모듈러 1을 취한 후, 소수 부분만 취한다. 

3. 2번 결과 값에 테이블 크기 m을 곱한다. 

3번 결과를 통해 테이블의 인덱스인 0 ~ (m - 1)에 매치할 수 있다. 

곱셈법은 소수가 필요없고, 테이블의 크기가 커져도 추가 작업이 필요없다. 

문자열 해싱

키의 자료형이 문자열일 때, 문자열을 해싱하는 방법은 다음과 같다. 

문자열의 문자를 숫자로 변환해준 후, 테이블의 인덱스에 매칭될만한 값으로 숫자를 다듬어주면 된다. 

문자열을 해싱하기 위해 사용하는 다항식 rolling method이다. 

hash(s) = (s[0] + s[1]*p + s[2]*p^2  … s[n-1]*p^n-1) mod m

문자열의 문자를 숫자로 변환해준 후, 테이블의 인덱스에 매칭될 만한 값으로 숫자를 다듬어 줄 때, 

중간 중간에 모듈러 연산을 한 후 더한값에 대해 모듈러 연산을 하게되면 오버플로우를 최대한 방지할 수 있다. 

*** 일반적인 수식에도 모듈러 연산이 있는 문제중에서 큰 수를 다루는 문제는 오버플로우를 어떻게 처리하는지 확인하는 함정이 있으니, 유의해야한다. 

충돌 처리

해시 테이블은 충돌 발생이 불가피 하므로, 반드시 충돌 처리를 해줘야한다. 

체이닝

충돌 처리는 체이닝으로 처리할 수 있다. 

체이닝은 해싱한 값중 중복값이 나올 경우, 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결하는 방법이

다.

그러나 이 방법에는 두가지 단점이 존재한다. 

1. 충돌이 많아질 경우, 링크드리스트의 길이가 길어지고 사용하지 않은 해시 테이블의 공간은 덜사용하게 되므로 공간 활용성이 떨어진다. 

2. 충돌이 많아질 경우, 링크드리스트의 한계로 인해 검색 성능이 떨어진다. 

왜냐하면, 링크드리스트로 검색할때 맨 처음부터 검색하기 때문이다. 

최악의 경우, O(N)의 시간복잡도가 발생할 수 있다. 

개방 주소법

이를 개방 주소법으로 개선할 수 있다. 
개방 주소법은 체이닝과 달리, 빈 버킷을 찾아서 충돌값을 삽입한다. 

이 방법은 체이닝보다 메모리를 더 효율적으로 사용하는 방법이다. 

개방 주소법 중 하나로 선형 탐사 방식이 있다. 

이 방식은 충돌발생 시 다른 빈 버킷을 찾을 때 까지 일정한 간격으로 이동한다. 

h(k, i) = (h(k) + i) mod m

*보통 간격은 1로 한다

단, 이 방법에도 단점이 있다. 

충돌 발생 시 한 칸씩 이동하며 해시 테이블의 빈 곳을 찾아서 값을 넣을 경우, 해시 충돌이 발생한 값끼리 모이는 영역이 발생한다. 이를 클러스터를 형성한다고 한다. 이런 영역이 발생하면 해시값이 충돌할 확률이 더 높아진다. 

이를 개선하기 위해 이중 해시 방식이 있다. 

이 방식은 해시 함수를 2개 사용하는 방식이다.  N개로도 늘려서 사용할 수 있다. 

첫번째 해시 함수는 기존 해시 함수의 역할을 수행하고, 두번째 해시 함수의 역할은 첫 번째 해시 함수의 결과로 충돌이 발생하면, 해당 위치를 기준으로 위치를 어디로 정할지 새로 결정하는 역할을 한다. 

*h1은 1차 해시함수, h2는 2차 해시함수이다. 

h(k,i) = (h1(k) + i * h2(k)) mod m

수식을 보면 선형 탐사 방식과 비슷하지만 클러스터를 줄이기 위해, m을 제곱수나 소수로 한다. 

실제 코테 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정이다. 

특정 값이나 정보를 기준으로 자주 검색하거나 특정 값과 매핑 값의 관계를 확인해야 하는 작업이 문제에 포함되면 해시를 고려해봐야 한다. 

front와 rear을 사용하는 큐는 원형 큐에 비해서 메모리 낭비가 있는 편이다. 

파이썬에서 원형 큐를 사용하기 위해서는 리스트나 덱을 활용하여 구현할 수 있다. 

리스트를 큐 처럼 사용하기 

queue = []

# 큐에 데이터 추가

queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거 

first_item = queue.pop(0)
print(first_item) # 출력: 1

# 큐에 데이터 추가
queue.append(4)

 #  큐의 맨 앞 데이터 제거 
first_item = queue.pop(0)
print(first_item) # 출력: 2

덱을 큐처럼 활용하기 

# deque = Double Ended Queue의 줄임말 
# 양 끝에서 삽입이나 삭제할 수 있는 큐 
# 위의 특징 때문에 큐를 구현할 때 덱을 사용하는 것이 좋음

from collections import deque

queue = deque( )

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거 

first_item = queue.popleft()
print(first_item) # 1

# 큐에 데이터 추가 
queue.append(4)

# 큐의 맨 앞 데이터 제거 

first_item = queue.popleft()
print(first_item) # 2

*pop(0)이 popleft()보다 훨씬 느리므로, 반드시 pop(0) 대신에 popleft() 를 사용할 것.

6장 스택

스택의 개념 

• 먼저 입력한 데이터를 제일 나중에 꺼낼수 있는 자료구조
• 맨 나중에 입력한 데이터를 제일 먼저 꺼낼 수 있는 자료구조
• 스택에 삽입하는 연산을 Push이라고 함
• 스택에서 꺼내는 연산을 Pop이라고 함

스택의 정의

ADT(Abstract data type) 추상 자료형이다. 

이때, 추상 자료형은 인터페이스만 있고 실제로 구현은 되지 않은 자료형을 말한다. 

즉, 구현되지 않은 설계만 된 자료형이라고 생각하면 된다. 

스택을 ADT형태로 정의해보면 다음과 같다. 

스택의 요소는 다음과 같다. 

• 푸시 Push(반환타입 - 없음)
• 팝 Pop (반환타입 - 아이템의 반환타입)
• 가득 찼는지 확인 isFull (반환타입 - boolean 타입)
• 비었는지 확인 isEmpty (반환타입 - boolean 타입)
• 최근에 삽입한 데이터의 위치를 저장할 변수인 탑 Top (반환타입 - int 타입)
  • 통상적으로 Top은 -1로 초기화 한다
  • Top이 0이 되면 값이 하나 있다는 의미이다. 
• 스택의 자료를 관리하는 배열 (아이템 타입 data[maxsize])

스택의 세부 동작

이번 포스팅에서 이 부분이 제일 중요하다. 

파이썬과 같은 언어로 스택을 구현하면 위에있는 모든 추상자료형의 요소들을 구현하지 않아도 스택을 쉽게 구현할 수 있다. 

그러나 뭐든지간에 본질이 기본이되어야 하는법이다. 

본질적인 것만 알면 스택에 관한건 통!! 한다. ㅎㅎ 

스택의 세부 동작은 다음과 같은 두 경우를 통해 설명하겠다. 

[스택에 3을 push 하는 경우]

1. isFull을 통해 push하고자 하는 스택에 공간이 있는지 확인한다. 
2. 공간이 있다면, top의 값을 +1한다.
3. 해당 인덱스의 칸에 데이터를 삽입한다. 

[스택에 3을 pop 하는 경우]

1. isEmpty를 통해 pop하고자 하는 스택이 혹시 빈공간은 아닌지, 꺼낼 값이 없는건 아닌지 확인한다. 
2. 값이 있다면, top의 값을 -1 한다.
3. top의 값을 -1하기 전의 값을 반환한다.

이때 반환한 값, 배열의 데이터를 지우거나 하지 않는다. 

top의 값만 -1을 해준다. 

향후 이것은 아무 문제가 되지 않는다. 왜냐하면 top은 -1이 된 위치를 가리키기는데, isEmpty라던지 isFull을 통해 스택의 내부 사정을 물어볼 때 top을 통해 상태를 확인하기 때문이다. 

파이썬에서는 list자료 구조(그 외의 다른 자료구조 또한 사용가능), append()나 pop(), len()을 통해 스택을 쉽게 구현할 수 있다. 

5장 배열 

배열의 개념 

배열은 자료구조로서 데이터를 저장할 수 있는 모든 공간마다 인덱스와 일대일 대응한다. 

따라서 어떤 위치에 있는 데이터든 한 번에 접근할 수 있어서 인덱스만 알면 데이터를 빠르게 탐색할 수 있다. 

이런 접근 방식을 임의 접근(random access)라고 한다. 

배열 선언

1)배열 선언의 방법 

일반적인 방법

arr = [0, 0, 0, 0, 0, 0]
arr = [0] * 6
# 두 코드의 결과 값은 동일하다.

리스트 생성자를 사용하는 방법

arr = list(range(6)) # [0, 1, 2, 3, 4, 5]

리스트 컴프리헨션을 사용하는 방법 

arr = [ 0 for _ in range(6)) # [0, 0, 0, 0, 0, 0]

2)배열의 특징

• 배열은 인덱스가 0부터 시작한다. 
• 파이썬의 경우 배열을 지원하는 문법은 없고 대신 리스트 문법을 사용하면 된다. 
• 파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어있고, 슬라이싱, 삽입, 삭제, 연결 등 연산을 사용할 수 있어서 편리하다. 

배열과 차원

배열은 2차원, 3차원 등 다차원 배열로 존재할 수 있다. 

하지만 컴퓨터 메모리는 1차원이다. 때문에 배열은 차원과 무관하게 메모리에 연속적으로 할당된다. 

1) 1차원 배열

만약 배열이 0번부터 10번까지 있다면 0번 배열에는 낮은 메모리 주소에서 시작하여 10번 배열까지는 오름차순으로 메모리 주소가 높아진다. 

2) 2차원 배열 

# 2차원 배열을 리스트로 표현하면 다음과 같다. 
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

# 2차원 배열을  다음과 같이 출력할 수 있다. 
print(arr[2][3]) #12 출력

#arr[2][3]에 저장된 값을 15로 변경
arr[2][3] = 15

#변경된 값을 출력
print(arr[2][3]) # 15

리스트 컴프리헨션을 사용하면 다음과 같이 선언할 수 도 있다. 

# 크기가 3 * 4인 리스트를 선언하는 예시
arr = [[i] * 4 for i in rnage(3)] #[[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

배열 연산의 시간 복잡도

배열은 임의 접근이라는 방식으로 접근함으로 모든 위치에 있는 데이터를 한번에 접근할 수 있다. 

따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

배열 데이터에 맨 앞에 다른 새로운 데이터를 추가한다면, 기존에 있던 데이터는 뒤로 한칸씩 밀어야 한다. 

따라서 이를 위한 연산이 필요한데, 이때 총 데이터의 개수가 N개라면 이를 위한 연산의 시간 복잡도는 O(N)이 된다. 

만약 배열의 데이터의 중간에 다른 데이터를 삽입할 경우 중간 이후에 있는 데이터를 뒤로 한칸씩 밀어야한다. 

중간 이후에 있는 데이터가 N개라면 이를 위한 연산의 시간 복잡도는 O(N)이 된다. 

== 배열은 특정한 경우에 따라서 데이터 추가나 삭제에 드는 비용이 많을 수 있다. 

배열을 선택할 때 고려할 점 

배열은 임의 접근이라는 특징으로 인해 인덱스를 통해 데이터로 바로 접근할 수 있어서 데이터에 빈번하게 접근하는 경우에 효율적이지만, 메모리 낭비가 발생할 수 있다. 따라서 다음과 같은 사항을 고려해야한다. 

1. 할당할 수 있는 메모리의 크기 확인(배열로 표현하고자 하는 데이터에 대한 메모리의 크기 확인)

2. 중간이나 맨 앞에 데이터 삽입이 빈번한가?(이럴 경우 시간복잡도가 높아짐)

(단, 현재 파이썬에서 리스트로 배열을 구현함으로써 배열 크기에 대한 고민은 하지 않아도 되고, 배열의 특성정도로만 이해하면 됨)

배열 구현을 위해 자주 사용하는 파이썬 리스트 기법

리스트에서 데이터 추가하기 

append() 메서드로 데이터 추가하기 

# 리스트의 맨 끝에 데이터 추가 
tmp_list = [1, 2, 3]
tmp_list.append(4) # [1, 2, 3, 4]

+연산자로 데이터 추가하기 

tmp_list = [1, 2, 3]
tmp_list = tmp_list + [4, 5]  # [1, 2, 3, 4, 5]

insert() 메서드로 데이터 추가하기 

tmp_list = [1, 2, 3, 4, 5]
tmp_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]

리스트에서 데이터 삭제하기 

pop() 메서드로 특정 위치의 데이터 팝

tmp_list = [1, 2, 3, 4, 5]
popped_element = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2, 4, 5]

remove() 메서드로 특정 데이터 삭제 

- 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제함 

tmp_list = [1, 2, 3, 2, 4, 5]
tmp_list.remove(2) # [1, 3, 2, 4, 5]

리스트 컴프리헨션으로 데이터에 특정 연산 적용

리스트에 제곱 연산 적용 예

numbers = [1, 2, 3, 4, 5]
squares = [num**2 for num in numbers] # [1, 4, 9, 16, 25] 이래도 nubers는 여전히 [1, 2, 3, 4, 5]임

4장 코딩테스트에 필요한 필수 문법 

빌트인 데이터 타입

파이썬의 데이터 타입은 다음과 같다. 

정수형 산술 연산에서 헷갈리는 부분만 코드를 통해 기술하였다. 

a = 13
b = 4

print(a / b)  # 나누기 (소수점 포함) 3.25
print(a // b) # 나누기 (소수점 제외)  3
print(a % b)  # 모듈러 연산 (나머지) 1
print(-a)     # 부호를 바꿈 -13
print(abs(-a))# 절대값 13
print(a**b)   # a의 b승 28561

정수형 비트 연산 정리는 코드를 통해 기술하였다. 

print(a & b) # AND 4
print(a | b) # OR 13
print(a ^ b) # XOR 9
print(~a) # NOT -14
print(a << 2) # 왼쪽 시프트 (a에  2^2를 곱한 것과 동일) 52
print(a >> 1) # 오른쪽 시프트 (a를 2^1로 나눈 것과 동일) 6

정수형 논리 연산 정리는 코드를 통해 기술하였다. 

print(a and b)   # 논리 연산 AND 4
print(a or b)    # 논리 연산 OR 13
print(not a)     # 논리 연산 NOT False

부동소수형 데이터를 다룰 일이 생겼을 때 엡실론을 항상 생각해야 한다. 

• 앱실론이란? 파이썬 부동소수형 데이터를 이진법으로 표현하기 때문에 표현 과정에서 발생하는 오차를 말한다. 

컬렉션 데이터 타입에서 컬렉션은 여러 값을 담는 데이터 타입을 말한다. 

대표적으로 리스트, 튜플, 딕셔너리, 셋, 문자열 등이 있다. 

여기서 데이터 수정 여부에 따라 뮤터블객체(변경할 수 있는 객체), 이뮤터블객체(변경할 수 없는 객체)로 구분할 수 있다. 

뮤터블 객체의 리스트는 사용 방법은 5장 배열의 코드를 통해 기술하였다. 

인덱싱은 인덱스를 활용해 특정 위치의 원소에 접근하는 것을 말한다. 

리스트 슬라이싱 방법은 코드를 통해 기술하였다. 

tmp_list = [1, 2, 3, 4, 5]
print(tmp_list[0:2])   # [1,2]
print(tmp_list[1:])    # [2, 3, 4, 5]
print(tmp_list[3:4])   # [4]
print(tmp_list[-4:-2]) # [2, 3]

딕셔너리에 대한 정리는 코드를 통해 기술하였다. 

# 딕셔너리 선언
tmp_dict = { }

# 딕셔너리 값 삽입
tmp_dict["mouse"] = 1
tmp_dict["keyboard"] = 2
tmp_dict["monitor"] = 3

# 딕셔너리 값 출력
print(tmp_dict) # {'mouse': 1, 'keyboard': 2, 'monitor': 3}

# 딕셔너리 값 검색
key = "mouse"
if key in tmp_dict:
	value = tmp_dict[key]
    print(f"{key}: {value}") # mouse: 1
else:
	print(f"{key}는 딕셔너리에 존재하지 않음")

# 딕셔너리 값 삭제
del tmp_dict["mouse"]
print(tmp_dict) # {'keyboard': 2, 'monitor': 3}

튜플에 대한 정리는 코드를 통해 기술하였다. 

리스트, 딕셔너리와 달리 한 번 생성하면 삽입하거나 삭제할 수 없다. 

# 튜플 초기화 
tmp_tuple = (1, 2, 3)

# 튜플 인덱싱, 슬라이싱 
# 문법 자체는 리스트와 같다. 

# 인덱싱
python(tmp_tuple[0]) # 1
python(tmp_tuple[1]) # 2
python(tmp_tuple[2]) # 3

# 슬라이싱

python(tmp_tuple[1:])  # (2, 3)
python(tmp_tuple[:2])  # (1, 2)
python(tmp_tuple[1:2]) # (2,)

리스트도 있는데 굳이 튜플을 쓰는 이유는 실수로 값을 변경하는 실수를 방지하기 위함이다. 

문자열에 대한 정리는 코드를 통해 기술하였다. 

# 문자열 추가 
string = "h"
string += "i"
print(string). # "hi"

# 문자열 수정
string = "hii"
string = string.replace("ii", "") # "i"를 모두 삭제
print(string)					  # H

함수의 람다식에 대한 정리는 코드를 통해 기술하였다. 

lambda x, y : x + y # x와 y를 받아서 더한 값을 반환하는 람다식 

# 람다를 이용한 간단한 함수 정의
add = lambda x, y: x + y
print(add(5, 4)) # 9

num = [1, 2, 3, 4, 5]
squares = list(map(lambda x: x**2, num))
print(squares) # [1, 4, 9, 16, 25]

코딩 테스트 구현 노하우는 3가지이다. 

조기반환은 코드 실행 과정에 있어서 함수 끝까지 가기전에 반환하는 기법이다. 이를 통해 코드의 가독성을 높이고 예외를 깔끔하고 빠르게 처리할 수 있다. 조기반환에 대한 정리는 코드를 통해 기술하였다. 

def total_price(quantity, price):
	total = quantity * price
    if total > 100:
    	return total * 0.9
        # 이렇게하면 이후 예외에 대한 처리를 하지 않아도 된다. 
    return total 
    
print(total_price(4, 50))

보호구문은 본격적인 로직을 진행하기 전 예외 처리 코드를 추가하는 기법임.
예를 들어 조건문을 사용해 초기 입력값이 유효한지 검사하고, 그렇지 않으면 바로 함수를 종료하는 보호 구문을 쓸 수 있음 

def calculate_average(numbers):
	if numbers is None:
    	return None
    
    if not isinstance(numbers, list): # numbers가 리스트가 아니면 종료(예외)
    	return None
        
    if len(numbers) == 0: # numbers의 길이가 0이면 종료(예외)
    	return None
        
    total = sum(numbers)
    average = total / len(numbers)
    return average

합성함수는 2개 이상의 함수를 활용해 함수를 추가로 만드는 기법임

이는 람다식을 활용하여 구현한다. 

def add_three(x):
	return x + 3
    
def square(x):
	return x * x
    
composed_function = lambda x: square(add_three(x))
print(composed_function(3)) # 36