Do blog

# ISA ISA는 하드웨어와 소프트웨어의 인터페이스라 할 수 있다. 명령어 집합(영어: instruction set) 또는 명령어 집합 구조(영어: Instruction set architecture, ISA)는 마이크로프로세서가 인식해서 기능을 이해하고 실행할 수 있는 기계어 명령어를 말한다. 마이크로프로세서마다 기계어 코드의 길이와 숫자 코드가 다르다. 명령어의 각 비트는 기능적으로 분할하여 의미를 부여하고 숫자화한다. 프로그램 개발자가 숫자로 프로그램하기가 불편하므로 기계어와 일대일로 문자화한 것이 어셈블리어이다. An ISA is defined as the design of a computer from the Programmer’s Perspective. This basically means t..

# Dijkstra 1. Prim Algorithm과 유사하다. https://thesulks.tistory.com/31 Prim ~ Dijkstra (BOJ1197 최소 스패닝 트리, BOJ1753 최단경로) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를.. thesulks.tistory.com # Bellman-Ford 1. 음수 사이클 (negative cycles) 음수 사이클은 |V|-1번 edge relaxation을 수행한 뒤 한 번 더 edge relaxation을 수행하여 확인할 수..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 최소 스패닝 트리의 가중치가 -2147483648보다 크거나 같고, 2147483647보다 작거나 같은 데 www.acmicpc.net #include #include #include #include using namespace std; int main() { i..

1. 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 www.acmicpc.net 2. Note gi가 주어졌을 때 가능한 gi에 가깝도록 게이트를 배정해야하고, 이를 위해 가까운 게이트를 탐색해야 한다는 것..

1. 문제 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다. www.acmicpc.net 2. Note 우선순위 큐에서 가장 작은 합성수를 뽑아서 주어진 소수들을 곱한 뒤 다시 큐에 넣는데, 왜 이 방식이 매 반복문마다 최소값을 보장할 수 있는지 이해하지 못했다. 다음에 다시 이해해보려고 한다.

https://stackoverflow.com/questions/26549140/breadth-first-search-time-complexity-analysis Breadth First Search time complexity analysis Time complexity to go over each adjacent edges of a vertex is say O(N), where N is number of adjacent edges. So for V number of vertices time complexity becomes O(V*N) = O(E), where E is the total ... stackoverflow.com

https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf/3332994#3332994 When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would..

https://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container Why is vector not a STL container? Item 18 of Scott Meyers's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library says to avoid vector as it's not an STL container and it doesn't rea... stackoverflow.com https://stackoverflow.com/questions/16738579/is-using-a-vector-of-boolean-..

14.5 Random Numbers 난수 생성기는 크게 두 부분으로 구성된다. - engine: 난수 또는 psuedo-난수의 시퀀스를 생성함 - distribution: 이러한 값을 어떤 범위 안의 수학적 분포로 매핑함 #include #include #include #include using namespace std; class Rand_int { public: Rand_int(int low = numeric_limits::min(), int high = numeric_limits::max()) : rd{}, rnd{rd()}, dist{low, high} {} int operator()() { return dist(rnd); } private: random_device rd; mt19937 rnd;..

https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time/19647659 What is pseudopolynomial time? How does it differ from polynomial time? What is pseudopolynomial time? How does it differ from polynomial time? Some algorithms that run in pseudopolynomial time have runtimes like O(nW) (for the 0/1 Knapsack Problem) or O(√n) (for... stackov..