분류 전체보기
-
[2019 5급 공무원 2차] 자료구조론 제 1문알고리즘 2020. 6. 12. 00:35
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 1문 제 1 문. 원소 개수가 n개인 집합의 멱집합(Powerset)은 격자구조(lattice)로 표현이 가능하다. 격자구조에서 각 정점은 각 부분집합이며, 두 부분집합 A,B가 A ⊂ B이고, A⊂C⊂B인 집합 C가 존재하지 않을 경우 두 정점 간에 간선이 존재한다. 예를 들어 집합 {1,2,3}에 대한 멱집합을 격자구조로 표현하면 다음과 같다. 물음에 답하시오. (총 20점) 1) 원소 개수가 n개인 집합에서 원소 개수가 k개인 모든 부분집합의 개수를 구하기 위한 int numSubsets(n,k) 함수에 대해 C언어 형식의 의사코드를 제시하고, 제시한 의사코드의 시간복잡도를 빅오(Big-Oh) 표기법으로 표현하시오. (단, 가능한 한..
-
[56회 변리사 2차-4번] 이진트리 (Binary Tree)알고리즘 2020. 6. 3. 19:39
2019년 제 56회 변리사 2차 데이터 구조론 2교시 4번 문제 해설 이진 트리 (Binary Tree) 하나의 노드가 최대 두개의 자식 노드를 가지는 트리를 말한다. 이진 트리 개념 속 여러 용어가 있지만 중요한 몇가지 용어를 소개한다. 노드의 차수 (Degree): 노드의 서브트리 수 단말(Terminal) 노드: 리프(leaf) 노드라고하며 차수는 0 비단말 노드: 차수가 0이 아닌 노드 노드 레벨: 루트 (레벨 1) 트리의 차수: Max(노드의 차수) 트리의 높이 (Height , Depth) : Max(노드 레벨) 자식 (Child) ,형제 (Sibling) 선조 (Ancestor): 루트까지의 경로상에 있는 모든 노드 자손 (Descendants): 한 노드의 서브트리에 존재하는 모든 노드 ..
-
[56회 변리사 2차-3번] Heap Sort알고리즘 2020. 6. 2. 16:52
2019년 제 56회 변리사 2차 데이터 구조론 2교시 3번 문제 해설 Heap Sort (힙 정렬) 힙정렬을 하기 위해서는 데이터가 힙구조 상태여야한다. 따라서 힙정렬 전에 데이터를 먼저 Heapify Algorithm으로 힙구조를 만든다. (힙구조는 여러개 나올 수 있다.) 오름차순 정렬을 위해 Max Heap을 구성하여 Max Heap의 가장 끝에 해당하는 리프노드와 root를 Swap하면 가장 큰 값이 가장 끝에 위치하게 된다. 가장 끝에 가장 큰 값이 위치 했으므로 가장 끝의 위치를 N이라고 하면 N-1의 위치에 그 다음으로 가장 큰 값을 위치시키면 된다. 이후 부터 다시 Max Heap 만들고 리프와 루트의 Swap (N-1)번 작업하며 정렬하는 알고리즘이다. 참고 ↓ https://www..
-
[56회 변리사 2차-2번] 최소신장트리(MST)알고리즘 2020. 5. 28. 18:01
2019년 제 56회 변리사 2차 데이터 구조론 2교시 2번 문제 해설 MST (Minimum Spanning Tree) 그래프 G에서 모든 정점을 연결하여 갈수 있도록 하되, 최소의 간선개수와 최소의 가중치로 이루어진 트리를 말한다. (즉, 정점 개수 V , 간선 개수 V-1, 간선은 무방향) 1. 그래프 G에 관하여 다음 물음에 답하시오 => 정점(Vertax) 의 개수 8 => 따라서 MST를 만족하는 간선의 개수 (8-1) = 7 개를 선택하면 된다. => 이 그래프에서의 MST가 가지는총 가중치의 합은 10이다. => 즉, 가중치의 합이 10인 MST를 구하는 3가지 알고리즘을 해설 한다. (1) 그래프 G에 대해 프림 알고리즘 (Prim's Algorithm)으로 최소신장트리를 구하는 과정을 ..
-
이더리움 서버 구축 WIKI at SSAFY블록체인 2020. 5. 26. 23:32
블록체인 idle 위키 bY 장석우🖥🖥 저희 팀은 p2p 경매 시스템을 구축 하고 있습니다. 사용자가 시스템에 등록한 자산인 디지털 작품을 경매를 통해 판매하고 그 소유권을 이전하는 기능과 경매기능은 서버를 거치지 않고 이더리움 스마트 컨트랙트를 통해 직접 진행합니다. 이때 이더리움 네트워크 상에 작성한 스마트 컨트랙트를 사용하고, 이더리움 네트워크의 통화인 이더가 매개 디지털 작품의 소유권을 프라이빗 혹은 허가형 블록체인의 대표인 하이퍼레저 패브릭에 기록하게 됩니다. 디지털 작품 소유권의 이해관계를 가지는 가상의 컨소시엄이 존재하며 이해관계자에 의해 구성된 패브릭 네트워크 채널과 자산을 관리할수 있는 체인코드로, 시스템을 통한 작품 등록, 삭제 , 경매 완료 등 소유권에 변경이 발생하는 이벤트가 있을 ..
-
[변리사 2차-1번] 구간 히프 (Interval Heap)알고리즘 2020. 5. 25. 19:40
2019년 제 56회 변리사 2차 데이터 구조론 2교시 1번 문제 해설 1. 구간히프를 정의하고, 그 특성에 관하여 설명하시오.(5점) * 먼저 heap이란? 숫자의 최대값, 최소값을 빠르게 탐색하기 위해 고안된 완전이진트리 (Complete Binary Tree)이다. 기본적인 Heap의 각 노드는 하나의 숫자로 이루어져 있으며 삽입,삭제시 리프노드부터 시작하여 부모-자식간의 대소판별 경쟁을 통해 최소 또는 최대값이 항상 루트 노트들 차지한다. 이러한 성질 때문에 우선순위큐 (Priority Queue)는 최소,최대 힙으로 만들어져있다. * 구간 Heap? 구간 히프는 Heap과 동일한 완전이진트리의 형태면서 각각의 노드는 최대 두개의 숫자로 구성 되어있다. 노드에 적힌 두개의 숫자는 폐구간 [a,b]..
-
[백준-1165,13502] 단어 퍼즐 (Trie,DFS,FTP)Baekjoon 2020. 5. 19. 14:22
*답을 구하는 해법을 기술 하였고 실제 제출시 통과되는 풀이는 아닙니다. *실제 제출시 통과되는 풀이로 업데이트 예정 문제 요약 대문자 알파벳이 하나씩 적혀있는 5x5의 보드와 단어 리스트 (사전)가 주어진다. 주어진 보드의 각 칸에서 8방향 탐색을 통해 사전에 있는 단어를 몇개 만들 수 있는지를 구하는 문제이다. 문제 풀이 문자열을 검색한다는 개념에서 Trie를 활용한 풀이를 기술한다. 다만 이 문제의 가장 큰 제약사항은 "소스 코드의 크기가 65536B를 넘을 수 없다"는 점이다. 제약사항을 봤을 때 이 문제를 풀기 위한 올바른 접근 방법은 코드안에 사전 데이터를 미리 넣어야 한다는 것이다. 주어진 사전 속의 단어의 개수는 24830개이고 이 텍스트 데이터들을 코드에 그대로 넣으면 이클립스 같..
-
[백준-11112] Eight Puzzle (Astar Algorithm)Baekjoon 2020. 5. 12. 14:32
문제 요약 8-Puzzle 게임을 푸는 문제이다. 3x3 보드판에 한칸의 빈공간, 나머지 칸에는 1~8 숫자가 무작위로 위치해 있다. 빈칸과 숫자의 자리를 바꿔 이동시키며 정답을 찾아가는 게임이다. 입력으로 주어지는 보드는 1부터 8사이의 숫자가 섞여있으며 #은 빈 공간을 나타낸다. 빈공간과 인접한 칸의 숫자와 자리를 바꿔보며 원하는 보드의 모양을 만들기 위한 최소의 이동 횟수를 구하면 된다. 문제 풀이 기본적으로 탐색 알고리즘을 통해 풀 수 있는 문제이다. 이 문제에서 제한된 시간은 1초이며 테스트케이스는 100개이다. 제한된 시간 내에 효율적인 탐색 방법으로 풀어야 하는 문제이며 본문에서는 Astar Algorithm을 활용한 풀이를 기술한다. Astar Algorithm은 미래에 가망 있는 값 ..