본문 바로가기

📚 전공 공부

(55)

[블록체인] 1. 블록체인 개요 : Blockchain Overview 목차 : 암호화폐와 비트코인의 등장 / 블록체인 개요 / 블록체인 용어 정리 암호화폐와 비트코인의 등장 암호화폐의 역사 - 사이퍼 펑크의 등장 (Cypher Punk) 암호+punk의 합성어 개인의 자유와 사생활 보호를 위해 암호화된 체계 구축을 주장하는 단체 중앙집권화된 정부나 기관이 개인 프라이버시를 보장하지 못하니, 스스로 프라이버시를 보호하고 열린 사회를 추구 1980년대부터 암호화폐는 사이퍼펑크를 중심으로 연구됨 - 1984 데이비드 차움의 Ecash & DigiCash 설립 : Blind Signature, 비밀키 공유기능 포함 - 1997 아담 백의 HashCash : 수학적 퍼즐 기반 - 1998 웨이 다이의 B-Money : 수학 퍼즐의 보상으로 암호화폐 지급, 경쟁적 채굴-신뢰성 확보의..

[문제해결기법] 7. 이분 탐색 1. 탐색 오름차순으로 정렬된 N개의 정수 배열 A[0], ..., A[N-1]이 있다. X가 주어졌을 때, A[i] = X라면 i를 리턴하는 함수 find(N, X)를 작성하시오. 이 함수는 내부적으로 compare(i, val)을 호출하는데, 이는 A[i]=val이면 0, A[i] val이면 -1을 리턴하는 함수이다. N은 최대 100이다. int find(int sub, int N, int X) { int start = 0, end = N-1, t; while (start 0) start = mid + 1; // 기준값보다 작으면 start를 당기기 else if (v) end = mid - 1; // 기준값보다 크면 end를 당기기 else return mid; }..

[문제해결기법] 6. 세그먼트 트리 1. Segment Tree 부분합 문제에서 응용 가능 생성 코드 2. 합을 구하는 코드 [start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다. (1) [start, end]와 [left, right]가 겹치지 않음 -> 할 일이 없다 (2) [start, end]가 [left, right]를 포함 -> 미리 구해둔 [left, right]의 합을 사용한다. (3) [start, end]를 [left, right]가 포함 -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다. (4) [start, end]가 [left, right..

[문제해결기법] 5. 욕심쟁이 기법 1. 욕심쟁이 알고리즘 : Greedy algorithm 매 단계마다 각 단계에서 최선의 선택을 한다. (현재 순간마다) 알고리즘이 매우 간단하나, 구한 답이 정답인지 검증이 필요하다. 기본 형태 2. 회의실 배정 문제 한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해서 시작 시간 Si와 끝 시간 Fi가 주어진다. 각 회의가 겹치지 않게 하면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하는 프로그램을 작성하시오. ❖ 입력 ➢ 첫 줄에는 회의의 수 n ➢ 둘째 줄부터 n+1줄까지 두 정수 Si와 Fi ❖ 출력 ➢ 잡은 회의를 차례대로 출력(둘 이상의 답이 있을 수 있음) 가능한 접근 방법 - 회의시간이 짧은 것 부터 넣는다 -> 반례 존재 - 다..

[문제해결기법] 4. 자료구조2 1. 트리 지름 트리의 두 정점 u, v의 거리의 최댓값 (1) O(n^3) : brute force (2) O(n^2) : u를 고정하고 bfs한다. (3) O(n) 트리에서 임의의 정점 x를 선택하고 x에서 가장 먼 정점 y를 찾는다.(bfs) 이후 y에서 가장 먼 정점 z를 찾는다. 그러면 y와 z가 가장 멀리 떨어져있는 정점 쌍이다. 증명 원하는 답이 두 정점 u와 v이다. 그렇다면 3가지 가능성이 있는데, x에서 가장 먼 점이 y라고 하면 (1) x = u / x = v (2) y = u / y = v (3) x,y,u,v 모두 다른 경우 (1)과 (2)는 위 알고리즘의 답이 맞다는 것이 자명하다. (3)의 경우는 u~y 경로와 u~v 경로가 거리가 같은 경우 이외에는 없어야 한다. x,y,u,..

[문제해결기법] 3. 자료구조1 1. RMQ : Range Minimum Query (범위 최소 쿼리) 배열의 부분배열에서 최솟값을 찾기 (1) O(n^3) 전처리, O(1) 질의 : brute force 방식으로 가능한 RMQ(a,b)에 대한 답을 모두 저장해놓는다. n^2칸을 채워야하고, 한 칸을 채울 때 최대 O(n)시간이 걸린다. (2) O(n^2) 전처리, O(1) 질의 : 가능한 RMQ(a,b)에 대한 답을 모두 저장하는데, RMQ(a,b+1) = min(RMQ(a,b) , A[b+1])을 사용하여 n^2칸을 각각 O(1)의 시간으로 채울 수 있다. (3) O(n) 전처리, O(sqrt(n)) 질의 : 배열을 sqrt(n) 묶음으로 나눈 후 각 묶음의 최솟값을 구하는데에 O(n)이 걸리며, RMQ(a,b)를 구하..

[문제해결기법] 2. 기초수학 1. 벡터의 외적 : cross product 2. 외적의 응용 : 부호 점검 3. CCW 알고리즘 : Counter-Clock Wise 세 점이 주어졌을 때 A->B와 A->C 두 벡터의 외적의 부호가 방향을 결정함. int ccw(int x1, int y1, int x2, int y2, int x3, int y3){ int tmp = x1*y2 + x2*y3 + x3*y1; tmp -= (y1*x2 + y2*x3 + y3*x1); if(tmp > 0) return 1; // a에 대해 b가 반시계 방향(왼쪽)에 있음 else if(tmp < 0) return -1; // a에 대해 b가 시계 방향(오른쪽)에 있음 else return 0; } 4. 응용 : 선분의 교차 여부 a-b를 이은 벡터 A에 ..

[문제해결기법] 1. C++ 1. 사용 언어 C : 가장 익숙하지만 지원 기능이 적음 C++ : STL에서 제공하는 기능을 활용 Java : java.util에 유용한 기능이 많다. 실행시간이 느려서 속도에서 제한을 받음 Python : 프로그래밍이 쉽지만, 실행시간이 가장 느리다. 2. 문제 해결 -> 기본적으로 자료구조, 알고리즘, 프로그래밍 능력을 묻는 문제 3. auto for(auto a : A){ ~ } 4. for : 반복문 5. pair 6. STL : standard template library made by HP in 1994 코드를 짧고 빠르게 작성할 수 있도록 도와줌. 7. template template const T& my_max(const T&x, const T&y){ return (y { 1, 3 } ..

이전 1 2 3 4 5 6 7 다음

티스토리툴바