dh_0e

컴퓨터의 기원compute + er2차 세계대전 당시 OS가 없던 시절 전쟁과 함께 개발됨암호 해석미사일 탄도 분석물리 계산 1950년대 초반현재의 컴퓨터에 비해 매우 원시적임프로그램인 기계적인 스위치를 이용하여, 1bit 단위로 컴퓨터에 입력되어 실행진공관 기반의 거대한 크기, 많은 열 방출1950년대 중반모든 프로그램이 기계어로 쓰임플러그 보드(Plug-Board: 빵판)에 와이어링(Wiring)을 통해 컴퓨터의 기능을 제어프로그래밍 언어 및 운영체제라는 존재가 없음영구적인 저장장치가 없어 매번 프로그램을 다시 입력함1960년대 초반펀치카드가 등장하며 프로그래밍한 카드로 컴퓨터를 구동시킴빵판의 대체재가 됨 Mainframe - 일괄처리(Batch)Business Machinery로써 쓰이면서 가치가 ..

프로그램을 실행하면 일어나는 일프로세서(CPU)가 메모리에서 명령어를 fetch함fetch: CPU가 다음에 실행할 명령어를 메모리에서 가져오는(읽어오는) 과정을 의미해당 명령어가 무슨 의미를 가지는지 decode(해석)함명령어에 적혀있는 Opcode 및 Operands(피연산자)를 기반으로 execute(실행)함Opcode: 연산자 / 명령어가 실행할 연산의 종류ex) 데이터 전송(MOV, POP, ..), 산술 연산(ADD, SUB, ..), 논리/비트 연산(AND, OR, ...), 제어 흐름(JMP, JE, ..), etc.프로세서는 다음 명령어 (PC+4)로 이동하여 동일한 수행 반복다음 명령어가 PC+4인 이유: MIPS 아키텍처에서 사용하는 기준인 고정 길이 명령어 구조에선 한 개의 명령어는..

다리 만들기 2 (백준 17472번) 문제 발상이나 각 알고리즘의 난이도는 쉬운편인데 구현이 복잡해서 실수하기 쉬운 문제.풀이 과정dfs나 bfs로 섬들의 번호를 매긴다. (Flood Fill)바다를 찾아 상하좌우로 만들 수 있는 다리를 전부 만든다. (Brute-force)만들어진 다리로 크루스칼이나 프림 알고리즘을 사용하여 모든 섬을 연결하는 최소 다리 길이를 구한다. (MST)#include#include#includeusing namespace std;int n, m, isl = 1;int d[11][11], bridge[11][11];int vi[11];void dfs(int y, int x, int num){ d[y][x] = num; if (y - 1 >= 0 && d[y - 1][x] =..

발전소 (백준 1102번) 비트필드를 이용한 dp 문제로 n이 16 이하의 자연수이기 때문에 $O(2^{n}*n^{2})$으로 해도 최대 16,777,216이 나오기 때문에, 시간초과가 나오지 않는다. 풀이 과정 dp 점화식을 dp[i][j] = 'i개의 발전소가 작동할 때, 발전소 상태가 j인 경우 드는 최소 비용' 으로 잡는다. 이때, j에 들어가는 값은 비트필드로 각 비트는 n(n-1)(n-2)...54321와 같이 내림차순으로 n~1번 발전소의 고장 여부를 나타낸다.(n이 5라고 가정했을 때, j가 10110이면 5, 3, 2번 발전소가 켜져있다는 뜻) 초기 dp 배열은 -1로 초기화하고, 작동중인 발전소들을 나타내는 값(: bit)을 구해서 dp[작동중인 발전소 수(: cnt)][bit]를 0..

LCA와 쿼리 2 (백준 15480번) 어떤 트리의 root를 계속해서 바꾸면서 LCA를 구하는 쿼리를 해결하는 문제로, LCA를 최대 100,'000번 구성하도록 코드를 짜면 무조건적으로 시간초과가 나온다. 수학적 패턴이나 조건 분기들을 따져야 하는 문제 같아서 계속 고민해 봤지만 발상이 쉽지 않았다. 풀이 과정 LCA(r, a)와 LCA(r, b), LCA(a, b)의 값을 비교하여 답을 쉽게 도출할 수 있다.LCA(r, a)와 LCA(r, b)가 같다면 LCA(a, b)가 root를 r로 바꾼 트리의 최소 공통 조상이 된다.이 경우엔, a부터 b로의 경로 중에 r이 없다는 뜻으로 root를 r로 바꾸어도 LCA는 그대로 LCA(a, b)가 된다.그렇지 않다면, LCA(r, a)와 LCA(r, b) ..

트리와 쿼리 2 (백준 13511번) 최소 공통 조상(LCA) 문제로 희소 배열, Binary Lifting을 사용하여 LCA를 $O(logn)$만에 구해야 한다. 풀이 과정 문제 설계는 여타 LCA 문제를 구현하듯이 하되, parent 배열에 비용, 정점 번호를 함께 저장한 뒤, LCA 함수를 약간 수정하고 문제 형식에 맞게 출력하면 된다. LCA 함수를 만들 때, u, v 정점에서 최소 공통 조상까지의 거리를 각각 cost에 더해주면서 합을 구해주고, 최소 공통 조상의 정점 번호를 함께 pair로 반환해준다. 반환한 값을 바탕으로 (1 u v) 형식의 쿼리는 그냥 cost 값을 출력해주면 되며, (2 u v k) 형식의 쿼리는 약간의 작업이 필요하다. 최소 공통 조상까지의 정점 갯수를 각각 LCA_u..