분류 전체보기 (49) 썸네일형 리스트형 컴퓨터 구조 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개이다. 한 줄에 하나의 명령어만.. DFS 심화 (1) - Bipartite (이분 그래프) 이분그래프 (Bipartite) 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 설계: Two-colorability i. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다. ii. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다. iii. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다. 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다. 시간복잡도: $ O(V + E) $ 코드 #include #include #include using namespace std; int V, E; vector adj_list[100]; int colored[1000],.. 17. Hash Hash 해시(Hash) 란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정을 말한다. 즉 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수이다. 키(key): 매핑전 원래 데이터의 값 해시값(Hash Value): 매핑 후 데이터의 값, 해시코드, 해시섬, 체크섬 등이라고도 한다. 해싱(Hashing) : 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법 해시 테이블 키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. 키를 해시 함수(hash function) 로 계산하여 그 값을 배열의 인덱스로 사용한다. 즉, key 값을 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다. 정리하면 다음과.. [STL] hash_map, unordered_map [STL] Hash map, Unordered_map hash_map의 자료구조 hash_map의 자료구조는 해시 테이블입니다. 해시 테이블에 자료를 저장할 떄는 key 값을 해시 함수에 대입하여 버킷번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장합니다. 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정합니다. 하지만 이 헤더파일은 STL 표준이 아니므로 사용이 불가한 환경이 있다. 내 맥북에선 컴파일이 안된다.. 대안은 비슷한 unordered_map을 써주면 된다. hash_map을 사용하는 경우 많은 자료를 저장하고, 검색 속도가 빨라야 한다. 빈번하게 자료를 삽입, 삭제 하지 않는다. Unordered_map 사용방법 #include using namespace std; unordered.. Binary Search (이분 탐색) Binary Search (이분 탐색) 설계 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 동작 정렬된 배열에서 이진 탐색(Binary Search) 알고리즘을 사용해 보자 13을 찾는다고 경우를 보자 i. 데이터 집합의 중앙값를 선택한다. ii. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 찾으려는 값(13) < 중앙값(9) 이면, 중앙값(9)의 왼편에서 중.. 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 표현이다. 컴퓨터에게 쉬운 문제와 어려운 문제를 나.. 나머지 연산 (Modulo Operation) Expression n | a: a는 n의 배수이다. a mod n: a를 n으로 나누었을 때 나머지 값 $ a \equiv b\ mod\ n $ : a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다, 모듈로 합동) $a \equiv b\ mod\ n $ 이면, a - b는 n의 배수이다. -> $ (a - b)\ mod\ n = 0 $ 나머지 연산 법칙 I. 덧셈 (A+B) % M = ((A % M) + (B % M)) % M II. 뺄셈 (A-B) % M = ((A % M) - (B % M) + M) % M 증명 $ 0 \leq A\%M < M $ $ 0 \leq B\%M < M $ 이므로, $ -M < (A\%M - B\%M) < 2M $ 이다. 따라서 양쪽에 M을 곱해줘야 0.. Halting Problem (정지 문제) Halting Problem 정지 문제는 "주어진 프로그램이 해결하고자 하는 문제를 해결하는지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다. 이 문제 자체가 이해가 안되는 사람들을 위해 쉽게 설명한 영상을 가져왔다. https://www.youtube.com/watch?v=92WHN-pAFCs 위의 영상에서 정지문제 자체에 대한 설명과 귀류증명과정을 정말 알기 쉽게 설명했다. 꼭 한번 보는 것을 추천한다. 정지 문제란? (쉬운 설명) 산술식을 받아서 결과값을 출력하는 기계 A가 있다고 가정해보자. 이 기계 A는 항상 옳은 답을 출력한다. 또 체스를 두는 기계 C가 있다고 가정해보자. 이 기계는 현재의 체스판 상태를 입력을 받아서 다음 수를 출력한다. 이 기계 C는 체스를 너무 잘해서 .. 이전 1 2 3 4 ··· 7 다음