오식랜드

양자 컴퓨터 양자 컴퓨터? “스팀펑크 샹드리에” 라고 불리는 외관 절대영도 (-273’c) 냉방 유지 필요 노이즈 위험으로 절대 안정 필요 양자 비트 (Qubit) 사용 리처드 파인만씨가 필요성 제시 Qubit (큐빗) 0 또는 1이 될 수 있는 상태 (일반 비트는 0 혹은 1의 상태) 연산이 빠르다 암호 해독이 빠르다 (소인수분해 / 이산대수) 기존 컴퓨터와의 비교 (슈퍼컴퓨터) 기존 컴퓨터 (슈퍼 컴퓨터) 양자 컴퓨터 비트 기반 디지털 기술 (0 or 1) 양자 기술 (Qubit) 현대 암호 체계 분석 불가 → 계산 능력 한계 초고속 대용량 연산을 통해 가능 → 동시 계산 처리 순서대로 반복적인 계산 3bit → 8회 양자 특성을 통해 동시 계산 3bit → 1회 612자리 정수 암호 해독 → 백만년..

다형성 다양한 형태가 존재한다는 의미 프로그램을 유연하게, 단순하게 만들어 준다 업 캐스팅 super class와 그 클래스를 상속받은 sub class 들이 있을 때, sub class를 super class형 참조변수로 저장 Object : 모든 class의 super class이므로, 모든 객체에 사용 가능 다만, super class에는 존재하지 않고, sub class에서 추가된 멤버는 사용이 불가능하다 SuperObject sub1 = new SubObject(); SuperObject sub2 = (SuperObject) (new SubObject); sub1.subClassMethod(); --> err! sub1.superClassMethod(); --> ok Object sub3 = n..

Single source shortest path 문제 (단일 출발점 최단 경로 문제) 질문 A에서 D까지의 경로가 있나? A에서 D까지의 경로가 하나 이상 있다면, 어느 경로가 최단인가? 경로의 길이: 경로에 있는 연결선의 가중치(weight)들의 합 소스(source): 경로에서의 첫 시작 노드(vertex) ⇒ S라고 한다 도착점(destination): 경로에서의 마지막 노드 Dijkstra 알고리즘 방향 그래프 : G=(V, E) 가중치 함수 (cost 함수) : W(e) 시작 노드 : S (Source) 방안 : 시작 노드 S를 기준으로, 다른 모든 노드로의 최단 거리를 구한다 (Greedy) ⇒ 어떠한 정점을 거쳐가는게 빠른지, S에서 직접 가는게 빠른지 비교가 필요하다 Dijkstra 과정..

그래프 용어 비방향성 그래프 : G=(V, E) V : 정점 vertex의 집합 E : 연결 선 edge의 집합 연결 그래프 두 정점 사이에도 경로가 존재하는 그래프 트리 (tree) 비순환적 비방향성 뿌리 있는 트리(rooted tree) 한 정점이 뿌리로 지정되어있는 트리 순환적 그래프 (cyclic graph) 비순환적 그래프 (acyclic graph) Spanning Tree (신장 트리) : G(V, E)가 비방향성 연결 그래프일 때, G의 부분 그래프인 T(V, E’)를 G의 spanning tree라고 한다 ⇒ T : tree, E’ : E의 부분집합 (E의 일부분) ⇒ 모든 정점을 포함하면서, cycle은 되지 않아 tree가 된 G의 부분 그래프 Minimum Spanning Tree ..

Huffman Code 암호처럼 한 문자를 2진수로 변환하여 사용하는 것 어떤 수도 다른 수의 접두어(prefix)가 아니어야 한다. 숫자는 가능한 짧은게 좋다. 특히 자주 사용하는 문자일수록 짧아야한다. 잘 만든 예시 접두어(frefix)로 겹치는 2진수가 없음 잘못된 예시 i의 10인지, n의 1010인지 알 수 없다. 과정 (Two-Way Optimal merge pattern 사용) 빈도 값 순으로 오름차순 정렬 정렬 된 리스트에서 가장 작은 두 값을 합함 (Greedy) 위의 두 값 대신, 새 값(두 값의 합)을 리스트에 포함 후 비교 위 과정을 반복함 1단계 ) 가장 작은 값 10과 10 병합 2단계 ) 가장 작은 값 15와 20 병합 3단계 ) 가장 작은 값 20과 20 병합 4단계) 가장 ..

문제 2개 이상의 정렬된 파일들을 하나의 파일로 합병한다. 이 때 비교 횟수를 최소로 한다. ⇒ 비교 횟수 최소 : Greedy 방식 해결 방안 찾기 앞에서 부터, 혹은 뒤에서 부터의 방식은 무조건 맞지 않다. 그 때, 그 때 원소의 갯수를 비교하여 가장 적은 원소를 가진 배열을 합친다 (Greedy) 예시 ) x1 ~ x4 : 길이가 다른 배열들. 이미 정렬이 된 상태. ⇒ 배열의 원소 갯수가 작은 배열을 먼저 합병한다. 예제 배열을 원소의 크기대로 오름차순 정렬을 한다 원소가 제일 적은 배열끼리 합병을 진행한다 배열이 합쳐지며 길이가 달라졌을 때 새롭게 sort를 한 후 합병을 진행한다 예제 : 트리 모형 예제의 결과를 뒤집어 만들어진 트리 형태의 노드 합쳐진 배열의 원소 합을 모두 더하여도 되지만,..