오늘 한 일☀️

• deque 공부
• 알고리즘 하 문제 위주 풀이 -> 완료
• 알고리즘 문제 오답 -> 진행 중
• 이진 탐색 공부(lower bound, upper bound, check 위주) -> 진행 중

deque

deque는 앞, 뒤에서 데이터를 정리할 수 있는 양방향 자료형이다.
+) 왜 양방향이 필요한가! 한쪽 방향으로만 출입구를 사용하면 맨 앞에 있는 원소를 제거할 때 n번의 이동이 필요하다. 평균적으로 n/2. 하지만 앞에서 뺀다면 1번만에 빠지기 때문에 상관없다.
자료구조 개념은 이전에 공부한 경험이 있으니, 각 언어에서 사용법을 알면 될 것 같다.

참고로 deque를 파이썬 공식 문서에서 찾아보면 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너 라고 나온다. 여기서 컨테이너는 데이터 종류에 무관하게 저장할 수 있는 자료형이라고 한다. 예를들어, 튜플(tuple), 리스트(list), 딕셔너리(dictionary)는 문자가 와도, 정수가 와도 상관없는 타입에 무관하게 저장이 가능한 컨테이너 객체이다. 이들은 컨테이를 상속한 자료형이다. 반면에 정수, 실수, 복소수 등은 타입이 고정되어 있는 잔일 종류 자료형이다.

• from collections import deque

from collections import deque
d = deque([1,2,3,4,5])	
d.append(6)	# 맨 뒤에 넣기
d	# 1, 2, 3, 4, 5, 6 

d.appendleft(0)	# 맨 앞이 빠짐
d	# 0, 1, 2, 3, 4, 5, 6

d.pop()	# 맨 뒤가 빠짐
d	# 0, 1, 2, 3, 4, 5

d.popleft()
0

d.rotate(2)
result = list(q)
result	# 4, 5, 1, 2, 3	-> 2만큼 오른쪽으로 회전하여 첫 값이 4가 된다.

d.rotate(-2)
result = list(q)
result 	# 3, 4, 5, 1, 2

Revivew

이분탐색

그동안 풀이한 알고리즘 문제들 중 온전히 내 힘으로만 풀지 않은 것들을 정리하지 않다보니 이후에도 발전이 없음을 느꼈다. 그래서 오늘은 풀이한 문제를 일부 리뷰하였다.

탈출조건에서 오랜 시간을 잡아먹은 나무 자르기 문제를 다시 보았다.
그동안 이진탐색을 자르다가 찾으면 -> 위치 반환, 계속 그렇게 범위 좁히다가 left, right 바뀌면 -> 종료 이렇게만 생각하고 풀이하는 경우가 많았는데 그렇게 단순하게 생각하기에 놓치는 부분이 많았다.

그래서 찾아보다보니 이런 좋은 글이 있었다.
https://www.acmicpc.net/blog/view/109

탐색 문제를 결정 문제로 생각하여 풀이하는 것인데 나처럼 범위에 대한 실수를 줄일 수 있을 것 같다.

또 괜찮은 사냥꾼 풀이를 찾아보니 lowerbound, upperbound 또 파이썬의 이진 탐색 알고리즘을 구현한 모듈인 bisect를 사용하는 경우도 많던데 내일은 이것들을 한번 정리해봐야겠다.

LIS

LIS를 탐색으로도 풀어봤다.(시간초과나서 백준 통과는 실패!)

다음과 같은 LIS의 특징을 정리하고 문제 풀이 한다.
1. 정수 i,j에 대해 i < j이면, S[i] < S[j]이다.(0 <= i, j <= |S|)
2. 정수 i,j에 대해 S[i] < S[j]이면, 원 배열 arr에서 S[i], S[j] 두 수의 위치 전후관계는 같다. (0 <= i, j <= |S|)

def lis(arr):
    if len(arr) == 0:
        return 0

    length = 1
    for start in range(len(arr)):
        next = []
        for j in range(start+1, len(arr)):
            if arr[start] < arr[j]:
                next.append(arr[j])
        length = max(length, 1 + lis(next))
    return length

print(lis(A))

증가 부분수열의 첫번째 수를 선택하고, 그 뒤에 있는 원소 중 큰 값들을 배열에 추려 재귀한다. 큰 값들 입장에서는 첫번째 수가 자신보다 작은 것을 의미한다. 따라서 큰 값들끼리 부분수열을 하여 재귀적으로 이전값의 길이를 1씩 더해니간다.

재귀적으로 더해나간다는 것이 중요 포인트라고 생각한다. 어차피 정확한 LIS는 중요하지 않고 길이만 알면 되기 때문이다. 이 문제 말고도 최장길이를 구할 때 이러한 컨셉이 많이 쓰이는 것 같다. depth로 연관지어 생각하기!⭐️

오늘은 일찍 일어나서 빨래도 하고, 오랜만에 운동도 하고, 발레 공연도 봤다.(그리고 다시 돌아왔다.) 오랜만에 갔던 곳을 다시 가보기도 하고, 간만에 취미도 하니, 이곳에 입소하기 전의 나로 돌아간 것 같았다.✨
오늘 본 발레 공연에서 코다(절정)이 인상깊었다. 발레리노가 연속으로 풍차돌리기(?)하고, 발레리나가 푸에테를 도는 장면에서 사람들이 모두 박수쳐주고 환호하니 무용수들도 신이 났다. 또 그분들한테서 나오는 좋은 에너지가 뒤에서 3번째 자리인 나에게까지 느껴졌다. 어쩌면 그들이 가지고 있는 좋은 인격이 춤에 반영된 것일 수도 있다.
그들을 보면서 나도 동료로서 주변이들에게 좋은 에너지를 전달하기 위해 좋은 인격을 갖춘 사람이 되어야겠다고 다짐했다.

내일 할 일👊

• 알고리즘 복습 마무리
• 알고리즘 문제 풀이