Algorithms, Part 1

Sorting problem key를 기준으로 오름차순 정렬한 예시입니다. Sample sort client 1, 2 숫자, 문자(알파벳)를 기준으로 정렬한 예시입니다. Sample sort client 3 directory를 기준으로 정렬한 예시입니다. Callbacks 데이터 타입에 대한 정보가 주어져있지 않은 상황에서도 정렬을 수행하기 위해 callback 메커니즘이 사용됩니다. comparetTo( ) 메서드를 통해 두 아이템의 타입을 비교할 수 있습니다. Java에서는 인터페이스라는 특정 메서드를 사용합니다. Callbacks: roadmap 객체 형식을 지닌 배열이 인자로 전달됩니다. Java의 comparable interface 같은 것을 generic이라고 합니다. compareTo( )..

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 배열의 크기를 줄일 때도, 그 작업을 매번..