파이문

문제 설명 링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다. 솔루션 꼼수 가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다. 참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다. 아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다. 하지만 이러면 constant space complexity 를 만족할 수가 없다. 두뇌 풀가동 merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다. 이는 tortoise-hare..

문제 설명 HashMap 을 구현하는 문제다. Python 으로 풀었다. 전체 코드는 여기서 볼 수 있다. 솔루션 Java의 HashTable 구현과 비슷하게 풀었다. 리스트를 두고 key 와 리스트 사이즈간의 hash 값을 구해서 리스트의 인덱스로 사용하였다. 인덱스가 겹칠 경우 (hash collision) 링크드리스트로 노드를 만들어서 넣어두었다. class Node: def __init__(self, key=None, value=None): self.key = key self.value = value self.next = None def __str__(self): return "Node(key:%s, value:%s, next:%s)" % (self.key, self.value, self.next..

☢️ 주의 레디스를 모르는 상태에서 의식의 흐름대로 조사하고 정리한 내용입니다. 발단 Redis에서 같은 키를 사용하는 서로 다른 어플리케이션이 있었다. 가장 베스트는 Redis 서버를 아예 분리해서 각각의 어플리케이션이 분리된 Redis 를 이용하면 되겠지만, 남는 서버도 없고 어플리케이션의 서비스 크기가 크지 않고 (메인 서비스가 아니고 부가적인 서비스였다.) 그러다 보니 서버 발주는 오바였다. MySQL 이 Database 를 여러개 두는 것 처럼 Redis 도 그럴 수 있지 않을까? 생각하였는데, 찾아보니 Redis 도 Database 를 여러개 둘 수 있었다. 아무 명령도 치지 않았고, 그냥 기본적인 것들로 사용하였다면 DB 는 자동으로 0 번이다. 만약 다른 DB 를 사용하고 싶다면 selec..

멀티쓰레드 환경에서 캐시 사용하기 프로그램을 개발하다 보면 캐시를 사용해야 하는 경우를 심심치 않게 발견하곤 한다. 특히 DB 에 접근하여 데이터를 가져올 때, 계속 SELECT (또는 get, scan 등) 하기 보다는 캐시를 사용하는 경우가 많다. DB 에서 값을 가져오는 비용이 비싸지 않아도 IO, 네트워크 latency 비용을 최소화 하려고 하기 때문이다. 캐시는 알고리즘 문제 풀이에서도 자주 사용하는데, 이 경우엔 재 연산 (연산 비용) 을 줄이기 위해서이다. 본 게시글에선 자바를 이용한 예제를 작성하도록 하겠다. 캐시란? 캐시의 정의를 다시 한번 짚고 넘어가보자. 캐시는 동일한 input 에 대해서 같은 작업을 하지 않도록 하는 것이다. 같은 작업을 하지 않는 다는 의미는, input 에 대한..