일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 문제풀이
- HBase
- Java
- 자바
- programmers
- Python
- docker
- 코드워
- 파이썬
- redis
- boj
- leetcode
- OOM
- DP
- 튜토리얼
- 리눅스
- scala
- Linux
- zookeeper
- 알고리즘
- 스칼라
- codewars
- 주키퍼
- 프로그래머스
- golang
- 동적프로그래밍
- go
- gradle
- dynamic programming
- Go언어
- Today
- Total
목록전체 글 (109)
파이문
타겟 넘버 숫자 배열이 주어지고, 각각을 더하거나 빼서 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..
Zookeeper 주키퍼는 기본적으로 분산 시스템을 위한 코디네이터다. 주키퍼 주키퍼는 데이터를 디렉토리 구조로 관리하며 key-value 스토리지 처럼 key 로 접근 가능하다. 물론 value 를 사용하지 않아도 된다. 그럴 땐 임의로 "" 와 같이 빈 문자열을 넣어준다. 이러한 디렉토리 구조는 (당연하겠지만 tree 형태) 계층을 가지고 있고 각 데이터 노드를 znode 라고 부른다. 이러한 znode를 다루는 주키퍼 작업을 recipe 라고 부른다. 주키퍼의 쿼럼 주키퍼의 쿼럼은 적어도 하나의 앙상블 (서버군) 과 겹쳐야 하며 과반수가 넘어야 한다. 만약 서버가 5대라면 쿼럼은 3개여야 한다. 만약 5대의 앙상블 서버 들 중 2대만 쿼럼으로 지정한다면 아래와 같은 시나리오가 발생한다. 서버 s1,..
Split Brain 이란? 시스템의 두 부분 이상이 독립적으로 진행되어 시스템이 일관되지 않게 동작하는 것을 말한다. 분산 시스템에서 마스터-슬레이브 상태에서 네트워크 이상으로 인해 슬레이브는 마스터가 이상이 있다고 판단한다. 때로는 맞을 수도 있고 때로는 오탐일 수도 있다. 만약 잘못된 판단임에도 슬레이브 중 하나가 마스터로 선출이 되면 두 개의 마스터가 존재하게 된다. 이런 경우를 Split Brain 스플릿 브레인이라고 부른다.