-
Sparse TableAlgorithm&Data Structure 2018. 11. 10. 13:17
Sparse Table Range Qeury를 구할 때 쓰는 자료구조 Range Qeury란 에를 들어 4 6 1 5 7 3 이라는 수열 이 있을때 구간 2 ~ 4 까지 최소 값이 무엇 이냐? 라는 쿼리에 대한 답을 리턴 하는 문제다 Range Qeury를 구하는 방법은 여러 가지가 있다 알고리즘 공간 복잡도 시간 복잡도 Brute Force O(1) O(N) Dynamic Programming O(n^2) O(1) Segment Tree O(N) O(logN) Sparse Table O(NlogN) O(1) 위 표에서 복 수 있듯이 input data가 변하지 않고 쿼리가 빈번하게 일어나는 일나는 상황에서 쓰이는 자료구조이다 Sparse Table을 구하는 방법 주어진 데이터를 Preprocessing..
-
Geth Trie insertBlockChain 2018. 11. 9. 14:32
Trie insert 테스트 trie_test.go 의 insert를 통하여 이더리움의 머클 페트리시아가 어떻게 데이터를 Insert하는 디버그 과정 trie := newEmpty() updateString(trie, "doe", "reindeer") updateString(trie, "dog", "puppy") updateString(trie, "dogglesworth", "cat") trie_test.go 위 코드를 따라가면 trie.go 의 trie.Update(key,value) 메소를 따라 간다 func (t *Trie) Update(key, value []byte) { //트라이에 변경을 시도하려는 함수 호출 if err := t.TryUpdate(key, value); err != nil {..
-
Go언어의 가비지컬렉션 알고리즘Golang 2018. 11. 7. 10:53
Go언어의 가비지 컬렉션 알고리즘의 핵심이 삼색알고림에 대해 알아보려고 합니다. 먼저 삼색알고리즘에 사용하는 정의 부터 알아 보겠습니다. 흰색 집합: 프로그램에서 더 이상 접근 할 수 없어 가비지 컬렉션이 되는 대상입니다. 검은색 집합: 프로그램이 사용 하고 있으며 흰색 집합의 오브젝트를 가리키는 포인터가 확식히 없는 오브젝트의 집합입니다. 회색 집합: 프로그램이 현재 사용하고 있지만 흰색 오브젝트를 가리키고 있어 검사 과정이 필요한 집합입니다. Point 검은 색에서 흰색 집합으로 연결 되지 않아 흰색 집합의 오브젝트를 제거 할 수 있습니다. 삼색 알고리즘 Process initial 모든 오브젝트가 흰색인 상태 Process Step 1 루트 오브젝트를 방문해서 탐색을 한 후 회색 집합으로 이동 시킨..
-
Codeforce #515 Binary Numbers AND SumProblem_Solving 2018. 10. 28. 14:06
Codeforce #515 Binary Numbers AND Sum 문제 원본 문제설명 입력 조건 2개의 이진수 자리수 n,m 자리수 만큼 이진 수가 들어온다. 이진수 a 와 b를 and 연산 한 값을 구한 뒤 b를 오른쪽으로 shift연산을 한다. 다음 a와 이전에 b를 오른쪽으로 shift 여산한 값을 and연산 한 값을 구한뒤 현재 b를 shift한다. b가 더이상 shift할수 없을 때 까지 반복한다. 문제 풀이 1 step 이진수 a를 전처리 한다. 전처리 방법은 누적합을 구한다. ex) 이진수 1010이 주어지면 비트가 켜신곳에 2의 지수승을 더하고 이전 인덱스에 최종적인 합을 누적해서 보관한다. 만약 b의 이진수 길이가 더 클경우 부분합 배열을 b의 이진수 길이 만큼 구한다. 위의 배열의 값..
-
BOJ 16236 아기상어Problem_Solving 2018. 10. 27. 14:34
BOJ 16236 문제풀이 문제원본 문제 설명 주어진 조건 처음 상어의 크기가 2이고, 상어는 1초에 상하좌우로 이동할 수 있다. 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 물고기를 자신의 무게 만큼 먹으면 무게가 1씩 증가한다. 상어는 같은 크기의 물고기는 먹을 수 없지만 같은 크기의 물고기가 있는 칸은 지날 수 있다. 먹을 수 있는 물고기가 한 마리면 그 물고기가 있는 위치로 이동 만약 먹을 수 있는 물고기가 여러 마리 라면 가장 가까운 위치로 이동 거리가 같은 물고기가 많다면 가장 위쪽 이런 경우도 많다면 가장 왼쪽에 있는 물고기를 먹는다. 먹을 물고기가 없으면 종료한다. 구해야 되는 것 아기 상어가 주어진 조건에 맞춰 물고기를 먹을때 걸리는 시간 문제 풀이 1 step 현재 위치에서 도..
-
BOJ 2479 계단오르기Problem_Solving 2018. 10. 25. 23:37
BOJ 2579 문제 풀이 문제원본문제 설명 0번 째 지점에서 n번째 계단 까지 올라 갈때 최대로 얻을 수 있는 점수를 구하는 문제 단 계단을 하나 또는 두개를 밟을 수 있고 연속으로 세계를 밟을 수 없다. 문제 풀이 점화식 DT[현재 계단 위치][이전에 밟은 스탭] = MAX(DT[+1 계단][1], DT[+2 계단][2]) 단 연속 3계단은 밟지 않는다. 소스코드 사용 알고리즘GOC++DP 재귀호출 (N=300)4608kb/4ms (input에서 string으로 받음)1992kb/0ms
-
boj11505 구간 곱구하기Problem_Solving 2018. 10. 25. 16:49
boj11505 구간 곱 구하기 문제 풀이 문제원본 문제 설명 N개의 숫자가 주어지고 두가지 쿼리 입력된다.첫번째는 구간의 곱을 구하는 쿼리두번째는 특정 노드의 수를 변경 하는 쿼리 문제 풀이 기본적인 Segment Tree문제이다Segment Tree는 각 구간에서 최소 또는 최대 부분합 등을 빠르게 구할 수 있는 자료구조이다 소스 코드 사용 알고리즘GOC++Segment Tree(재귀호출)40524kb/432ms (input에서 string으로 받음)33235kb/380ms
-
boj 1953 팀배분Problem_Solving 2018. 10. 25. 16:37
boj 1953 팀배분 문제 원본 문제 설명 학생을 청팀과 백팀으로 두팀으로 나누는데 각각의 학생은 싫어하는 학생이 있다.각 팀에는 서로 싫어 하는 학생이 존재 하면 안된다. 문제 풀이 1 step그래프를 생성할 때 싫어 하는 사람끼리 간선으로 연결 한다. 2 stepBFS로 탐색하면서 부모랑 다른 팀에 배정 시킨다. 3. step각 학생을 순회하면서 2 step에서 구한 팀을 이용해 팀을 나누어 출력한다. 소스 코드 결과 사용 알고리즘GOC++BFS(List를 이용한 queue)3212kb/4ms (input에서 string으로 받음)1992kb/0ms 참고로 GO를 이용할 때 queue라이브러리가 존재하지만 List로 구현 하였습니다.두개에 대한 차이는 차후 포스팅 할 예정입니다.^^