안녕

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.09.24 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Assembly Language (컴퓨터의 언어 - 어셈블리어) [컴퓨터 구조] Assembly Language (컴퓨터의 언어 - 어셈블리어) 앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.09.23 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Introduction to Computre Architecture (컴퓨터 구조의 소개) [컴퓨터 구조] Introduction to Computer.. hi-guten-tag.tistory.com 1. Design Principle 1 : Simplicity favors regularity add ..

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.09.23 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Introduction to Computre Architecture (컴퓨터 구조의 소개) [컴퓨터 구조] Introduction to Computer Architecture (컴퓨터 구조의 소개) 0. 글을 쓰기에 앞서 해당 글은 경북대학교 컴퓨터학부 수업인 COMP0411-008 컴퓨터 구조의 수업을 들으면서 작성하는 내용입니다. 책은 [David Patterson, John Hennessy, ªComputer Organization and Design RI.. hi-guten-tag.tistory.com 1. Computer's Language 컴퓨터의 언어를 Inst..

0. 글을 쓰기에 앞서 해당 글은 경북대학교 컴퓨터학부 수업인 COMP0411-008 컴퓨터 구조의 수업을 들으면서 작성하는 내용입니다. 책은 [David Patterson, John Hennessy, ªComputer Organization and Design RISC-V Edition: The Hardware Software Interface,ª The Morgan Kaufmann] 을 보고 있습니다. 1. Introduction 컴퓨터는 지속적으로 발전하고 있고, 이런 컴퓨터의 발전은 이제 우리 삶 전반에 걸쳐 영향을 끼치고 있습니다. 대표적인 예시로 Computers in automobiles, Cell Phone, Human genome project, World Wide Web, Search ..

P = NP임을 증명하려면 NP에 속한 각각의 문제에 대해 문제를 풀 수 있는 다항 시간 알고리즘을 찾아야 합니다. 하지만 이 작업은 단순화할 수 있습니다. 즉, 많은 문제 중에서 하나만 다항 시간 알고리즘을 찾으면 됩니다. 하나만 다항 시간 알고리즘을 찾으면, 나머지 문제들도 마찬가지로 P에 속하게 되는 NP-Complete에 대해 알아보겠습니다. 우선 알아보기 전에 이론의 기초가 되는 CNF-Satisfiability에 대해 알아봐야 합니다. 그리고 마지막으로 지금까지 결정 문제에 대해서만 NP, P를 따졌는데, 이제는 최적화 문제까지 확장한 NP-Hard에 대해서도 알아보겠습니다. 1. CNF-Satisfiability CNF ~ 는 Conjunctive Normal Form의 약자로, 논리식 사이..

이전 글의 Halting Problem을 기억하시나요? 이처럼 진위 판별을 불가능한 문제가 있고, 진위 판별이 불가능한 문제가 있습니다. 간단하게 진위 판별 문제(결정 문제)로 NP를 제한하면 이론을 전개하기가 쉬워집니다. 우선 결정 문제를 한 번 알아봅시다. 1. Decision Problem 그러기 위해선 우선 지금까지 해온 모든 알고리즘들, Decision Problem과 Optimization Problem에 대해 생각해봐야 합니다. 최적화 문제란 답이 최적해라는 말입니다. 하지만 최적화 문제는 결정 문제로 만들 수 있습니다. 참고로 결정 문제는 yes or no 두 가지 정답만 내놓습니다. 예를 들어서, TSP 문제를 생각해봅시다. 우리는 최소 거리를 구하는 알고리즘을 구현했지만, 만약 특정 거..

새로운 알고리즘을 개발할 때, 이 알고리즘이 다루기 어렵다는 것은 무엇을 의미할까요? 현실에서 다루기 어렵다는 것은 취급하기 또는 작업하기 어렵다로 정의하지만, 컴퓨터 과학에서 다루기 어렵다는 것은 "해당 문제를 다항시간(Polynomial-time)에 풀 수 없다"를 의미합니다. 즉 알고리즘의 Worst Case W(n) = O(p(n)) 만족하는 다항식 p(n)이 없다는 뜻입니다. 다항 시간안에 풀 수 있는 알고리즘은 2n, 3n^3, n lg n등이 있습니다. n lg n은 n에 대한 다항식은 아니지만, n lg n < n^2에 의하여 다항시간 알고리즘으로 분류합니다. 따라서 컴퓨터 과학에서 문제가 다루가 힘들다는 것은 특정 알고리즘의 성질이 아니라 문제의 성질이 되어야 합니다. 사실 최악 시간 복..

https://www.acmicpc.net/problem/7450 7450번: Bin Packing The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The fir www.acmicpc.net 코드) def func() -> int: cnt = 0 # bin의 개수 l = 0 r = n - 1 # 뒤에서 찾아야함 w..

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.04.13 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 (Dynamic Programming) [알고리즘] 동적 계획법 (Dynamic Programming) 1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, D hi-guten-tag.tistory.com 2022.05.27 - [Computer Science/알고리즘] - [알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법) [알고리즘 - 이론] Branch-and-B..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWvzGUKKPVwDFASy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 반복문 쓸 필요도 없고, 그냥 점화식 세워서 문제 풀어버리면 된다. c++) #include using namespace std; int main() { unsigned long long int test, i; cin >> test; for (int j = 1; j > i; if (i == 1){ cout

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net from math import sqrt _ = int(input()) # 필요 없음 k = list(map(int, input().split())) # 자연수들 M = max(k) # 자연수의 최댓값 arr = list(i for i in range(M + 1)) # arr을 초기화 함 for i in range(2, int(sqrt(M)) + 1): # 2부터 M의 제곱근까지만 계산해도 됨 if ar..