알고리즘 문제풀이를 이어가다가 DFS (깊이우선탐색) 주제를 공부하게 되었다.

예제로 나온 문제에서 이항계수 개념을 활용해야 하는 문제가 나왔는데, 졸업한지 오래되어 개념을 까먹었다..

다시 개념을 익힐 겸! 기록으로 남겨본다.

1. 이항계수

이항계수?
이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수

이항계수의 표현식은 nCk 로 표현된다.

nCk = n! / (k!(n-k)!)

아래는 n이 5이고 k가 3일때 5C3을 구하는 과정을 트리형태로 그려보았다.

이항계수 계산법인 팩토리얼로 계산했을때 답이 10 이 나오는데 직접 flow를 그려가보니 정말 10개의 가짓수가 나왔다.

2. 이항계수 계산하기

2-1) DFS (깊이우선탐색) - 재귀함수 활용하기

재귀함수를 활용해 중복을 허용하지 않는 n개 중 k 개를 구하는 방법은 아래와 같다.

# L = level
# s = start point
def DFS(L, s):
    global cnt
    if L == m:
        for row in res:
            print(row, end=" ")
        print()
    else:
        for i in range(s, n+1):
            res[L] = i
            DFS(L+1, i+1)


if __name__ == "__main__":
    n,m = map(int, input().split())
    res = [0]*m
    DFS(0, 1)
-------------------------------------------------
1 2 
1 3 
2 3

여기서 중복을 허용하지 않기 위해 DFS 함수 내의 s값은 1직전 s값보다 1만큼씩 증가하여 다음 level로 넘어가게 한다.
중복을 허용한 가짓수를 확인하려면 아래와 같이 코드를 수정하면 된다.

# L = level
# s = start point
def DFS(L, s):
    global cnt
    if L == m:
        for row in res:
            print(row, end=" ")
        print()
    else:
        for i in range(1, n+1):  # s부터 시작하는것 대신 항상 1부터 시작하도록 변경
            res[L] = i
            DFS(L+1, i+1)


if __name__ == "__main__":
    n,m = map(int, input().split())
    res = [0]*m
    DFS(0, 1)
-------------------------------------------------
1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3

2-2) python 라이브러리 itertools 활용하기

python nCk 계산에 활용할수 있는 라이브러리가 있다. (아주.. 굿...) 바로 itertools 이다.

재귀함수를 통해 문제를 풀면서 이해가 되지 않아 머리를 쥐어뜯어가면서.. 노트에 받아적으면서 겨우 이해가 됐을 때 이 라이브러리를 알고 신세계를 맛봤다

그러나 일부 코테에서는 해당 내장함수 사용을 금지하는 경우도 있으니 반드시 재귀함수 방식으로의 풀이도 익혀두어야 한다.

지난 년도 삼성 코테에서 itertools 라이브러리 사용을 막았다는....

또한 "특정 조건" 을 충족해야하는 조합을 구할땐 이런 함수 사용이 어려울 수 있으므로 주의!!

a) itertools 의 permutations

중복을 허용하는 리스트 n 중에서 k개를 선별하는 가짓수 반환

n = [1, 2, 3]
k = 3
for tmp in it.permutations(n, k):
    print(tmp)
-------------------------------------------------
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

b) itertools 의 combinations

중복을 허용하지 않는 n개 중 k개를 선별하는 가짓수 반환

n = [1, 2, 3]
k = 3
for tmp in it.combinations(n, k):
    print(tmp)
-------------------------------------------------
(1, 2)
(1, 3)
(2, 3)

이어서..!!! 어흐 어려워

이전의 후위표기식 문제를 해결하는데에는 스택 (Stack) 자료구조가 활용되었다.
이번에는 또다른 자료구조인 큐 (Queue) 에 대해 이해해 보고자한다.

1. 큐 (Queue)

큐 (Queue)
후입선출 (LIFO) 이었던 Stack 과 달리 큐는 선입선출을 기본으로 하는 자료구조형이다.
First In First Out으로 먼저 담긴 값이 먼저 반환되는것을 의미한다.

예시로는 티켓부스에서 티켓을 구매하기 위해 줄선 모습을 상상하면된다. 먼저 줄 선 사람이 먼저 티켓을 구매하는 것이 선입선출의 예 이다.
업무로 연관을 지어보면, 본인이 일하는 회사의 프로그램 구조에서는 이 "큐" 를 적극 활용하고 있다.
"유저의 여러 액션을 하나의 메세지로 만들어 이를 하나의 SQS에 전송하고 하고 FIFO 방식으로 전달된 메세지들을 SQS에서 처리하여 각 기능을 담당하는 프로젝트를 호출" 하게 된다.

만약 이런 구조에서 Stack방식을 활용했다면 가장 먼저 요청들어온 유저 액션이 가장 나중에 처리되었을 것이다.

이처럼 먼저들어온것을 먼저 처리해 주는 방식이 FIFO 방식의 큐 자료구조이다.

2. 큐 (Queue) 와 데크 (Deque)

앞서 말했듯 큐 는 FIFO 방식이다. 이때 "입"과 "출"의 방향은 단방향이다. 양쪽에서 데이터를 넣고, 양쪽에서 빼는 구조는 아닌 것이다.
이와 달리 python에 존재하는 내장함수 deque는 FIFO 방식의 큐를 기반으로 한 양방향 큐 자료구조이다.

양방향 출입을 허용하는 데크 (Deque) 는 때론 스택, 때론 큐 를 대체할수 있으며 list 구조에서 데이터 삽입, 반출하는 때 보다 단축된 시간복잡도를 갖는다고 한다. (이 부분은 시간복잡도에 대해 더 이해해야 할듯)

3. python의 데크 (Deque) 사용법

데크는 단방향인 큐와 달리 양방향 이라고 했다. 따라서 좌, 우 모두 값 추가가 가능하며 좌, 우 모두 값 삭제도 가능하다.
queue 자료구조에서 값의 입, 출은 append와 pop 으로 수행한다.
deque 에서는 이를 양방향으로 진행하기 위해 appendleft 와 popleft 를 지원한다.

시간복잡도 | deque함수 | 설명
O(1)    | deque.append(x) : x를 데크의 오른쪽 끝에 삽입 : [0,0,0] -> [0,0,0,x]

O(1)    | deque.appendleft(x) : x를 데크의 왼쪽 끝에 삽입 : [0,0,0] -> [x,0,0,0]

O(1)    | deque.pop() : 데크의 오른쪽 끝 값 삭제 : [y,0,0,x] -> [y,0,0]

O(1)    | deque.popleft() : 데크의 왼쪽 끝 값 삭제 : [y,0,0,x] -> [0,0,x]

O(k)    | deque.extend(array) : 배열 array를 순환하면서 데크의 오른쪽에 추가 : [0,1,2].extend([a,b,c]) -> [0,1,2,a,b,c]

O(k)    | deque.extendleft(array) : 배열 array를 순환하면서 데크의 왼쪽에 추가 : [0,1,2].extendleft([a,b,c]) -> [c,b,a,0,1,2]

O(N)    | deque.reverse() : 데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환 : [1,2,3,4] -> [4,3,2,1]

O(N)    | deque.remove(x) : x를 데크에서 찾아 삭제. 이때 값 x 가 없으면 ValueError가 발생한다.

O(K)    | deque.rotate(num) : 데크를 num만큼 회전한다 (양수면 오른쪽, 음수는 왼쪽으로) : 이때 동작은 pop 된 값을 append 하는것과 일치하다.

deque의 append, appendleft, pop, popleft 등을 활용하여 주어진 리스트에서 주어진 우선순위에 따라 특정 값이 몇번째로 처리되는지에 대한 문제를 해결할 수 있다.

중위표기식, 후위표기식은 전공강의를 들으면서 개념을 알고 있었는데 이걸 막상 문제로 풀려고 하니 정확한 프로세스를 표현하지 못했다.

자료구조 "스택" 을 활용하여 중위표기식을 후위표기식으로 표현하는 프로그램을 작성하면서 다시 학습하고자 한다.

1. 중위표기식 과 후위표기식 이란

중위표기식은 우리가 흔히 사용하는 표기 방식으로 연산자 가 피연산자 사이에 존재한다. 중간에 있어 "중위" 표기식!
후위표기식은 연산자 가 피연산자 의 뒤에 존재한다. 뒤 후 자로 "후위" 표기식!

1-1) 중위표기식 예시

3+5*2/(7-2)

가 있을때 연산자 우선순위를 고려하여 문제를 풀어나간다.

3+5*2/(7-2)
1) 3+5*2/5
2) 3+10/5
3) 3+2
4) 5

1-2) 후위표기식 예시

352*72-/+

후위표기식은 연산자가 피연산자의 뒤에 있으므로 연산자가 나오면 연산자 앞의 두개의 피연산자와 해당 연산자를 계산해 준다.

352*72-/+
1) 52* 계산 : 5*2 => 3(10)72-/+
2) 72- 계산 : 7-2 => 3(10)5/+
3) (10)5/ 계산 : 10/5 => 32+
4) 32+ 계산 : 3+2 => 5

계산 결과로 알수 있듯 각 예시로 들은 식은 동일한 수식이다.

2. 연산자 우선순위

a) 덧셈, 뺄셈

덧셈과 뺄셈은 연산자 우선순위에서 가장 하위에 위치한다.

b) 곱셈, 나눗셈

곱셈과 나눗셈은 연산자 우선순위에서 덧셈과 뺄셈보다 상위에 위치한다.

c) 괄호

괄호의 종류로는 소괄호, 중괄호, 대괄호가 있는데 일반적으로 괄호는 괄호로 둘러싸인 바깥의 연산자들 보다 상위의 우선순위를 가진다. 또한 괄호의 세 종류 내에서는 소괄호 > 중괄호 > 대괄호 순으로 상위의 우선순위를 가진다.

3. 중위표기식 -> 후위표기식 : 스택 구조 활용

중위표기식을 후위표기식으로 변환하라는 문제는 알고리즘 문제에서 쉽게 볼수 있다. 특히 자료구조 "스택" 을 활용한 문제에서.
자료구조 "스택"을 활용해 변환하는 과정을 말하기 전, 연산자 우선순위에 대한 정확한 이해가 필요하다.

스택?
Last In First Out 구조로 나중에 들어간 값이 가장 먼저 반환되는 구조이다. 파이썬에서는 list의 스택 자료 형태에서 내장함수로 append() 와 pop()이 활용된다.

먼저 위로 예시를 들었던 중위표기식 3+5*2/(7-2) 을 후위표기식으로 변환해보자.
스택구조를 활용해 후위표기식으로 변환할때 다음과 같은 규칙이 있다.

1. 피연산자가 나올 경우 후위표기식으로 바로 작성한다.
2. 연산자가 나올 경우 연산자 우선순위에 따라 stack에 쌓거나, 후위표기식으로 작성한다.

간단한 규칙이지만 다양하게 존재하는 연산자 우선순위에 따라 따져야할 조건들이 많다.

result = ""  # 변환 완료된 후위표기식
stack = [] # 스택 자료구조
target_list = "3+5*2/(7-2)"  # 후위로 변환하고자 하는 중위표기식

for target in target_list:  # 문자열을 for loop으로 실행 시 문자 한개씩 확인할 수 있다.
    if target.isdecimal():  # 파이썬 내장함수 isdecimal()로 해당 문자열이 숫자로 변환 가능한지 확인 할 수 있다. (boolean)
        result += target
    else:
        # 괄호가 나온 경우 최우선 순위로 stack 에 쌓기
        if row == "(":  
            stack.append(row)
        # 곱셈, 나눗셈이 나온경우 동일한 우선순위를 가진 연산자가 확인될때까지 stack에 쌓여있는 피연산자 꺼내기
        elif row in ["*", "/"]:  
            # 이때, stack에 더이상 연산자가 없는 경우 꺼내는걸 중단한다.
            while stack and (stack[-1] in ["*", "/"]):  
                # stack 에서 꺼낸 연산자는 후위표기식에 작성된다.
                res += stack.pop()  
            # 이후 확인 대상이었던 연산자는 stack에 쌓인다.
            stack.append(row)  
        # 덧셈,뺄셈은 최하위 우선순위이나 소괄호 내의 것은 소괄호 바깥의 연산자들보다 상위순위를 갖는다.
        elif row in ["+", "-"]:  
            # stack에 쌓인 연산자가 여는 소괄호가 아닌경우때 까지 연산자를 꺼낸다.
            while stack and stack[-1] != "(":  
                # stack 에서 꺼낸 연산자는 후위표기식에 작성된다.
                res += stack.pop()  
            # 이후 확인 대상이었던 연산자는 stack에 쌓인다.
            stack.append(row)  
        # 닫는 소괄호가 나온 경우 stack에는 여는 소괄호가 있을 것이다.
        elif row == ")":  
            # 여는 소괄호가 나올때까지 모든 연산자를 우선순위에 맞춰 후위표기식으로 작성한다.
            while stack and stack[-1] != "(":  
                res += stack.pop()
            # 괄호는 후위표기식에 작성되지 않으므로 소괄호는 없애준다.
            stack.pop() 
    while stack:
        res += stack.pop()

각 조건문에 대해 좀더 자세히 살펴보면 다음과 같다.

1. 괄호내의 것은 우선순위로 변환한다. 또한 후위표기식에서 괄호는 표현되지 않으므로 변환에 사용하지 않는다.
2. 덧셈, 뺄셈일 경우 해당 연산자보다 후순위의 연산자가 없으므로 stack에 쌓여있는 모든 연산자들을 처리해 주어야 한다.
   (본인과 동등한 우선순위의 연산자, 상위 순위 연산자 처리해야 하기 때문)
3. 위 2번과 동일한 맥락으로 곱셈, 나눗셈일 경우 본인과 동등한 우선순위 연산자까지는 모두 처리해 주어야 한다.
   • 이 규칙으로 인해 3+5_2 는 352_ 가 되고 +는 그대로 stack에 남아있게 되었다. (이후 처리됨)

스택구조 활용에 이렇게 알찬 예제는 없는듯 하다. 그래서 알고리즘 스택 문제 단골 손님인가 싶다.!

먼저 아스키코드란 1963년 미국 ANSI에서 표준화한 정보교환용 7비트 부호체계이다.

https://namu.wiki/w/%EC%95%84%EC%8A%A4%ED%82%A4%20%EC%BD%94%EB%93%9C

알고리즘을 풀다가 주어진 알파벳이 있을때 이를 아스키코드로 변환하는 문제가 나와 알아보게 되었다.

1. 아스키코드 -> 문자열

SQL이나 C, C++ 에서는 문자열을 뜻하는 값으로 char (character) 를 사용한다. python에서는 아스키코드를 문자열로 변환하는데 내장함수 chr() 을 사용한다.

asc_code = 65
answer = chr(asc_code)
print(answer)
print(type(answer))
------------------------------------
>>> 'A'
>>> <class 'str'>

chr()을 통해 변환된 아스키코드는 string type의 문자열로 반환된다.

1-1) 문자로 변환할 수 없는 아스키코드

변환하고자 하는 값이 아스키코드가 아닌경우, 이를 chr() 함수 사용시 에러가 발생한다.

asc_code = 134583495739845
answer = chr(asc_code)
--------------------------------------------
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: chr() arg not in range(256)

에러를 확인해 보면 chr() 내장함수 안의 값은 범위 0부터 256미만 까지만 입력이 가능하다고 한다.

b_code = 1.5
b = chr(b_code)
--------------------------------------------
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: integer argument expected, got float

또한 python의 내장함수 chr()에는 int 타입의 수만 들어가야 한다.

1-2) 문자로 변환 가능 최소값, 최대값

# 아스키코드 0의 문자열 변환
zero_code = 0
zero_answer = chr(zero_code)
print(zero_answer)
print("---" + zero_answer + "---")
print(type(zero_answer))
------------------------------------------
>>>
>>> ------
>>> <class 'str'>
# 아스키코드 255의 문자열 변환
max_code = 255
max_answer = chr(max_code)
print(max_answer)
print(type(max_answer))
>>> ÿ
>>> <class 'str'>

이때 0의 코드값은 없는값 (공백도 아님) 으로 변환되고, 255은 특수문자로 변환된다.

2. 문자 -> 아스키코드

문자열을 해당하는 아스키코드로 변환하는데에는 python의 내장함수 ord() 가 사용된다. ord는 ordinal position을 뜻하며, 문자의 순서 위치 값 을 의미한다.

a = "A"
a_code = ord(a)
print(a_code)
print(type(a_code))
------------------------------------------
>>> 65
>>> <class 'int'>

이때 변환된 아스키코드값은 'int' 형이다.

2-1) 아스키코드로 변환할 수 없는 문자 : 문자열

a = 'AAAAA'
a_code = ord(a)
------------------------------------------
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ord() expected a character, but string of length 5 found

에러를 확인해 보면 ord() 내장함수의 파라미터 값으로는 character 만 가능한데, 길이 5의 문자열이 사용되었다고 한다.
이를 통해 문자 와 문자열이 구분되야 하며, ord() 에는 문자열이 아닌 문자가 사용되어야 한다는걸 알 수 있다.

b = 'ㄱ'
b_code = ord(b)
------------------------------------------
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ord() expected a character, but string of length 3 found

한글은 보이는것과 달리 영어처럼 단일 문자 취급되지 않는다.

2-2) 아스키코드로 변환할 수 없는 문자 : 0

위의 1-2 에서 확인한 문자 변환 내장함수 chr()의 범위를 통해 아스키코드 0과 255로 변환해보자

min_str = ''
min_code = ord(min_str)
------------------------------------------
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ord() expected a character, but string of length 0 found

ㅜㅜ... 아스키코드 0을 문자로 변환했을때 없는값이 출력되어 똑같이 빈 string을 아스키코드로 변환하려 했더니 오류가 발생했다.
아스키코드 0은 없는값, 즉 Null 값을 반환하기 때문에 이를 구현할 수 없는 것이다.
혹시나 해서 None을 변환해 보려 했지만 실패!

min_str = None
min_code = ord(min_str)
------------------------------------------
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: ord() expected string of length 1, but NoneType found

last update : 2024.01.21

백준에서 알고리즘을 풀면서 입력받은 값을 사용하는 방식에 참 다양한 게 있다는걸 알게되었다.

다음은 알고리즘을 풀면서 알게된 python의 다양한 입력방식에 대한 것들이다.
이 외에도 알고리즘을 계속 풀면서 알게되는 방법들에 대한 내용을 추가할 계획이다!

1. input

# 입력받기
A = input()

# 입력받은 것에 type 명시하기
A_int = int(input()

# 띄어쓰기로 구분된 여러 값 입력받기
Mul_A = map(int, input().split())

# 줄바꿈으로 구분된 두가지 값 (두 줄 기준) 입력받기
first_line = input()
second_line = input()

가장먼저 알게된 것은 python의 input 이었다.

1-1) input의 입력 type

python의 내장함수 input은 입력받은 값을 string 타입으로 변환하여 입력받는다.
python에서는 모든 것을 객체 (object)로 입력받는데, input 함수로 입력받은 것은 string class 로써 받아들여진다.

def check():
    intInput = input("python 내장함수 input으로 입력받기! (숫자) : ")
    print(intInput)
    print(type(intInput))

    stringInput = input("python 내장함수 input으로 입력받기! (문자) : ")
    print(type(stringInput))
    print(stringInput)
------------------------------------------------------------------
python 내장함수 input으로 입력받기! (숫자) : 123
>>> 123
>>> <class 'str'>
python 내장함수 input으로 입력받기! (문자) : 123
>>> <class 'str'>
>>> 123

이때 input으로 입력받는 값은 "Enter" 가 입력되기 까지 입력 받는 숫자 전부이다.

1-2) input의 개행문자열

"Enter"로 입력받는 input은 마지막 Enter에 대한 개행문자열은 삭제처리 된다. 문자열의 개행문자 삭제 함수인 rstrip() 가 자동으로 적용된 것이다. 이는 두번째로 알게된 입력방식 sys 보다 시간효율이 떨어지는 방식임을 의미한다.

1-3) 입력 방식 커스텀

input 함수는 값을 입력받을때 별도로 prompt message를 설정할 수 있다. 1-1 에서 볼수 있듯 "python 내장함수 input으로 입력받기!" 를 input 함수에 함께 써 넣으면 파일이 실행 될 때 해당 문구가 함께 나타나며 값을 입력받게 된다. python으로 만드는 간단한 숫자야구게임과 같은 프로젝트에서 이를 많이 활용하는 모습이다.

1-4) 입력받은 값 변수에 저장하기

input을 통해 입력받은 값은 변수로 저장이 가능하다. 이때 입력받은 당시 사용된 prompt message는 변수로 저장에서 배제된다.

def check():
    student = input("안녕 학생들 : ")
    print("오늘 출석한 학생들 명단 :", student)
    print("출석 일등!", student.split(" ")[0])
---------------------------------------------------
안녕 학생들 : 바둑이 철수 영희
>>> 오늘 출석한 학생들 명단 : 바둑이 철수 영희
>>> 출석 일등! 바둑이

띄어쓰기로 구분된 여러값을 입력받은 input()저장 변수 student는 string 타입이므로 띄어쓰기를 기준으로 이를 list로 변환하기 위해 split 함수를 사용했다.
이중 첫번째 인자값을 사용하여 첫번째 출석 학생 이름을 출력하도록 했다.

1-5) 타입을 지정하여 입력받기

input을 통해 입력받는 값의 타입을 입력과 동시에 지정할 수 있다.

def check():
    origin_input = input()
    print(type(origin_input))
    int_change_input = int(input())
    print(type(int_change_input))
    no_int_change_input = int(input())
---------------------------------------------------
1004  # origin_input
>>> <class 'str'>
1004  # int_change_input
>>> <class 'int'>
천사  # no_int_change_input
Traceback (most recent call last):
  File "/Users/practice.py", line 32, in <module>
    check()
  File "/Users/practice.py", line 30, in check
    no_int_change_input = int(input())
                          ^^^^^^^^^^^^
ValueError: invalid literal for int() with base 10: '천사'

하지만 변환이 되지 않은 경우 바로 ValueError 가 발생하니 타입이 명확할 경우에만 사용하여야 한다.

1-6) 값 여러번 입력받기

한줄에 여러값을 입력받을 수 있고, 여러줄을 입력받을 수 있다.
먼저 한줄에 여러값을 입력받을때 해당 값을 각각 변수로 저장하기 위해서는 공통된 구분값이 필요하다. 그리고 공통 구분값을 split() 함수를 활용하여 저장하도록 한다.

def check():
    first_input, second_input = input().split(",")
    print(first_input)
    print(second_input)
--------------------------------------------------
apple,orange
>>> apple
>>> orange

위 예제에서 한줄에 구분값으로 여러값을 입력받으면서 동시에 타입을 지정하기 위해선 python의 map 함수를 활용한다.
python의 map 함수는 다수의 값을 동시에 타입변환할때 사용되는 내장함수이다.

def check():
    first_input, second_input = map(int, input().split(","))
    print(first_input)
    print(type(first_input))
    print(second_input)
    print(type(second_input))
--------------------------------------------------
123,456
>>> 123
>>> <class 'int'>
>>> 456
>>> <class 'int'>

이때에도 역시 입력받은 값이 타입변환이 불가능할 경우 ValueError가 발생한다

123,사과
Traceback (most recent call last):
  File "/Users/practice.py", line 31, in <module>
    check()
  File "/Users/practice.py", line 26, in check
    first_input, second_input = map(int, input().split(","))
    ^^^^^^^^^^^^^^^^^^^^^^^^^
ValueError: invalid literal for int() with base 10: '사과'