Algorithms, Part 1/2주차

Java collections library java의 collections라는 라이브러리엔 유용한 툴들이 많이 들어있습니다. python에도 같은 이름의 라이브러리가 있어서 코딩테스트 문제를 풀이할 때 종종 사용됩니다. War story (from Assignment 1) 과제 1이었던 percolation 문제를 예로 들어서 라이브러리 사용에 충분한 이해가 전제되어야 함을 강조하고 있습니다. n by n 사이즈의 문제를 다룰 때, 이를 배열로 풀이한 사람은 N^2 만큼의 시간이 소요됩니다. 반면 이를 linked list로 풀이하면 N^4의 시간, 즉 제곱만큼의 시간이 소요됩니다. 이는 linked list가 탐색을 수행할 때 배열의 길이 n에 비례하는 시간 복잡도를 가지기 때문입니다. 즉, 상수(c..

Iteration 실제로 어떤 작업이 이루어질 때 그 내부 구조에 대해서 사용자는 굳이 알 필요가 없습니다. 그래서 사용될 수 있는 Java의 좋은 기능 중 하나가 iterator라고 합니다. python에서도 iterable 객체에서 값을 하나씩 꺼낼 수 있는 iterator가 존재합니다. Stack iterator: linked-list / array implementation itertator의 구조를 자세히 살펴보고 있습니다. 호출이 될 때마다 current에 저장된 값이 다음 값으로 넘어가는 것을 알 수 있습니다. Bag API 강의가 너무 오래 전이라 그래서 어느 정도의 괴리가 존재하는지 모르겠네요.. python의 set 자료형을 말하는 것 같습니다. 이때 당시의 자바는 이걸 Bag이라는 A..

Parameterized stack 이 내용도 사실 파이썬과는 큰 차이가 있습니다. Java에서는 generic이라는 것이지만, 파이썬에서는 type hint를 지원하기 때문입니다. run time error를 지양하고 compile 단계에서 에러가 발생하도록 하는 장치라고 볼 수 있습니다. 어떤 프로그램이 곧 product라고 생각하면, 고객에게 전달된 뒤에 문제가 발생하는 것보다 내 손에 있을 때 발생하는 것이 낫겠죠. 그래서 사전에 정해진 일반적인 형태 등을 정해놓은 것이 generic, 그리고 파이썬에서는 type hint라고 이해하면 될 것 같습니다. Generic stack: linked-list implementation generic type name을 사용해서 기존의 코드를 개선한 예시입..

Queue API Queue 자료구조는 Stack과 정반대의 특성을 지닙니다. 대표적으로 FIFO, 들어온 순서대로 나가는 특성을 지니고 있죠. Queue: linked-list representation 파이썬에서는 포인터라는 개념이 없기 때문에 더욱 어색하지만 개념은 간단한 것 같습니다. 아이템을 추가할 때는 맨 앞에, 제거할 때는 맨 뒤에서 하다보니 가리키는 주소값이 두 군데여야 한다는 것입니다. Queue dequeue: linked-list implementation Queue: linked-list implementation in Java 굳이 파이썬으로 이런 코드를 짤 필요는 없는 것 같습니다.. 단순히 deque를 불러와서 추가할 줄만 알면 충분합니다. 참고로 popleft를 쓰면 배열의 ..

Stack : resizing-array implementation array의 크기를 재조정하는 것은 아주아주 비효율적인 방식입니다. 왜냐하면 크기를 재조정할 때마다 배열의 모든 아이템을 복사해야 하기 때문이죠. 이러한 경우 N개의 아이템을 삽입할 때, 총 연산 횟수는 (N^2) / 2이기 때문에 N이 충분히 클 때는 활용 불가능한 방식입니다. 따라서 배열의 크기를 매번 재조정하는 것이 아니라, 배열이 꽉 찼을 때만 이를 두 배로 늘리는 방식을 사용합니다. 이때는 N개의 아이템을 삽입할 때 N만큼의 시간이 걸립니다. Stack : amortized cost of adding to a stack Stack : resizing-array implementation 배열의 크기를 줄일 때도, 그 작업을 매번..

Stacks and queues Stack : 가장 최근(마지막)에 추가된 아이템을 확인하는 자료구조 Queue : 가장 처음에 추가된 아이템을 확인하는 자료구조 Client, implementation, interface Stack API Stack과 관련된 아주 기본적인 method입니다. stack에 아이템을 추가하는 push, 마지막 아이템을 제거하며 반환하는 pop, stack이 비었는지 확인하는 isEmpty 등이 있습니다. 물론 Java 기준이기 때문에 Python과 약간의 차이는 있지만 LIFO 구조 자체는 동일합니다. Stack test client 아주 간단한 stack 예제 입니다. 문자열이 '-'과 동일할 땐 pop하며 출력, 그렇지 않을 땐 stack에 추가합니다. 따라서 예시는 ..