처음에 해메었던 부분들이 있었다.

이유는 구간의 총 합이 100m 로 고정되어있다는 걸 간과한채 미지의 수가 들어오면.. 하면서 복잡하게 생각하느라 로직이 꼬였던듯 하다.

일반 tc는 통과했지만 히든tc에서 오답처리되어 0점...!!

다시 문제를 확인했고 접근방식을 변경했다.

[1] 내 풀이 : 모든 구간의 속도 차이 비교 (단, 과속일때만 기록)

비교해야 할 구간이 100m 까지이고, 단위가 1m 이므로 모든 구간을 비교해도 괜찮겠다 싶었다.

- step1

이것이 가능한 이유는 구간이 100m 로 비교적 짧게 고정되어있기 때문이다. 이 방식은 구간이 미지수에 매우 범위가 크다면 시간제한이슈로 사용하지 못할 듯 하다.

- step2

0부터 100까지 index 를 사용해 stand_all 과 test_all 의 각 값을 비교한다. 이때 test_all-stand_all 값이 0보다 커야 테스트 중에 과속했다는 것을 의미하므로 그 값만 diff_list 에 담아준다.

- step3

만약 diff_list 에 아무갑솓 안담겨있다면 이는 저속 주행 혹은 정속 주행만 했음 을 의미한다. 따라서 조건에 맞게 0 을 반환한다.
이와 달리 diff_list에 유효한 값이 있다면 이중 가장 큰 값을 출력한다. 이것이 가장 큰 차이가 나는 과속 범위를 뜻한다.

내 풀이가 사용 가능했던 이유는 앞서 말했든 비교범위가 작게, 고정되어있기 때문이다. 실제로 이 방식으로 문제를 풀었을때 평균 0.1 초의 풀이시간이 나온걸 확인할 수 있었다.

만약 범위가 아주아주 크다면 모든 구간을 비교하는것은 사용하지 못할 듯 싶다. 최대한 비교횟수를 줄이기 위해 속도 차이가 나는 구간 마다의 기록 방식을 생각했지만 구현이 잘 안되어 다른 사람들의 풀이를 참고하였다.

[2] 추가 풀이 : 속도가 변하는 구간 값만 확인하기 (deque 활용 가능)

- step 1

구간별 속도를 기록한다. 이중배열속 0번 index는 구간을, 1번 index는 해당 구간의 속도를 뜻한다. 모든 0번 index값을 더하면 주어진 구간인 100이 나온다.

- step 2

약간 queue같은.. 모양인데 정말로 Python의 deque 를 사용해도 될것 같다. 배열보다 pop 하는 효율이 더 좋다고 하니...

기준 과 테스트 의 가장 첫 구간을 비교하여 구간길이의 차는 항상 테스트구간을 기준 으로 한다.

두 구간의 속도 차를 비교하여 해당 값이 0 보다 크다면 모든 속도차이를 비교한 배열에 append 한다. 0이면 정속 주행이고, 음수값이면 저속 주행이므로 배열에 담을 필요가 없다.

• 2-1 : 구간 차 가 양수" 라면 테스트 구간이 더 길다는 뜻이다. 때문에 남은 구간을 "테스트 list"의 0번째 인덱스에 다시 넣어준다. 속도비교도 하므로 속도값은 검사한 테스트 구간 값 그대로 넣어준다.
• 2-2 : 구간 차 가 "음수"라면 기준 구간이 더 길다는 뜻이다. 때문에 남은 구간을 "기준 list"의 0번째 인덱스에 다시 넣어주어야 하는데 이때 값 diff_len 은 음수이므로 절대값 처리 하여 넣어준다. 속도비교도 하므로 속도값은 검사한 기준 구간 값 그대로 넣어준다.

- step 3

모든 과속 데이터가 담긴 배열을 확인하여 조건에 맞게 답을 출력한다. 데이터가 없다면 0을, 데이터가 있다면 그중 가장 많이 과속한 max값을 출력한다.

1. 자료형 초기 선언 두가지 방식 : 괄호 사용 or 내장 함수 사용

python 언어로 작업을 하면서 변수를 자료형의 초기상태로 선언할때 dictionary 는 중괄호 {} , list 는 대괗로 [] 로 표현했었다. 어느순간 작업하면서 얇은 괄호가 눈에 잘 띄지 않는 듯 하여 내장함수를 사용한 적도 있었다.
또한 python에서는 함수의 리턴 type을 명시할때도

def some_function() -> dict:
    ...

이런식으로 자료형의 "이름" 을 직접 명시하다 보니 자료형의 이름이 보이는것이 통일되게끔 작업한거 같기도 하다.
한개 함수는 항상 같은 자료형을 return 하는것이 좋기 때문에 조건에 맞는 데이터가 없어서 return 할 값이 없다 하더라도 None을 반환하지 않고 초기 자료형을 반환하도록 작업한다. 때문에 return 될 변수는 함수 첫 부분에 초기상태로 선언해둔다.

def some_function(a) -> dict:
    res = {} # 혹은 res = dict()
    if type(a) == int:
        res["type"] = "int"
    return res

만약 return 변수 res 를 초기에 선언하지 않았다면 if 문 안에서 res 변수를 선언하는 동시에 값을 담아 return 하고, if 문 바깥쪽에 예외상황의 return 을 선언해 주면 되긴 하다

def some_function(a) -> dict:
    res = {} # 혹은 res = dict()
    if type(a) == int:
        res = {"type": "int"}  # 혹은 res = dict(type='int')
        return res
    return {} # 혹은 return dict()

하지만 조건문이 여러개가 되고, 코드가 복잡해지면 return 이 빠지는 곳이 있을수 있어 모든 조건을 확인 한 후 마지막에 return 하는 방식으로 작업한다. 이때는, 딕셔너리 타입의 변수 res를 선언할때 res={} 이나 res=dict() 이 어떠한 차이가 있는줄 정확히 이해하지 못하였었다.

# 괄호를 이용하기

dict_var = {}
list_var = []
------------------------------
>>> print(dict_var, type(dict_var))
{} <class 'dict'>
>>> print(list_var, type(list_var))
[] <class 'list'>

# 내장함수 이용하기

dict_var2 = dict()
list_var2 = list()
------------------------------
>>> print(dict_var2, type(dict_var2))
{} <class 'dict'>
>>> print(list_var2, type(list_var2))
[] <class 'list'>

출력 결과를 보나, 타입을 보나 둘다 차이가 없어보인다. 하지만 python 의 timedit를 사용해 두가지의 변수 선언 방식의 시간 효율을 따져보니 차이가 발견되었다.

2. 선언 방식에 따른 실행 속도의 차이 : timeit

timeit 은 python에서 제공해주는 모듈로 timeit 이후의 명령어를 실행하는데 걸리는 시간을 확인해준다.

timeit.timeit(stmt='pass', setup='pass', timer=<default timer>, number=1000000, globals=None)

stmt 은 timeit 으로 측정할 코드 및 함수 주체이며, setup stmt에 선언된 코드 및 함수를 실행하기 위해 필요한 사전 함수이다. 이때 실행속도 측정에 setup의 시간은 포함되지 않는다.
timer 함수로 Timer 인스턴스를 만드는데 default 값이 지정되어 있으며, number 실행으로 timeit() 메서드를 실행한다.
이때 number 인자도 default 값으로 10000000 이 지정된다. 또한 비필수 인자인 globals 는 코드를 실행할 이름 공간을 지정한다.

위 모듈을 통해 변수 초기선언 방식인 dict()와 {}의 속도차이를 확인해 보았다.

~ > python -m timeit "dict()"
10000000 loops, best of 3: 0.0451 usec per loop
~ > python -m timeit "{}"
100000000 loops, best of 3: 0.0115 usec per loop

단순 빈 자료형 선언인데도 속도가 무려 4배 넘게 차이가 났다.
그렇다면 변수를 초기 선언하면서 값을 세팅할때는 얼마나 나는지 1개 key-value 를 담아서 확인해보았다.

~ > python -m timeit "dict(fruit='apple')"
10000000 loops, best of 3: 0.0806 usec per loop
~ > python -m timeit "{'fruit': 'apple'}"
10000000 loops, best of 3: 0.0263 usec per loop

위 상황보다는 덜 나지만 비슷하게 4배정도 차이가 나는걸 확인할 수 있었다.

0.03초 차이가 크지 않아 보이지만 프로그래밍에서는 굉장한 차이를 의미한다.

따라서 변수를 선언할 때에도 이런 유의미한 차이를 이해하고 작성하면 조금더 효율적인 코드를 작성 할 수 있을 것이다.

알고리즘 문제풀이를 이어가다가 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에 남아있게 되었다. (이후 처리됨)

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