1.개발 진행 및 완료상황
- 2주차 python algorithm 우선순위 큐 문제풀이중
-
업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용
- priority queue 문제를 풀때 heapq를 사용해야 하는지, 기본적인 in-built함수로 구현할 줄 알아야 하는지 궁금했다. 코치님께 질문하였는데, 그 이유를 스스로 생각해보고 찾길 원하셨는지 여러가지 질문들을 하셨다. 시간복잡도, 자료구조, list, stack, queue등을 물어보셨는데 답변을 못하였다. 기초적인 개념들에 대한 이해가 부족하다는 것을 뼈저리게 느꼈다. 이와 관련된 공부들은 3번에 후술하였다.
- 새로 배운 내용
array 와list, tuple, dictionary, set의 개념과 차이 :
array(배열)는 하나의 값을 저장하는 변수가 아니라 묶음 단위로 값을 저장하기 위한 것이다. list와 tuple은 data container이며 배열을 구현하는데 사용한다.
list는 순서, index를 가지고 있고 mutable하여 값을 변경하는 것이 가능하다. 특정 값의 존재를 확인하는 in연산자를 적용하면 하나씩 스캔후 결과를 반환하기에 성능이 낮다.
tuple은 list와 마찬가지로 순서, index가 있지만 immutable하여 수정이 불가능하다. 같은 data를 저장시 list보다 적은 용량을 차지하기 때문에 수정이 불필요하고 간단한 형태에서는 tuple을 사용하는 것도 좋다. 또한 unpacking이라고 하여 튜플의 갚을 한번에 차례대로 변수에 대입하는것이 가능하다.
dictionary는 key와 value로 구성되어 있다. 중복된 원소가 존재할 수 없고 원소의 순서도 없다. 원소가 각자 key값을 가지고 있기 때문에 in연산자 사용시 크기와 무관하게 연관 속도가 일정하여 list보다 성능이 좋다.
set : key값으로만 구성되어 있다. dictionary와 마찬가지로 중복이 불가능하고 순서가 없다. list에서 중독된 원소들을 제거하고 싶을 때 set으로 변환하기도 한다.
stack과 queue의 operation :
stack은 후입선출이 특징이다. push로 데이터를 삽입하고 pop을 통해 데이터를 꺼낸다. push,pop이 이뤄지는 윗부분이 top이고, 아랫부분은 bottom이다.
queue는 선입선출이 특징이다. enqueue로 데이터를 추가하고 dequeue로 꺼낸다. 데이터를 넣는 쪽과 꺼내는 쪽이 다른데 전자를 rear, 후자를 front라고 한다.
priority queue는 우선순위 큐로 enqueue시 데이터에 우선순위를 부여하여 추가한다. 이를 바탕으로 dequeue시 우선순위가 높은 데이터를 꺼낸다. heapq.heappush(heap, data)로 데이터를 넣고 heapq.heappop(heap)으로 꺼낸다.
list와 deque, priority queue의 시간 복잡도 차이:
deque를 사용하면 list보다 훨씬 속도가 빠르다. 시간복잡도는 list는 O(n), deque는 O(1)이다. 특히 append,remove,push,pop 등의 연산이 많을수록 차이가 두드러진다. deque사용시 Max length를 정할 수 있고, 양쪽에서 요소의 추가 삭제가 이루어질 수 있다. 반면 list는 fixed size memory array라서, 고정된 사이즈의 메모리를 가지고 있다. 첫번째 원소를 삭제하면 뒤의 모든 원소를 앞으로 이동해야 한다. stack은 순차적으로 원소를 처리하고 구조가 단순하여 구현이 쉽고 데이터 저장 및 읽기 속도가 우수하다. 하지만 저장 개수를 정해야해서(재귀함수 호출시) 공간낭비의 우려가 있다. 우선순위 큐는 heap 자료구조를 사용한다. N개의 데이터 처리를 기준으로 최악의 경우 복잡도는 list의 경우 O(N^2), heap은 O(NlogN)이다. 데이터가 커질수록 차이가 극명해진다.
Heapq 사용 여부의 차이 :
이 개념 공부를 하게 된 원인이다… 우선 heap이란 완전이진트리를 기본으로 가지는 자료구조이다.
이진트리는 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 의미하다. 이 이상이 안될 뿐 없거나 하나만 있어도 된다. 왼쪽 자식과 오른쪽 자식을 구분한다.
완전이진트리는 루트부터 아래쪽 레벨로 노드가 가득 차있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진트리를 의미한다.
이진 탐색(검색) 트리는 모든 노드가 두가지 조건을 만족해야 한다.
- 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.
- 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.
즉, 키값이 같은 노드는 복수로 존재할 수 없다. 이진 탐색 트리의 특징은 단순한 구조, 중위 순회의 깊이 우선 검색을 통해 오름차순으로 노드값을 얻을수 있음, 이진 검색과 비슷한 방식으로 빠르게 검색 가능, 쉬운 노드 삽입 등이 있다.
다시 돌아와서 heap은 완전이진트리를 구조로 하는 자료구조이다. 그리고 이진 탐색트리의 두가지 조건과는 무관하다. heap은 root를 최댓값(최대 heap) 혹은 최솟값(최소 heap)으로 하여 오름차순, 내림차순으로 정렬할 수 있다. 삽입, 삭제의 시간복잡도는 O(logN)이다. list, sort, pop등이 O(NlogN)임을 감안하면 작다는 걸 알 수 있다.
최소 heap을 기준으로 삽입과 삭제는 다음과 같은 과정을 거친다.
삽입: 왼쪽에서 오른쪽 순서로 완전이진트리를 구성하며 데이터 삽입 -> 입력된 데이터와 부모 노드 비교 -> 부모보다 작다면 서로의 자리를 변경 -> 이전 두단계를 최소 heap 자료구조를 만족할때까지 반복한다.
삭제: root node를 삭제 -> tree의 말단에서 가장 오른쪽에 있는 node를 root로 승격 -> root node가 된 데이터와 두 자식노드의 값을 비교하여 가장 작은 값과 위치 변경한다. -> 이후 자식노드와 비교를 반복하여 완성한다.
결국 heapq를 사용하면 힙을 직접 구현하지 않아도 되는데 시간복잡도의 측면에서 차이가 심하다. tree는 원소에 한번에 접근이 가능한 반면 array를 사용하여 tree를 구현시 메모리 고정할당방식이라는 배열의 특성상 불편한 점이 많다.
반복(loop)와 재귀함수의 차이:
재귀는 동일한 패턴으로 한 문제를 여러개의 단순한 소문제로 나누고 한 소문제를 다른 소문제 내부로 순차적으로 호출함으로서 해결하는 함수적 접근이다. 재귀는 한 소문제를 한번에 해결할 수 있는 함수를 정의함으로서 실행된다. 그 함수 내부 어딘가에서 자신을 다시 호출하여 또다른 소문제를 해결한다. 따라서, 제한 기준이 만족하기 전까지 스스로를 계속하여 호출한다. 메인 프로그램에서 재귀함수의 첫 호출은 작은 문제를 해결하기 위한 작은 호출이 끝나야만 이뤄진다. 따라서 파이썬은 모든 소문제의 결과를 임시 메모리에 저장하고 필요하다면 연산을 실행하고 재귀가 끝난 후 메모리를 해제한다.
반복은 ‘for’와 ‘while’루프를 통해 수행된다. 반복은 제한 기준이 만족되기 전까지 일부 코드를 반복적으로 실행한다. 재귀와는 다르게, 반복은 각 반복의 결과 저장을 위한 임시 메모리가 필요하지 않다. 오히려 프로그래머는 각 반복동안 결과를 수집하기 위해 반복적인 호출 전에 숫자, 리스트, 문자열, mutable한 data type과 같은 변수를 잘 정의해야 한다. ‘for’루프는 리스트, 문자열, 튜플, range같은 sequence에서 반복을 수행한다. sequence에 더이상 원소가 남아있지 않으면 반복을 종료한다. 또한 자동적으로 연속적인 요소들을 가로지른다. 그러나 ‘while’ 루프는 반복의 초기화와 수동적인 증가가 필요하다. while 루프는 반복자와 관련한 조건이 만족되기 전까지 수행된다.
python이 이전 반복단계의 관한 정보를 저장하지 않기 때문에 반복문이 재귀보다 더 빠르고 메모리 사용도 효율적이다. 실제로, 거의 모든 반복은 재귀로도 구현될 수 있고 반대도 마찬가지이다. 같은 함수의 반복적인 호출등의 이유로 어떤 경우에는 반복보다 재귀가 더 간단히 수행되기도 한다. 반면에 어떤 것들은 재귀보다 반복이 더 수월하기도 하다. 시간 복잡도와 메모리의 관점에서는 반복이 재귀보다 선호된다. 재귀와 반복 중 while 루프는 무한 호출 같은 위험한 상황을 초래하기도 한다. 만약 제한 기준이 충족되지 않으면, while 루프나 재귀함수는 수렴되지 않고 프로그램 실행의 중단으로 이어진다.
재귀는 함수의 정의로 실행되기 때문에, 이 함수는 프로그램 내부 어디서든 호출될 수 있다. 반복 코드는 필요한 곳에 있어야 한다. 그럼에도 불구하고 반복 코드는 전형적인 파이썬 함수 내부에서 선언하여 일반화 될수 있다.
- 참고할 만한 레퍼런스들
-
- 자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
- https://analyticsindiamag.com/ultimate-guide-to-recursion-and-iteration-in-python/
- https://heytech.tistory.com/69
- https://kururu.tistory.com/65
- https://evan-moon.github.io/2019/10/12/introduction-data-structure-heap
- https://brownbears.tistory.com/550
- https://autumn-irene.tistory.com/73
- https://wellsw.tistory.com/122
- https://cording-artist.tistory.com/124
- https://heytech.tistory.com/68
-
특이사항
- 문제 풀이도 중요하지만 정확한 개념에 대한 이해가 필요하다.
-
회고
- 제대로 이해하고 공부해야겠다. 말로 설명할 수 없는 것은 아는게 아니다.
- TO-DO-LIST
- 알고리즘 개념 공부
- 2주차 알고리즘 백준 문제(우선순위 큐) 마무리하기
- CSAPP 읽기
