-
BFS를 이용하여 DAG그래프 인지 판별Algorithm&Data Structure 2023. 6. 11. 16:18
정의 DAG : ( Directed Acyclic Graph) 비순환 그래프 구조 (Ex : Tree) BFS : ( Breadh-First Search) 넓이 우선 탐색 (비순환 그래프에서 Level를 찾을때 주로 사용) Indegree : 부모 노드로 부터 들어오는 간선 개수 Algorithm 각 노드의 indegree를 구한다. indegree가 0 인 노드를 queue에 push한다 해당 노드는 root노드가 된다 BFS로 각 노드를 순회 하면서 방문되 노드의 indegree를 차감 시키고, indegree가 0일때 queue에 push후 카운트를 증가 시킨다. 노드의 순회가 끝난후 카운트의 수가 노드의 수와 같으면 DAG그래 프다
-
BOJ 9934 완전 이진 트리Problem_Solving 2020. 2. 2. 17:41
문제링크 9934번: 완전 이진 트리 문제 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다. 깊이가 2와 3인 완전 이진 트리 상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 www.acmicpc.net #문제 설명 주어진 조건과 노드의 순서를 보고 완전 이진 트리를 구하는 문제 - 주어진 조건 1) 루트에서 시작 2) 왼쪽 노드를 방문하지 않았다면 왼쪽 노드 방문 3) 왼쪽노드를 가지고 ..
-
BOJ 2357 최솟값과 최댓값Problem_Solving 2020. 2. 1. 20:42
문제 링크 1. 문제 설명 N 개의 정수가 주어지고 M개 구간 a와 b가 주어질 때 구간 [a,b]의 최소값과 최대값을 구하는 문제 2.풀이 방법 1) Segment Tree를 이용 하여 구한다. 2) 코딩을 간단하게 하기위해 최소 값 또는 최대값 세그먼트를 구현한뒤 트리를 빌드 할 때 -1를 곱한다. 3.세그먼트 트리 설명 Divide : input으로 들어온 데이터를 반으로 나눈다. Conquer : Divide에서 나누어진 Sub Array A[1...mid] B[mid...N] 의 최소값 또는 최대값을 재귀 적으로 구한다. Combine : 두개로 나누어지 배열에 A, B에서 최소값을 리턴받아 해당 노드에 저장 - 노드에 적혀 있는 번호가 배열의 인덱스 번호 - 해당 구간은 리턴되는 값 만약 N개..
-
Codeforce #521 Div3 D. Cutting OutProblem_Solving 2018. 11. 18. 02:35
문제 원본 문제 설명 배열 S가 주어 졌을 때 길이가 k인 S의 부분 배열 t를 이용해 원소를 제거할 때 가장 많은 시간을 수 행 할 수 있는 부분 배열 t를 구하는 문제 ex 7개의 S배열 원소 3개의 부분 배열의 원소 개수 S = [1,2,3,2,4,3,1] 일 때 부분 배열 [1,2,3]일 때 2 번의 수행 시간동안 배열을 지울 수 있다. 1 번째 수행 때 S배열이 [1,3,2,4]가된다. 2 번째 수행 때 S배열이 [4]가된다. 3 번째 수행 하려고 할 때 S배열에 부분 배열 t가 존재 하지 않으므로 2번의 수행 시간이 걸린다. 문제 풀이 parametric search를 이용한 분제 1 step S배열의 각 원소의 개수를 구한다. 위 예에선 1 : 2개 2 : 2개 3 : 2개 4 : 1개 2 ..
-
Codeforce #521 Div3 E. Thematic ContestsProblem_Solving 2018. 11. 18. 02:05
문제 원본 문제 설명 문제 토픽 N개 가 입력으로 주어 진다. 하루에 하나의 콘테스트가 열리는데 같은 토픽 k개를 제출 할 수 있고 해당 콘테스트는 이전에 열린 콘테스트보다 정확히 2배 많은 토픽을 출제 해야 한다. 이때 최대로 낼 수 있는 문제를 구하는 문제 EX) 첫 번째 input data 18 2 1 2 10 2 10 10 2 2 1 10 10 10 1 1 10 10 첫 째날 1토픽 2개 둘 째날 2토픽 4개 셋 째날 10토픽 8개 총 14개의 문제를 출제 할 수 있다. 문제 풀이 1 step 입력 받은 원소를 정렬한다. 2 step 정렬된 입력받은 원소를 가지고 이분 탐색을 이용하면 각 원소의 개수를 구할 수 있다. 위 예에서 원소를 정렬 하면 1 1 1 1 2 2 2 2 2 10 10 10 1..
-
pBFTBlockChain 2018. 11. 13. 10:56
Byzantine failur model 분산 시스템에서 각 노드간에 상태를 알 수 없다 일부노드가 악의적이거나 장애가 났을 경우 가 있다고 가정하는 모델이다. BFT라고 불리는 시스템은 불량인 노드가 f개가 있을때까지 실뢰할 수 있다는 것을 가정한 시스템이다 예를 들어 5f개라면 전체노드중 1/5이 Byzantine Failure일때 정상적으로 동작하는 모델을 뜻한다. 어떤 노드가 Byzantine Failure일 상황은 크게 두가지이다. 메시지를 보내지 않는 노드 악의적으로 메시지를 보내는 노드 1번의 경우가 발생되면 해당 네트워크를 신뢰 할 수 있는지 판별하기 위해서 (N-f)개의 정족수로 판단 하여야한다. 2번의 경우 (N-f)메시지 중에 악의 적인 노드 f개가 있을때 (N-f) - f > f 라..
-
Raft Consensus AlgorithmBlockChain 2018. 11. 12. 18:00
Consensus Algorithm이란 분산 데이터에서 데이터를 동기화 시키기 위한 알고리즘 Raft는 Consensus Algorithm중 하나로써 다음과 같은 상태를 가진다 Follower State Candidate State Leader State 1 처음 모든 노드는 follower State상태가 된다. Follow State 상태 각 노드에 Election Timeout시간이 랜덤에 부여되고 이시간을 먼저 소진 한 노드가 Candidate State 상태가 되어 자기자신에게 투표후 다른 노드에게 투표해 달라는 신호를 요청한다. 만약 일정 시간동안 응답이 안오면 다시 Election Timout시간을 보낸다. Candidate 노드가 투표를 요청하면 Follow노드들은 투표를 진행 하고, 투표..
-
Array ManipulationProblem_Solving 2018. 11. 11. 14:46
해커랭크의 Array Manipulation문제 풀이문제원본 문제 설명 구간 a b에 k수를 더하는 쿼리가 들어오고, 모든 쿼리가 끝났을 때 배열에서 가장 큰 수를 리턴 하는 문제 문제 풀이 구간 시작 -1 인덱스에 K를 더한다 구간 끝 인덱스에 -K를 한다 배열의 시작부터 끝까지 누적합을 구해가면서 각 인덱스의 값중 최대값을 리턴한다. Ex) 1 5 3 [3,0,0,0,0,-3,0,0,0,0,0] 4 8 7 [3,0,0,7,0,-3,0,0,-7,0,0] 6 9 1 [3,0,0,7,0,-2,0,0,-7,-1,0] 여기서 주의 할점은 인덱스의 위치를 신경써서 저장해야 한다. 개구간인지 폐구간인지는 구현방법에 따라 다르다 소스 코드