본문 바로가기

CS study

 (17)
컴퓨터 구조 2강 (1) CH2. Instruction: Language of the computer Instruction Set Instruction: 컴퓨터 언어의 한 단어 Instruction set: 주어진 아키텍처에서 이해하는 명령의 어휘 컴퓨터 명령의 레퍼토리 많은 측면에서 공통점이 있지만 컴퓨터마다 명령어 세트가 다릅니다. MIPS Instruction Set 책 전체에서 예제로 사용 임베디드 코어 시장의 큰 점유율 소비자 가전, 네트워크/저장 장비, 카메라, 프린터 등의 애플리케이션 다른 유명한 명령어 세트: ARMv7, intel x86, ARMv8 Hardware Operation 규칙 1. 간단하게 하기 위해선 규칙적인 것이 좋다. Arithmetic operands은 항상 3개이다. 한 줄에 하나의 명령어만..
17. Hash Hash 해시(Hash) 란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정을 말한다. 즉 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수이다. 키(key): 매핑전 원래 데이터의 값 해시값(Hash Value): 매핑 후 데이터의 값, 해시코드, 해시섬, 체크섬 등이라고도 한다. 해싱(Hashing) : 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법 해시 테이블 키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. 키를 해시 함수(hash function) 로 계산하여 그 값을 배열의 인덱스로 사용한다. 즉, key 값을 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다. 정리하면 다음과..
P-NP problem P-NP problem P-NP문제를 이해하기 위해 차근차근 기초지식부터 공부해보자. 알고리즘과 시간 복잡도 컴퓨터를 사용하여 특정한 계산 문제를 풀기 위해서는, 바로 그 문제에 해당되는 알고리즘을 컴퓨터에게 알려주어야 한다. 그리고 컴퓨터공학자들의 주된 관심사는 그 알고리즘이 문제를 얼마나 빨리 해결할 수 있느냐는 것이다. 시간복잡도 점근적 표기법은 아래와 같다. (Worst case) $ O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(N^3) < O(2^N) < O(N!) $ 다들 알다시피 어떤 문제를 해결함에 있어 입력의 크기가 N개 일 때, 연산을 해야하는 대략적인 횟수를 가리키는 것이 시간복잡도의 O 표현이다. 컴퓨터에게 쉬운 문제와 어려운 문제를 나..
Halting Problem (정지 문제) Halting Problem 정지 문제는 "주어진 프로그램이 해결하고자 하는 문제를 해결하는지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다. 이 문제 자체가 이해가 안되는 사람들을 위해 쉽게 설명한 영상을 가져왔다. https://www.youtube.com/watch?v=92WHN-pAFCs 위의 영상에서 정지문제 자체에 대한 설명과 귀류증명과정을 정말 알기 쉽게 설명했다. 꼭 한번 보는 것을 추천한다. 정지 문제란? (쉬운 설명) 산술식을 받아서 결과값을 출력하는 기계 A가 있다고 가정해보자. 이 기계 A는 항상 옳은 답을 출력한다. 또 체스를 두는 기계 C가 있다고 가정해보자. 이 기계는 현재의 체스판 상태를 입력을 받아서 다음 수를 출력한다. 이 기계 C는 체스를 너무 잘해서 ..
16. 그래프 탐색 (2) - DFS DFS (Depth-First Search) 개요 설계 모델 BFS와 같이 색깔로 정점의 상태를 구별해 보자. White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다. Gray: discover는 되었지만 정점에 대해서 탐색이 끝나지 않은 상태 = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태 Black: discover되고 해당 정점에 대해 모든 탐색이 끝난 상태 = Black 정점의 인접 정점들은 모두 Gray 혹은 Black 상태일 것이다. DFS에서 Gray 정점은 약간 BFS와 다른데, 각 Gray 정점에서 2개의 타임스탬프를 가진다. d[v]: 정점 v의 discovery time f[v]: 정점 v의 finish time (방문할 수 있는..
15. 그래프 탐색 (1) - BFS 그래프 탐색 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 그래프 탐색은 크게 두가지 방법이 있다. BFS (Breadth-First Search, 너비우선탐색) 개요 한 시작 정점을 정해서 인접한 정점부터 모두 탐색하는 방식이다. 설계 모델 정의 Discover: 정점을 처음 방문한다. Explore: 간선을 처음 이용한다. 정점의 구분 White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다. Gray: discover는 되었지만 정점에 대해서 Explore가 끝나지 않은 상태 = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태 Black: discover되고 해당 정점에 대해 모든 Explore가 끝난 상태 ..
14. Graph Basics Graph 그래프란? 정점(V, vertex)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조 = 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 용어 정점(Vertex, V): 꼭짓점 (node라고도 부름) ex) 위 그래프에서 정점은 총 7개 0,1,2,3,4,5,6 이 있다. 간선(Edge, E): 꼭짓점 간의 관계, 꼭짓점을 연결하는 선 (link, branch라고도 부름) ex) 위 그래프에선 간선이 총 6개 [(0-1) ,(1-2), (1-3), (2-5), (2-6), (3-4)] 있다. 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점 ex) 위 그래프에선 정점 1의 인접 정점은 정점 0, 2, 3이 있다. 정점의 차수(degree)..
11. AVL tree AVL tree 모든 BST 연산은 $ O(d) $ (d는 트리의 높이) 이다. $ d = \lfloor \log_2 N \rfloor $ (N은 트리의 총 노드 갯수) best case: $ O(\log N) $ worst case: $ O(N) $ 여기서 차이가 나는 이유는 트리의 균형의 문제이다. BST의 균형을 맞추기 위해 고안된 알고리즘이 많다. AVL tree: Adelson-Velskii and Landis (AVL) trees (height-balanced trees) Weight-balanced trees Red-black trees Splay trees and other self-adjusting trees B-trees and other (e.g. 2-4 trees) multiway ..

티스토리툴바