개발자 아지트

재귀 함수란?

: 재귀 함수는 자기 자신을 호출하여 원래 문제에 속한 더 작은 하위 문제를 해결하는 함수이다.

이를 통해 문제를 반복적으로 분해하다가, 더 이상 분해할 수 없는 기본 조건(base condition)에 도달하면 함수 호출을 종료한다. 

재귀 함수의 장점과 단점은 무엇인가?

 장점

• 코드가 반복적인 구조를 가진 문제(예: 특정 패턴의 탐색)를 간결하게 작성할 수 있습니다.
• 문제를 작게 나누어 해결하는 경우 구현이 상대적으로 단순해집니다.

단점

• 잘못된 구현이나 불필요한 깊이의 호출이 발생하면 성능이 저하될 수 있습니다.
• 깊은 재귀 호출로 인해 프로그램이 강제 종료될 가능성도 있습니다.

 재귀 함수에서 재귀 깊이를 줄이기 위한 방법

재귀 함수는 깊이(호출의 반복 횟수)가 깊어질수록 성능에 악영향을 줄 수 있다.

이때, 재귀 깊이를 줄이기 위한 몇 가지 방법을 사용할 수 있다.

메모제이션(Memoization)
이전에 계산한 값을 저장해 두었다가 재사용하는 기법이다.

이를 통해 동일한 계산을 여러 번 반복하지 않게 되어 재귀 호출 횟수를 줄일 수 있다.

memo = {}
def fibonacci(n):
   if n in memo:
       return memo[n]
   if n <= 1:
       return n
   memo[n] = fibonacci(n-1) + fibonacci(n-2)
   return memo[n]

반복문으로 변환
재귀로 풀 수 있는 문제는 대부분 반복문을 통해 해결할 수도 있다.

반복문으로 변환할 경우, 재귀 함수 호출로 인한 추가적인 메모리 사용을 방지할 수 있다.

 def fibonacci_iterative(n):
       a, b = 0, 1
       for _ in range(n):
           a, b = b, a + b
       return a

최적화된 종료 조건 설정
재귀 호출의 종료 조건을 잘 설정하면 불필요한 깊은 호출을 방지할 수 있다.

특히, 매번 상태를 변경하거나 갱신하여 기본 조건에 빨리 도달하도록 설계해야 한다.

재귀 함수를 구현하는 절차

1. 기본 조건 설정 (Base Condition):

기본 조건은 재귀 호출이 끝나야 할 시점을 정의하는 것이다.

만약 기본 조건이 없다면, 함수가 계속해서 자기 자신을 호출하여 무한 루프에 빠지게 되고, 결국 스택 오버플로우 오류를 발생시킨다.

기본 조건은 문제의 가장 작은 단위를 처리하는 코드로 작성해야 하며, 일반적으로 재귀 호출의 종료를 의미합니다. 

2. 더 작은 문제로 분할:

재귀의 핵심은 문제를 작은 문제로 나누는 것이다. 원래 문제를 더 작은 하위 문제로 분할함으로써, 최종적으로 기본 조건에 도달할 수 있다. 하위 문제는 원래 문제와 동일한 성질을 가져야 한다. 이렇기 때문에 재귀 호출이 문제를 반복적으로 해결할 수 있게 되는 것이다. 

또한 각 재귀 호출에서 문제의 크기를 줄여야 한다는 것이다. 만약 문제의 크기가 줄어들지 않으면, 기본 조건에 도달할 수 없게 되어 함수가 계속해서 호출되는 문제가 발생한다.

3. 재귀 호출:

마지막 단계는 재귀적으로 자기 자신을 호출하는 것이다. 이때, 더 작은 문제를 해결하기 위해 동일한 함수를 호출하게 된다. 재귀 호출은 기본 조건에 도달할 때까지 계속되며, 기본 조건에 도달하면 결과가 반환되기 시작한다.

이 과정에서 주의할 점은, 함수가 재귀 호출을 할 때마다 상태가 변화해야 한다는 것이다. 그렇지 않으면 문제의 크기가 줄어들지 않아 무한 루프에 빠질 수 있다.

재귀 함수 구현 시 주의해야 할 점

1. 기본 조건을 확실하게 설정해야 한다.
2. 재귀 깊이 고려해야 한다. 

재귀 호출은 호출할 때마다 메모리의 스택 공간을 사용한다. 따라서 재귀 호출이 너무 깊어지면 메모리가 부족해질 수 있다. 특히, Python에서는 재귀 깊이가 기본적으로 제한되어 있어, 그 한도를 넘어서면 RecursionError가 발생한다.

따라서 재귀 깊이를 고려하여 설계해야 하며, 가능한 경우 반복문을 통해 문제를 해결하는 방법도 고려해야 합니다. 혹은 sys.setrecursionlimit() 함수를 사용해 최대 재귀 깊이를 조정할 수 있습니다.

import sys

# 재귀 깊이 제한을 늘리기
sys.setrecursionlimit(2000)

그러나 이 방법은 메모리 사용량을 늘리기 때문에 신중히 사용해야 한다.

3. 반복적 재계산을 방지해야한다. 
많은 재귀 함수에서 동일한 하위 문제를 여러 번 계산하는 경우가 발생할 수 있다. 이로 인해 중복 계산이 일어나고 성능이 크게 저하될 수 있다. 이를 방지하기 위해 메모이제이션(Memoization)을 사용하여 이미 계산된 값을 저장하고 재사용하는 방법을 고려해야 한다.

출처: "코딩 테스트 합격자 되기-박경록" 

7-1. 큐의 개념

큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 

일상생활에서 줄 서는 것이 큐 구조이다. 먼저 선 사람이 먼저 들어간다. 

이런 큐의 특징을 선입선출, FIFO(First in First out) 이라고 한다. 

큐도 스택처럼 꺼내는 연산을 팝, 삽입하는 연산을 푸시라고 한다. 

*큐의 특성을 활용하는 분야 

큐의 동작 방식은 프로그래밍 언어에서 많이 활용된다. 대표적으로 여러 이벤트가 발생했을때 발생한 순서대로 처리가 필요할 때 큐가 활용된다. 작업 대기열이나 이벤트 처리의 경우 큐 구조로 처리된다. 

큐의 ADT(abstract data type, 추상자료형)

*연산

*상태

front는 큐의 앞, rear는 큐의 뒤를 의미한다. 

큐는 앞에서 데이터를 꺼내고(팝), 뒤에서 데이터를 넣으므로(푸시) 이렇게 앞 뒤의 최종 데이터의 위치를 기억해야한다. 

초기에는 front와 rear모두 초깃값을 -1로 설정한다. 

*큐의 세부동작 이해하기 

푸시 연산 

1. isFull() 연산을 통해 현재 큐가 가득 찼는지 확인한다. 

2. 큐가 가득 차지 않았다면, rear을 +1 하고 다음 rear가 가리키는 위치에 값을 푸시한다. 

팝 연산

1. isEmpty() 연산을 통해 큐가 비었는지 확인한다. 해당 연산을 통해 front, rear의 값이 같은지 확인해서 큐에 원소가 없는데 팝하는 동작을 방지한다. 

2. 만약 큐가 비어있지 않다면 front을 +1 한다. 이렇게 하면 front, rear가 0으로 같아지고, 

3. isEmpty() 연산 시 큐가 빈것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있다. 

front의 다음 부터 rear까지만 큐가 관리하는 데이터라고 생각해야 한다. 

이런식으로 큐를 관리하다보면, 실제 data 공간에 비해 큐가 관리하는 데이터가 줄어들게 되면 메모리 공간을 낭비한 상황을 만날 수 있다. 이렇게 된 이유는 큐를 한 방향으로 관리하기 때문이다. 이렇게하면, fornt 이전의 부분을 활용할 수 없게된다. 

이를 개선하기 위해 원형 큐를 사용한다. 

코딩테스트에서 파이썬을 사용하면 그냥 리스트만 사용해도 충분하게 이런 형태들의 큐를 사용할 수 있다. 

* 큐 구현하기 

큐를 간단하게 구현하는 방식은 크게 2가지가 있다. 

1. 리스트를 활용하는 방식

queue = []

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

# 큐의 맨 앞 데이터 제거, 스택과의 차이는 pop()에 인수로 0을 넣어 맨 앞 데이터를 제거했다는 점이다
first_item = queue.pop(0)
print(first_item) # 출력: 1

2. 덱을 활용하는 방식

from collections import deque

queue = deque()

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

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

실제로 큐를 구현할 때 덱을 사용하는 이유는 속도 때문이다. 

pop(0)을 10 만번하면 0.79초가 소요되고,

popleft()를 10 만번하면 0.007초로 매우 크게 차이가 난다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

6-1. 스택 개념

스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 

먼저 들어간 것이 마지막에 나오는 규칙을 선입후출, FILO(First In Last Out)이라고 한다. 

이때, 스택에 삽입하는 연산을 push, 빼는 연산을 pop이라고 한다. 

6-1. 스택의 정의

스택 자료형의 동작 형태를 설계하는 것은 추상 자료형(ADT)을 정의하는 것이다. 

추상 자료형ADT(abstract data type) 이란?

=> 인터페이스만 있고 실제 구현은 되지 않은 자료형

스택은 push, pop, 스택이 가득 찼는지 확인(isFull), 스택이 비었는지 확인isEmpty)과 같은 연산을 정의해야 한다. 

또한 스택에는 최근에 삽입한 데이터의 위치(현재 가리키는 인덱스)를 저장할 함수인 top도 있어야 한다. 

스택 구현하기

스택은 최근에 삽입한 데이터를 대상으로 뭔가 연산 해야 할 경우 적합. 

# 스택 ADT 구현

stack = [] #스택 리스트 초기화 
max_size = 10 # tmxordml 최대 크기 

def ifFull(stack):
    # 스택이 가득 찼는지 확인하는 함수 
    return len(stack) == max_size

def isEmpty(stack):
    # 스택이 비어있는지 확인하는 함수 
    return len(stack) == 0

def push(stack, item):
    # 스택에 데이터를 추가하는 함수
    if ifFull(stack):
        print("스택이 가득 찼다.") 
    else:
        stack.append(item)
        stack.append("데이터가 추가됐다. ")

def pop(stack):
    # 스택에서 데이터를 꺼내는 함수
    if isEmpty(stack):
        print("스택이 비었다. ")
        return None
    else:
        return stack.pop()

그러나 파이썬의 리스트는 크기를 동적으로 관리하기 때문에 max_size나 isFull(), isEmpty()함수는 따로 구현하지 않는다. 

코드의 push(), pop()함수는 기존의 원소 추가 함수append(), 원소 꺼내는 함수 pop()이 있기 때문에 따로 구현하지 않아도 된다. 

주의: 실전에서는 문제에 스택을 활용해야 풀 수 있다는 생각을 하지 못해서 문제를 풀지못하는 경우가 대부분임

따라서 스택 관련 문제를 많이 풀어보고, 해당 문제는 스택을 사용하면 좋겠다는 감을 익히는 것이 중요함

질문

1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요. 이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.

답:

<스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계>

문자열의 길이가 n이라고 가정한다. 

1. 문자열의 문자를 임의의 리스트에 하나씩 넣는다. 

2. 빈 임의의 문자열 변수를 하나 선언한다. 

3. 임의의 리스트에서 pop()을 하여 꺼낸 값을 빈 임의의 문자열 변수에 + 연산을 하여 추가한다. 

3번은 문자열의 길이만큼 행한다. 

<위 알고리즘의 시간 및 공간 복잡도>

전체 시간복잡도 = 1번 과정에 대한 시간 복잡도 n + 3번 과정에 대한 시간복잡도 n^2 = O(n^2)

전체 공간 복잡도 = 문자열의 길이 n만큼 nbyte = O(n)

<스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법>

파이썬의 슬라이스를 사용해 뒤집는 방법이 있다. 

2. 스택이 재귀적인 함수 호출과 어떻게 관련이 있는지 설명해 보세요. 재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법을 예시를 통해 설명할 수 있나요?

답:

<스택이 재귀적인 함수 호출과 어떻게 관련이 있는가?>

재귀적인 함수 호출은 함수 호출 조건을 5로 준다면, 첫번째로 함수를 호출 한것이 해당 함수를 두번째로 호출하게되고 두번째로 호출 한 함수에서 해당 함수를 세번째로 호출하게 되고 , , ,이런식으로 진행이 되다가 조건에 따라 추가적인 함수 호출을 하지않게 된다. 마지막으로 함수를 호출한 것이 실행되면서 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 네번째로 호출한 함수에서 다섯번째로 함수 호출한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 세번째로 호출한 함수에서 네번째로 함수 호출을 한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다... 이렇게 첫번째 함수까지 처리되어 재귀 함수의 실행이 끝난다. 

이렇듯 재귀적인 함수의 호출은 스택의 LIFO(Last In, First Out) 원칙에 따라 진행되는 것을 알 수 있다. 

<재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법과 그 예시>

비재귀적 방식이란 함수가 자기 자신을 호출하지 않고, 대신 반복문과 같은 구조를 사용해서 문제를 해결하는 방식이다. 

예를들면 대상인 피보나치 함수를 재귀로 구현하면 다음과 같다. 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
print(fibonacci(3))

위 재귀 함수를 비재귀적 방식으로 다시 구현하면 다음과 같다. 

def fibonacci(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    
    return b

print(fibonacci(3))

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

5-1. 배열 개념

배열은 인덱스와 값을 1대 1 대응하여 관리하는 자료구조이다. 

배열은 인덱스를 통해 어떤 위치에 있는 값이든 한 번에 접근할 수 있다. 

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

파이썬에서 배열 선언하는 방법

arr = [0, 0, 0]
arr = [0] * 3

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

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

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

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

파이썬에서는 배열을 지원하는 문법은 따로 없고, 대신 리스트라는 문법을 지원한다. 

(사실 엄밀히 말하자면 배열과 리스트는 다른 개념임)

파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현됐다. 

파이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용하면서 배열의 크기는 가변적으로 사용할 수 있다. 

배열과 차원

배열은 2차원, 3차원, ..., 다차원 배열 까지 사용할 수 있다. 

그러나 컴퓨터의 메모리 구조는 1차원이다. 

이는 2차원, 3차원, ..., 다차원 배열도 실제로는 1차원 공간에 저장된다는 뜻이다. 

배열은 몇 차원이든 상관없이 메모리에는 연속적으로 할당된다. 

1차원 배열

배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연속적으로 할당된다. 

2차원 배열

2차원 배열은 1차원 배열을 확장한 것이다. 

2차원 배열 활용 예시 

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

# arr[2][3]에 저장된 값 출력
print(arr[2][3]) # 12

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

리스트 컴프리헨션을 통한 2차원 배열 활용 예시 

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

arr = [[1, 2, 3], [4, 5, 6]]

위의 배열에서  첫번째 행과 두번째 행의 메모리 주소는 연속된다. (1행의 인덱스 2 다음 바로 2행의 인덱스0의 주소가 이어진다. )

5-2. 배열의 효율성

배열 연산의 시간복잡도를 통해 배열의 효율성은 아래와 같다. 

배열 연산의 시간 복잡도

아까 배열은 인덱스를 통해 임의 접근 방법을 사용한다고 했다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

만약 배열에 데이터를 추가하거나 삭제해야 한다면? 추가후에 기존에 있던 것들을 처리할 필요가 있는지,  혹은 대상을 삭제하고 기존에 있는 것들을 처리할 필요가 있는지 확인이 필요하다. 

1. 맨 뒤에 삽입할 경우

• 임의 접근을 통해 맨뒷 자리를 찾을 수 있다. 
• 맨 뒤에 값을 추가한 후에 기존의 값들을 이동할 필요가 없다. 
• 즉, 시간 복잡도는 O(1)이다. 

2. 맨 앞에 삽입할 경우

• 임의 접근을 통해 맨 앞 자리를 찾을 수 있다. 
• 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 현재 갖고 있는 데이터의 개수가 N개라면,  O(N))
• 즉, 시간 복잡도는 O(N)이다. 

3. 중간에 삽입할 경우

• 임의 접근을 통해 중간에 삽입할 자리를 찾을 수 있다. 
• 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 뒤로 밀어야 야 하는 데이터의 개수가 N개라면,  O(N))
• 즉, 시간 복잡도는 O(N)이다. 

위의 경우 들을 봤을때, 배열로 데이터를 저장하기 전에는 항상 이런 비용을 생각하는 것이 바람직하다. 

이렇듯 배열을 선택할 때 고려할 점은 다음과 같다. 

배열을 선택할 때 고려할 점

1. 할당할 수 있는 메모리 크기를 확인해야 한다. (파이썬에서는 리스트를 사용하므로, 배열 크기에 대한 고민은 할 필요가 없다. 공부를 위해 읽어두기)

• 운영체제마다 배열을 할당할 수 있는 메모리의 값은 다르지만, 보통 정수형 1차원 배열은 1천 만개, 2차원 배열은 3천*3천 크기를 최대로 생각한다. 따라서 이 이상의 값의 데이터를 관리하고자 하면 런타임에서 배열 할당에 실패할 수 있다. 

2. 중간에 데이터 삽입이 많은지 확인해야 한다. 

• 배열은 선형 자료구조이기 때문에, 중간이나 맨 처음의 위치에 데이터를 자주 삽입하면 시간복잡도가 높아져, 시간초과가 발생할 수 있다. 

5-3. 코딩테스트에서 자주 활용하는 리스트 기법

리스트에 데이터를 추가하는방법 

1. append()

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

2. + 연산자

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

3. insert()

# 특정 위치에 데이터를 삽입할 수 있다. 
tmp_list = [1, 2, 3]
tmp_list.insert(2, 9) #[1, 2, 9, 3]

리스트에서 데이터를 삭제하는 방법

1. pop() 

# 특정 위치에 데이터를 삭제할 수 있다. 
# 삭제한 데이터의 값을 반환한다. 
tmp_list = [1, 2, 3]
pop = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2]

2. remove()

# 특정 데이터를 찾아 삭제할 수 있다. 
# 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제한다. 
tmp_list = [1, 2, 3]
tmp_list.remove(2) # [1, 3]

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

리스트 컴프리헨션은 기존 리스트를 기반으로 새 리스트를 만들거나, 반복문이나 조건문을 통해 복잡한 리스트를 생성하는 등 다양한 상황에서 사용할 수 있는 문법이다. 

리스트에 제곱 연산 적용 예시 

tmp_list = [1, 2, 3]
squares = [num**2 for num in tmp_list] #[1, 4, 9]
# tmp_list의 값은 여전히 [1, 2, 3] 이다.

리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐, 연산 대상 리스트를 바꾸지 않는다. 

유용하게 쓰이는 리스트 연관 메서드 

alphabet = ["a", "b", "c", "a"]

# 리스트의 전체 데이터 개수 반환 함수 len()
len(alphabet) # 4

# 특정 데이터가 처음 등장할 적의 인덱스를 반환하는 index()메서드, 만약 값이 없는경우 -1 반환
alphabet.index("a") # 0

# 사용자가 정한 기준에 따라 데이터를 정렬하는 sort()메서드
# 함수안에 인수가 없을 경우, 오름차순으로 데이터 정렬
alphabet.sort() # ["a", "a", "b", "c"]
# 역순 
alphabet.sort(reverse=True) # ["c", "b", "a", "a"]

# 특정 데이터 개수를 반환하는 count() 메서드
alphabet.count("a") # 2

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

파이썬에서는 기본적으로 제공하는 데이터 타입들이 있다.

집을 사면 딸려오는 가구(사실 그 딸려오는 가구 값도 포함되는건 맞지만)처럼 파이썬에서는 기본 데이터 타입과,

컬렉션 데이터 타입을 제공한다. 

04-1 빌트인 데이터 타입

기본 데이터 타입

기본 데이터 타입에는 정수형, 부동소수형, 문자열 타입이 있다.

정수형

: 양, 음의 정수와 0을 포함한다.

사칙연산 뿐만 아니라 그 외의 연산도 가능하다. 

예를들어, **을 통한 지수 연산, //을 통한 나눗셈에서 몫만 반환하는 연산 등

아래는 정수형 데이터 정의 및 활용 방법이다. 

# 정수형 변수 선언

a = 4
b = 3

# 정수형 산술 연산

print(a + b) # 더하기 1
print(a - b) # 빼기 12
print(a * b) # 곱하기 45
print(a / b) # 나누기(소수점 포함) 1.3...
print(a // b) # 나누기(소수점 제외) 1
print(a % b) # 모듈러 연산(나머지 값 출력) 1
print(-a) # 부호 바꿈 -4
print(abs(-a)) # 절대값 4
print(a**b) # a의 b승 64

# 정수형 비교 연산

print(a == b) # 같은 값인지 비교 False
print(a != b) # 같은 값이 아닌지 비교 True
print(a > b)  # 왼쪽값이 더 큰지 비교 True
print(a < b)  # 오른쪽 값이 더 큰지 비교 False
print(a >= b) # 왼쪽값이 더 크거나 같은지 비교 True
print(a <= b) # 오른쪽값이 더 크거나 같은지 비교 False

# 정수형 비트 연산

a = 13
b = 4

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

*~a가 14인 이유

a는 2진수로 표현하면 0000 1101 이다. ~(not)을 하면 0000 1101이 반전돼서 1111 0010이 된다. 

맨 왼쪽의 값이 0이면 양수, 1이면 음수를 나타내는 것이다. 

1111 0010은 음수의 값이고, 컴퓨터에서 음수는 2의 보수로 표현된다. 

2의 보수를 읽기 위해서는 값을 한번 반전해주고 => 0000 1101 

그대로 1을 더해준다. => 0000 1110 이는 10진수로 14이다.

하지만 이 값은 음수이므로 -14로 표현할 수 있는 것이다. 

*논리 연산 AND 연산자

파이썬에서 논리 연산 AND는 두 피연산자가 모두 참이면 마지막 값을 반환한다. 

만약 첫 번째 피연산자가 거짓이거나 NULL이면, 첫 번째 피연산자를 반환한다. 

부동소수형

부동소수형에서는 사칙 연산, 정수형 나누기, 모듈러, 제곱 연산, 논리 연산을 할 수 있다. 

부동소수형에서 눈여겨 봐야할 곳은 10 % 3.2의 값이 0.4가 나와야 하지만 파이썬에서는 

0.39999999999999947이 나온다. 

그 이유는 파이썬에서는 부동소수형 데이터를 이진법으로 표현하기 때문에 발생하는 거고, 표현 과정에서 오차가 발생한다.

이를 엡실론이라고 한다. 

따라서 부동소수형 데이터를 활용한 문제에서는 오차 허용 범위의 언급을 확인하고, 주의 해야한다. 

04-2 컬렉션 데이터 타입

컬렉션 데이터 타입은 여러 값을 담는 데이터 타입을 말한다. 그 유형으로 리스트, 튜플, 딕셔너리, 셋, 문자열 등이 있다.

또한 컬렉션 데이터 타입은 두가지로 나눌 수 있는데, 이는 데이터의 수정 가능 여부에 따라 변경할 수 있는 객체(mutable object)와 변경할 수 없는 객체(immutable object)로 나눌 수 있다. 

변경할 수 있는 객체(mutable object)

: 객체 생성 후 객체를 수정할 수 있다. 리스트, 딕셔너리, 셋이 이 유형에 해당한다. 

변경할 수 없는 객체(immutable object)

: 객체 생성 후 객체를 수정할 수 없다. 문자열, 튜플이 이 유형에 해당한다. 

(정수나 부동소수점은 컬렉션 데이터 타입은 아니지만 이뮤터블 객체에 속한다)

<리스트>

: 리스트는 뮤터블 객체이고, 순서가 있는 자료형이다. 리스트는 인덱스를 활용해 특정 위치의 원소에 접근할 수 있다. 

기본적인 리스트 사용법은 다음과 같다. 

# 리스트 선언
tmp_list = [1, 2, 3, 4]
tmp_list2 = [5, 6] + [7, 8, 9]
tmp_list3 = list(tmp_list)
print(tmp_list) # [1, 2, 3, 4]
print(tmp_list2) # [5, 6, 7, 8, 9]
print(tmp_list3) # [1, 2, 3, 4]

# 리스트 인덱싱
tmp_list.append(5)
print(tmp_list) # [1, 2, 3, 4, 5]

# 인덱싱으로 값 삭제
del tmp_list[0]
print(tmp_list) # [2, 3, 4, 5]

리스트의 활용방법 중에 리스트 슬라이싱이라고 있다. 

슬라이싱은 시퀀스 자료형의 범위를 지정해 값을 복사하여 가져오는 방식을 말한다. 

리스트 슬라이싱 활용법은 다음과 같다. 

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

<딕셔너리>

: 딕셔너리는 뮤터블 객체이고, 키와 값 쌍을 저장하는 해시테이블로 구현돼 있다. 

키를 사용하여 값을 검색하는 자료형이다. 

기본적인 딕셔너리 사용법은 다음과 같다. 

# 딕셔너리 초기화 
dic = { }

# 딕셔너리 삽입과 출력
dic["yellow"] = 1
dic["green"] = 3
dic["blue"] = 5

print(dic) #{'yellow': 1, 'green': 3, 'blue': 5}

딕셔너리 검색 활용법은 다음과 같다.

키에 해당하는 문자열인지 확인하고, 키의 값이 딕셔너리에 존재하면 키-값을 출력한다. 

key = "yellow"
if key in dic:
    value = dic[key]
    print(f"{key}: {value}")
else:
    print(f"{key}는 딕셔너리에 존재하지 않습니다. ")

딕셔너리 수정 방법은 다음과 같다. 

dic["green"] = 5
print(dic) #{'yellow': 1, 'green': 5, 'blue': 5}

딕셔너리 삭제 방법은 다음과 같다.

del dic["green"]
print(dic) #{'yellow': 1, 'blue': 5}

<튜플>

: 튜플은 이뮤터블 객체이다. 한 번 생성하면 삽입하거나 삭제할 수 없다. 

기본적인 튜플 사용법은 다음과 같다. 

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

튜플은 인덱싱과 슬라이싱을 활용할 수 있고, 리스트와 활용법이 같다.

<문자열>

: 문자열은 문자의 집합 형태이며, 이뮤터블 객체이다. 

기본적인 문자열 사용법은 다음과 같다.

# 문자열 초기화 

string = "Hi" # 큰 따옴표 사용
string2 = 'Hello'# 작은 따옴표 사용

# 문자열 추가, 삭제 
string3 = "A-"
string3 += "yo" # 이때, string3은 기존의 문자열의 메모리 주소와의 연결은 끊고, 문자열을 새로 만들고 해당 문자열이 담길 메모리 주소를 새로 할당한다. 
print(string3) # "A-yo"

# 문자열 수정 
string4 = "Ha"
string4 = string4.replace("a", "o")
print(string4) # "Ho"

04-3 함수

파이썬에서의 함수 사용법은 다음과 같다.

def add(num1, num2):
    result = num1 + num2
    return result 

# 함수 호출

ret = add(5, 10)
print(ret)

함수를 더 간단하게 사용하기 위한 방법으로 파이썬에서는 람다식을 사용할 수 있다. 

또한 람다식은 익명 함수를 만드는데 사용한다. 

익명 함수는 이름 없는 함수이고, 코드에서 일시적으로 실행할 목적으로 사용하거나, 다른 함수의 인수로 사용할 수 있다. 

람다식의 사용법은 다음과 같다. 

# 람다식 정의

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

# 람다식 사용 유형 1

add = lambda x, y: x + y
print(add(5, 4)) # 9

# 람다식 사용 유형 2

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

04-4 코딩 테스트 코드 구현 노하우

1. 조기 반환

: 코드 실행 과정이 끝나기 전에 반환하는 기법

2. 보호 구문

: 본격적인 로직 진행 전 예외 처리 코드를 추가하는 기법 

3. 합성 함수

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

보통 합성 함수로 람다식을 활용한다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

코딩테스트 준비를 하기 위해서 연습 문제를 풀때, 제한 시간을 한번쯤 볼 수 있었을 것이다. 

여기서 말하는 제한 시간은 알고리즘이 실행되고 종료될 때 걸리는 시간의 제한 시간을 말하는 것이다. 

컴퓨터에서 1초당 처리되는 연산 횟수가 대략적으로 정해져있다.

(코딩테스트를 치는 환경(연습으로 문제푸는 환경도 마찬가지)에는 모든 컴퓨터의 성능이 동일하다고 가정한다. )

(1초당 1억개의 연산 가능)

그런데 문제에 대해 알고리즘을 어떻게 짜냐에 따라서 1초당 처리되는 연산 횟수가 줄어들 수도 있고 유지될 수도 있다. 

더 많아질 수는 없다. (컴퓨터가 자가 발전하지 않는 이상(?))

코드를 작성하고 나서 이 알고리즘이 어떻게 짜여졌냐? 어떻게 짜여졌길래 1초당 처리되는 연산 횟수가 이런가?

작성한 알고리즘이 1초당 처리되는 연산 횟수가 이정도면 대략 이정도의 복잡도를 가진 알고리즘일 것이다. 

(단, 입력 크기를 N으로 일반화 해야함. 왜냐하면 입력 크기가 1인 경우 알고리즘을 작성해야 하는 경우로 예를 들자면, 입력크기가 1일때만  연산 횟수가 1인 성능을 가지는 것이기 때문 == 해당 상황에 한정된것, 입력 크기가 다른 값으로 바뀔경우 연산 횟수 성능도 바뀔 것)

이런 맥락에서의 복잡도를 가지고,

==> 우리는 이것을 알고리즘의 시간복잡도라고 하기로 했다. 

입력 크기에 따른 연산 횟수 추이를 활용해 시간 복잡도를 표현하는 방법을 점근적 표기법이라 한다. 

[시간 복잡도(time complexity)]

: 알고리즘의 성능을 나타내는 지표. 입력 크기(알고리즘이 처리해야 할 데이터의 양)에 대한 연산 횟수의 상한을 의미한다. 

시간 복잡도는 낮으면 낮을 수록 좋다. 

시간 복잡도는 최선, 보통, 최악의 경우로 나눌 수 있지만, 코딩테스트에서는 작성한 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 계산해야한다. 왜냐하면, 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하기 때문이다. 

* 빅오 표기법

: 빅오 표기법은 최악의 경우일 때의 시간 복잡도를 표현하는 방법이다. 

빅오 표기법은 특정 알고리즘의 연산 횟수가 f(x)일 때, 함수의 최고차항만을 남기고 남은 자수를 지워 O(최고차항)와 같이 표현하면 된다. 

* 빅오 표기법을 쉽게 쓸 때 최고차항만 남기고 차수를 지우는 이유

: 시간복잡도 식에서 최고차항 이외의 값들을 2차원 그래프에서 표현해보면 최고차항 이외의 값들은 무시할 수 있을 정도로 작으므로 무시한다. 

컴퓨터는 1초에 최대 1억번 연산할 수 있다. 

코딩 테스트의 문제는 출제자의 의도대로 로직을 구현했을 경우 대부분 코드를 정답처리 할 수 있게끔 채점시간을 정한다. 

이때, 언어별로 다른 성능의 차이는 고려하지 않는다. 

[시간 복잡도 계산해보기]

: 과정

1. 문제 정의

2. 연산 횟수 측정

3. 시간 복잡도 분석

* 고려할 점

출력 자체도 연산이다. 

비교도 연산이다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

LCS란?

:"가장 긴 공통 부분 수열"이다. 알고리즘 LCS에서는 가장 긴 공통 부분 문자열이다. 두 개의 문자열이 있을 때, 그 문자열에서 순서를 유지하면서 공통으로 나타나는 글자들을 이어서 만들 수 있는 가장 긴 문자열을 찾는 것을 의미한다.

*부분 문자열이란?

:부분 문자열에는 연속된 부분 문자열인 Substring과 연속되지 않은 부분 문자열인 Subsequence라는 개념이 있다. 

Subsequence라는 개념을 예시를 들어 설명하자면, "ABCDEF"와 "AEBDF"라는 두 문자열이 있다면, 이 두 문자열에서 공통으로 나타나며 글자들이 두 문자열에서 같은 순서로 나타나는 문자열 중 가장 긴 부분 수열은  "ABDF"이다. 

예시

* 위 배열 활용법 *

조회하는 문자열이 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야한다. 

조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값을 교체한다. 

맨 첫번째 행의 모든 열을 0으로 하고 다음 모든 행의 첫번째 열에 0은 왜 넣는걸까?

=> 조회하는 문자열이 같을때, 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야하는데, 

앞에 0을 넣지 않으면 첫번째 문자열의 맨첫번째 값과 두번째 문자열의 맨 첫번째 값에 어떤 값을 넣어줘야 할지 모르기 때문이다. 

왜 바로 앞의값(왼쪽)의 값에서 +1을 하지 않을까? 

=> 바로 앞의값에서 +1을 하면 lcs의 값에 +1을 하는 꼴이 된다.

(하지만 두번째 단어의 조회할 자리는 여전히 같은 자리임=> 두번째 단어의 조회할 자리를 +1 하면 할수록 lcs의 값이 중복으로 +1되는 꼴)

왜 조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값으로 교체할까? 

왜 하필 현재 자리에서 왼쪽, 위의 값을 비교할까? 

 => 현재 자리의 왼쪽은 현재 자리의(같은행, 다른열==현재열-1) lcs값은 고려하지 않고 이전 문자까지의 lcs값만을 가지고 있는 것이고,

현재 자리의 위쪽은 현재 자리의 lcs값을 고려하지만, 새로 조회하는 문자와의 비교는 하지 않은 값이다. (다른행==현재행-1, 같은열)

왼쪽, 위의 값은 각각 자신이 할 수 있는 최적의 lcs를 구한 상태이다.

따라서 둘 중에 큰 값을 골라 현재의 자리의 값을 교체해줌으로써 최적의 값을 유지할 수 있게된다. 

[이분탐색(이진탐색)의 정의]

: 오름차순으로 정렬된 리스트에서 찾고자 하는 값의 위치를 찾는 알고리즘

[이분탐색의 특징]

: 모든 값을 순회하는 일반탐색 보다 빠른 속도.

시간복잡도: O(logN)

[이분 탐색 진행 과정]

오름차순으로 정렬된 배열에서 특정 데이터를 탐색하는 상황

1. 오름차순으로 정렬된 배열에서 맨처음 값의 인덱스를 low라고 하고, 맨 뒤의 인덱스의 값을 high의 변수에 저장함. 

2.  배열의 중앙값을 선택: 중앙값은 mid가 된다. 

3. 중앙값과 특정 데이터의 값을 비교한다. 

만약, 중앙값보다 특정 데이터가 클 경우, 중앙값 오른쪽의 요소들을 선택하여 탐색한다. = 탐색을 대상 배열의 맨 처음 인덱스의 값(low)가 중앙값+1의 값을 가진다. 

(반대의 경우는 high가 중앙값-1의 값을 가짐)

4. 선택된 우측 요소의 중앙값을 선택한다. (mid갱신)

5. 중앙값과 특정 데이터를 비교한다.

만약, 특정 데이터가 중앙값 보다 클 경우,중앙값 오른쪽의 요소들을 선택하여 탐색한다. = 탐색을 대상 배열의 맨 처음 인덱스의 값(low)가 중앙값+1의 값을 가진다.

(반대의 경우는 high가 중앙값-1의 값을 가짐)

6. 남은 배열(2개)중에 좌측 요소를 선택하여 특정 데이터를 비교한다. 

만약 두 값이 같으면 탐색 종료 

[구현]

• 반복문
• 재귀

1. 탐색 대상값이 속한 자료를 오름차순으로 정렬한다. 

2. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. 

3. 중간값(mid)이 찾고자 하는 값(target)과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid값이 같을 때까지 아래 조건에 따라 2번 3번을 반복한다. 

1. 찾고자 하는 값(target)이 중간값(mid)보다 작으면 end값을 mid-1의 값으로 바꾼다. 
2. 찾고자 하는 값(target)이 중간값(mid)보다 크면 high값을 mid+1의 값으로 바꾼다.

그래프를 구현하기 위해 필요한 요소

• 노드
• 간선(노드간 연결 유무)
• 가중치(노드간 간선에 대한 가중치)
• 방향(노드간 연결 됐을때 방향이 있는 경우)

그래프 구현 방법

• 인접 행렬
  • 가중치가 있는 경우, 가중치에 대해 초기화 할때는 inf(무한대의 값) 혹은 -1로 초기화 

보통 인접 행렬로 구현많이 함.

깊이 우선 탐색

시작 노드부터 탐색을 시작해, 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문함

최대 깊이 노드까지 방문한 다음, 이전에 방문한 노드로 거슬러 올라가면서 해당 노드와 연결된 노드 중 방문하지 않은 노드로 

다시 최대 깊이 까지 차례대로 방문합니다. 

절차

1. 스택이 비었는지 확인한다. 스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했음을 의미한다. 따라서 스택이 비었으면 탐색을 종료한다. 
2. 스택에서 노드를 팝한다. 팝한 원소는 최근에 스택에 푸시한 노드다. 
3. 팝한 노드의 방문 여부를 확인한다. 아직 방문하지 않았으면, 노드를 방문 처리한다. 
4. 방문한 노드와 인접한 모든 노드를 확인한다. 그리고 그 중에서 아직 방문하지 않은 노드를 스택에 푸시한다. 스택은 FILO 구조이므로, 방문 순서를 오름차순으로 고려한다면 역순으로 노드를 푸시해야한다. 

너비 우선 탐색 

시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. 

여기서 말하는 거리는 시작 노드와 목표 노드까지의 차수이다. 

컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억번임을 기억하기

(백준한정-파이썬) 추가시간 없음 이라는 말이란?

=> 파이썬은 기존대로 1초에 2천만번 연산 가능함
(원래는 이런말 없으면 원만하게 정답 처리를 해주기 위해서 1초에 1억번까지 연상 가능하도록 해줌. )