개발일지

문제설명 입출력 예제 개념 이 문제는 각 숫자를 입력받을 때마다 중간값을 계산하고 출력하는 것이다. 단순하게 배열에 값을 추가하고, 매 반복마다 중앙값을 출력하려면 시간 복잡도가 O(N^2)이 되어 시간 초과가 발생할 수 있다. 이를 해결하기 위한 최적화된 알고리즘이 두 힙 알고리즘이다. 두 힙 알고리즘은 최대 힙과 최소 힙을 이용한다. 이 방식에서는 현재까지 입력받은 수 중 중간값 이하의 수를 최대 힙에, 중간값 초과의 수를 최소 힙에 저장한다. 따라서 중간값은 항상 최대 힙의 루트에 위치하게 된다. 이 알고리즘의 각 연산은 로그 시간 복잡도를 가지므로, 전체 시간 복잡도는 입력의 개수에 비례하는 선형 로그 시간 복잡도 O(N logN)를 가지게 된다. 이렇게 해서 큰 입력에 대해서도 효율적으로 문제를..

문제 설명 제한 사항 및 입출력 예제 개념 최소 공배수의 개념을 유클리드 호제법을 이용하여 구하는 문제다. 백준 최소 공배수 문제의 연장선으로서, 주어진 벡터의 모든 원소를 순회하며 최소 공배수를 구하면 된다. 풀이 (1) 유클리드 호제법 구현 #include using namespace std; int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y); } int lcm(int x, int y) { return x * y / gcd(x, y); } int solution(vector v) { int answer = 1; for (int i = 0; i < v.size(); ++i) answer = lcm(answer, v[i]); retur..

병렬 처리 기법과 ISA 병렬 처리 기법 이전 포스팅에서 CPU 성능을 향상하기 위한 몇 가지 기본 전략을 논의했었다. 클럭 속도를 높이는 것, 멀티코어나 멀티스레드를 지원하는 아키텍처를 사용하는 것 등이 그 예다. 그러나 CPU 성능 향상은 단순히 이러한 방법에만 의존하는 것이 아니라, 효율적인 작동 방식도 중요하게 고려해야 한다. 이번 게시글에서는 명령어 병렬 처리 기법에 초점을 맞추어 설명해 보겠다. 명령어 병렬 처리 기법(Instructuin-level parallelism)이란 여러 명령어를 동시에 처리함으로써 CPU가 휴식 없이 지속적으로 작동하게 하는 방법을 의미한다. 명령어 파이프라이닝, 슈퍼스칼라, 그리고 비순차적 명령어 처리 등이 이 기법의 대표적인 예시다. 명령어 파이프라이닝 명령어 ..

코어와 스레드 클럭 이번 시간에는 CPU 성능 향상에 대한 다양한 전략들을 알아보도록 하자. 우선 클럭에 대해 알아보자. 클럭은 CPU의 작동 원리를 다룰 때 클럭에 대해 잠깐 설명했었다. 컴퓨터의 여러 부품들은 클럭 신호에 의존하여 동작한다. 이 신호는 CPU의 명령어 사이클, 즉 명령어를 처리하는 순서와 속도를 제어한다. 클럭의 단위는 헤르츠(Hz)이며, 이는 1초 동안 클럭이 반복되는 횟수를 나타낸다. 따라서 클럭의 속도가 높아질수록 CPU는 명령어 사이클을 더 빠르게 수행하게 되며, 이는 다른 부품들이 더 빠르게 작동하도록 한다. 그렇다면 클럭 속도를 무작정 높이면 CPU가 빨라질까? 이에 대한 답은 '부분적으로 빨라진다'이다. 클럭 속도를 강제로 증가시키는 오버클럭킹(Overclocking) 기..

문제 설명 제한 사항 및 입출력 예제 개념 다음 그림처럼 토너먼트 브라켓 구조를 띄고 있는 대회에서 A참가자와 B참가자가 무조건 이긴다는 가정 하에 몇 번째 라운드에서 만날지 예측하는 문제다. 배열을 갱신하며 두 특정 참가자가 만나는 시점까지 반복하는 방법과, 두 참가자의 위치를 업데이트하고, 이들이 같아질 때까지 라운드를 증가시키는 방법이 존재한다. 풀이 (1) 배열 갱신 #include using namespace std; int solution(int n, int a, int b) { int cnt = 1; vector v(n, 0), tmp; v[a - 1] = true; v[b - 1] = true; for (int i = 0; i < n; i += 2) { if (v[i] && v[i + 1]..

문제설명 입출력 예제 개념 최소 비용을 통해 목표를 달성하는 그리드 알고리즘을 활용하는 문제다. 이 문제의 핵심 아이디어는 가장 낮은 기름값을 갖는 주유소를 찾아, 그곳에서 기름을 충전하는 것이다. 따라서 현재 위치에서 다음 도시로 이동하기 위해 필요한 기름을 충전하는데, 현재 주유소의 기름 가격과 다음 주유소의 기름 가격을 비교하여 최소 비용을 항상 유지하게 기름값을 갱신하면 된다. 풀이 #include #include using namespace std; int main() { long long N; cin >> N; vector station(N), road(N-1); for (int i = 0; i > road[i]; for (int i = 0; i < N; ++..

명령어 사이클과 인터럽트 명령어 사이클 명령어 사이클(Instruction cycle)은 기본적으로 CPU가 프로그램을 실행하는 기본 단위다. 각 사이클은 명령어를 가져오거나, 해독하거나, 실행, 그리고 메모리에 결과를 저장하는 과정을 포함하고 있다. 다음 과정은 CPU의 기본 작업 흐름을 설명하는 것으로, 각 CPU와 명령어 집합마다 다소 차이가 있을 수 있지만, 큰 뼈대는 같다고 봐도 무방하다. 인출 사이클(Fetch cycle): CPU가 프로그램 카운터가 가리키는 메모리 주소에서 명령어를 가져온다. 프로그램 카운터는 그다음에 실행될 명령어의 메모리 주소를 저장한다. 디코딩 사이클(Decoding cycle): 인출된 명령어를 이해하고 실행할 수 있도록 해독한다.이 단계에서 CPU는 명령어가 무엇인..

문제설명 입출력 예제 개념 각 사람이 돈을 인출하는 데 필요한 시간 합의 최솟값을 출력하는 문제다. 대표적인 그리디 알고리즘으로 효율적으로 해결할 수 있는 문제로서, 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 최단 작업 우선 스케줄링 방식을 이용하면 된다. 여기서 돈을 인출하는데 걸리는 시간을 작업으로 보고, 이 작업들을 가장 짧은 것부터 처리하면 모든 사람이 돈을 인출하는데 필요한 최소 시간을 구할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N; cin >> N; vector v(N); int* sum = new int[N]; for (int i = 0; i > v[i]; s..

CPU의 구성 요소 개요 컴퓨터의 뇌라고 할 수 있는 중앙처리장치(Central Processing Unit, CPU)는 주 기억장치인 메모리에서 명령어를 읽어 들이고 이를 해석하여 수행하는 작업을 맡는다. CPU의 주요 구성 요소로는 산술 및 논리 연산을 수행하는 ALU(Arithmetic Logic), 명령어의 순서와 수행을 제어하는 제어 유닛(Control Unit), 그리고 중간 결과와 작업 상태를 저장하는 레지스터(Register)가 있다. 이번 포스팅에서는 이러한 구성 요소들에 대해 공부해 보도록 하자. ALU ALU는 CPU의 핵심 요소로서 다양한 산술 및 논리 연산을 처리한다. 산술 연산은 덧셈, 뺄셈, 곱셈, 나눗셈 등을 포함하며, 논리 연산은 AND, OR, NOT 등의 비트 수준 연산..

문제설명 입출력 예제 개념 이 문제는 회의 시간이 겹치지 않도록 하면서 동시에 가능한 한 많은 수의 회의를 배정하는 문제다. 이를 해결하는 방법 중 하나는 먼저 회의들을 종료 시간 기준으로 오름차순 정렬하는 것이다. 그리고, 가장 먼저 끝나는 회의를 선택한 후, 이전에 선택한 회의와 시간이 겹치지 않는 회의 중 가장 빨리 끝나는 회의를 다음으로 선택하는 것이다. 이러한 방식을 반복함으로써 가능한 많은 수의 회의를 배정할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N, n, k, count = 1; cin >> N; vector v(N); 회의의 수 N, 그리고 회의의 시작과 끝에 대한 입력을 초기화할 변수 n, k,..