랄뚜기의 코딩일기

CPI CPI는 말 그대로 한 Instruction을 읽을 때 돌아야 하는 Cycle의 수이다. 다른 종류의 Instruction마다 필요한 Cycle의 수는 일정하지 않고 다르다. 예를 들어 Add $1,$2,$3은 1개의 Cycle이 필요하다면, beg $1,$2, 100은 2개의 Cycle이 필요할 수 있다. 따라서 CPU Time을 나타날 때 사용되는 Clock Cycles와 CPI의 엄밀한 정의는 다음과 같다. 즉, CPU Time을 표현할 때 쓰는 CPI는 Avg.CPI라고 이해하는 것이 좋다. 예시를 통해 더 자세히 알아보자. Class A의 instruction을 읽을 때는 1개의 Cycle, Class B는 2개, Class C는 3개의 Cycle이 필요하다는 것이다. ( 한 개의 ins..

Relation Relation은 DB에서 Table(표)과 같은 의미로 쓰인다. Relation schema는 Relation을 속성과 속성들의 도메인을 나타낸다. R = (A1,A2,...,An) 로 표현한다. 위는 Instructor Relation의 예시이다. Instructor Relation schema 는 Instructor = { ID, name, dept_name, salary } 이다. Relation를 구성하는 tuple은 정렬되어있지 않다 Database는 Data가 추가되거나 제거되기 때문에 그 상태가 계속 변한다. 이런 Database의 한 순간을 Database instance라고 한다. (Database instance는 변하지 않는다.) Key Key는 Relation에서 ..

문제 Madoka's father just reached 1 million subscribers on Mathub! So the website decided to send him a personalized award — The Mathhub's Bit Button! The Bit Button is a rectangular table with n rows and 𝑚m columns with 0 or 1 in each cell. After exploring the table Madoka found out that: A subrectangle A is contained in a subrectangle B if there's no cell contained in A but not contained in B. T..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 입력 첫째 ..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째..

Processes Process는 program이 메모리에 올라가 CPU가 접근 할 수 있는 상태를 의미한다. Program이라고 하면 안되고 Processor이라고도 하면 안된다. (Processor는 CPU이다.) Process는 두 가지 추상적인 개념을 program에 부여한다. Logical control flow 각각의 프로그램이 CPU를 독점적으로 사용는 것으로 착각한다. OS가 context switch를 해주기 때문에 가능하다. Private address space 각각의 프로그램이 메인 메모리를 독점적으로 사용하는 것으로 착각한다. OS가 virtual memory를 제공해주기 때문에 가능하다. Logical control flow와 Private address space 때문에 CPU..

Relative Performance Performance는 1/execution time으로 정의할 수 있다. 그렇다면 "X는 Y보다 n배 빠르다"를 어떻게 표현할 수 있을까? 위 표현은 x의 performance / y의 performance로 나타낼 수 있고 performance는 excution time의 역수이므로 위와 같이 나타낼 수 있다. 예를 들어 A의 execution time은 10s B의 execution은 15s라면 A는 B보다 15/10=1.5배 빠르다고 할 수 있다. 실행시간(Execution time)은 Elapsed time과 CPU time으로 나눌 수 있다. Elapsed time은 시스템이 프로그램을 처리하는데 드는 총 시간을 의미한다.( Processing, I/O, ..

Control Flow Processor는 한 번에 한 가지 일만 처리할 수 있다. 실행되었을 때부터 종료될 때까지 CPU는 그저 instruction들을 순서대로 읽을 뿐인데 이 순서를 Control Flow라고 한다. 항상 instruction을 순서대로 읽으면 좋겠지만 당연하게도 정해진 순서를 바꿔야 하는 경우가 발생하게 된다. Program state에서 Jumps, branches, call, return 등을 사용하여 프로그래머가 의도적으로 이 control flow를 바꿀 수 있다. 하지만 data가 disk나 network adapter에서 오는 경우, divides by zero가 발생하는 경우, 사용자가 Ctrl-C를 누르는 경우, System에 할당된 시간이 다 된 경우 등 Syste..