파이문

단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 DFS 풀이 begin 과 한 글자 차이가 나는 단어를 찾고 그 단어에서 부터 모든 words 와 (역시 한 글자 차이가 나는 ) 비교해 가며 구현한다. 이 때 정답은 가장 적은 변화로 target 을 찾는 경우의 수를 구하는 문제다. 우선 처음 for 문으로 모든 words 에 대해 비교한다. 즉 begin -> 1번 단어 -> .... -> 종료 와 begin -> 2번 단어 -> ... -> 종료 와 같이 begin 바로 다음에 비교할 단어를 words 의 모든 단어를 대상으로 하는 것이다. 이 구현대로 하면 1 번 단어 -> 2번 단어와 2번 단어 -> 1번 단어와 중복되는 계산이 있을..

네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 DFS 풀이 문제 설명이 길지만, 축약하자면 undirected graph 에서 연결 되지 않은 그룹이 몇개 있는지에 대한 문제다. DFS 로 그래프를 따라 가되, 이미 방문 했던 노드면 패스하고 방문하지 않았던 노드면 다시 계속 따라가게 구현하면 된다. 노드의 방문에 대한 여부는 미방문(0), 누군가가 방문 하고 있는 중 (1), 방문 완료(2) 로 확인할 수 있지만... 문제에선 사실 여기까진 필요없고 단순히 boolean 으로 확인하면 된다. (만약 directed graph 라면 이 알고리즘을 써야 한다. 참고) class Solution { public int dfs(int i, int..

타겟 넘버 숫자 배열이 주어지고, 각각을 더하거나 빼서 target 을 만들 수 있는 모든 경우의 수를 구하는 문제였다. 자바로 풀었다. https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 풀이 재귀로 모든 경우의 수(더하고, 빼고) 로 다 넣어서 구한다. 만들어진 최종 값이 target 과 동일할 경우 1을 리턴하고 이 값을 누적한 것이 결과 값이다. class Solution { public int dfs(int prev, int index, int[] numbers, int target) { if (index >= numbers.length) { if (target == prev) { return 1; } return 0; } int cur1..

문제 설명 링크드 리스트가 주어지는데, 상수의 공간 복잡도와 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 에 대한..

https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos https://raft.github.io/

주키퍼를 통한 리더 선출 HBase 를 비롯한 많은 분산 시스템에서는 주키퍼를 통해 일관성, 가용성 (CAP 이론중 CA) 을 보장 받고 있다. Leader Election (리더 선출) 다양한 다른 분산 시스템과 같이 주키퍼를 이용해 고 가용성 어플리케이션을 설계할 일이 생겨서, 리더 선출 방법들을 살펴 보았다. 이 방법은 최선이 아닐 수 있다. 리더 선출 준비 우선 임의의 path 를 지정한다. 여기서는 /election 이라고 하겠다. /election 하위에, 가용하는 서버 목록의 정보들을 Ephemeral-sequential 모드로 생성하는 것이 핵심이다. 만약 서버가 1번부터 10번까지 총 10개 있다고 해보자. (혹은 10개의 프로세스라고 볼 수도 있다.) 1번 서버(혹은 프로세스) 가 /e..

FailSafe 를 사용한 Java Retry 예제 Delay 시간을 주면서 Retry 를 하려고 하다가, FailSafe 라는 오픈 소스를 발견했다. Star 도 2k 개가 넘고, 최근 (8월) 까지도 커밋하길래 사용하기로 하였다. 사실 Retry 관련해서 스택오버플로우 검색을 했는데, FailSafe 개발자가 열심히 홍보하더라 Usage 사용하기 전에 RetryPolicy 라는 클래스로 정책을 생성해야 한다. RetryPolicy 생성 아래의 예제는 ConnectionException 이 날 경우 1초의 Delay 로 3번 Try 를 하게 만드는 코드다. RetryPolicy retryPolicy = new RetryPolicy() .handle(ConnectException.class) .withD..