본문 바로가기

분류 전체보기90

빠른 거듭제곱 알고리즘 (C#) 대부분의 언어에는 이미 거듭제곱 함수가 내장되어 있지만, 가끔씩 내가 직접 만들어야 하는 상황이 생긴다. 예를 들어 Mod 연산이 필요한 문제라든가... 그래도 구현이 어렵진 않기 때문에 한번 외워두면 두고두고 써먹을 수 있다. 거듭제곱의 계산은 (1)반복문 과 (2)재귀 로 구현할 수 있다. 각자 편한 방식을 택하자. (1) 반복문 여기서는 간단하게 느낌만 설명하겠다. 3^13을 예로 들어보자. 지수 13을 이진수로 바꿔서 생각하면, 우리는 3^13을 아래와 같이 표현할 수 있다. 지수법칙에 의해 3개의 항으로 나누어졌다. 반복문에서 행해지는 작업은 위 항들을 구하는 것이다. public static int pow(int a, int b) { int result = 1; while (b > 0) { i.. 2022. 8. 29.
정수의 각 자릿수를 다루는 방법 (C#) 정수 x의 각 자릿수를 순서대로 출력하는 코드는 아래와 같다. public static void Print(int x) { if (x / 10 > 0) Print(x / 10); Console.Write(x % 10); } 만약 거꾸로 1의 자리부터 출력하고 싶다면 재귀가 아닌 반복문으로도 충분하다. public static void PrintReverse(int x) { while (x > 0) { Console.Write(x % 10); x /= 10; } } 거꾸로 된 출력이 아니라 값을 원한다면 아래의 방법을 사용하면 된다. public static int Reverse(int x) { int result = 0; while (x > 0) { result = result * 10 + x % 10;.. 2022. 8. 28.
경쟁 상태(Race condition)의 간단한 예시 전역 변수 count = 5에 대하여 각각의 스레드가 count++, count--를 한 번씩 수행하도록 했다. 그렇다면 두 스레드가 모두 Join되었을 때 count는 5를 그대로 유지하고 있을까? ... 만약 그렇다고 생각했다면 아래의 설명을 읽어보자. count++는 Low level에서 아래와 같이 동작한다. 그래서 count++를 수행하는 도중에도, 드물긴 하지만 Preemptive 스케쥴러에 의해 Context switch가 발생할 수 있고 이는 count의 일관성을 해치는 결과를 낳는다. 아래는 그 과정이다. 스레드 1에서 count++를 수행하던 도중 Context switch가 발생한 경우다. 원래대로라면 스레드 2는 count = 6을 레지스터로 가져와 연산을 진행했어야 하는데, 문제는.. 2022. 8. 25.
FCFS, SJF, SRTF, RR의 계산 및 비교 *Waiting time, Turnaround time의 계산 및 비교입니다. Non-preemptive FCFS (First-Come, First-Served) 가장 간단한 스케쥴링 알고리즘 먼저 도착한 프로세스부터 차례대로 실행 도착 순서에 따라 결과가 달라질 수 있음 Total waiting time : 0 + 7 + 10 + 18 = 35 Avg. waiting time : 35 / 4 = 8.75 Total turnaround time : 8 + 11 + 19 + 23 = 61 Avg. turnaround time : 61 / 4 = 15.25 SJF (Shortest-Job-First) 가장 짧은 CPU Burst time을 가진 프로세스부터 실행 항상 최적의 결과를 도출하며, 이를 증명할 수.. 2022. 8. 23.
Context switch란 여러 프로세스들을 동시에 실행(하는 것처럼) 하기 위해 컴퓨터는 그 프로세스들을 번갈아가며 실행하게 되는데, 그 과정에서 일어나는 것이 Context switch이다. Context switch를 직역하면 문맥 교환이라는 뜻이 된다. 즉, Context switch는 프로세스의 문맥(context)인 PCB를 교환(switch)하는 작업이다. PCB의 교환은 Dispatcher에 의해 이루어지고, 아래의 과정을 거친다. 현재 실행중인 프로세스의 PCB를 저장하고, 다음 프로세스의 PCB를 불러온다. PCB에는 다음에 실행될 명령어의 주소(Program counter)를 비롯한 다양한 정보들이 포함되어 있기 때문에 이것을 기억해두지 않으면 다시 처음부터 실행해야 될 수도 있다... 그리고 이로 인한 딜레이.. 2022. 8. 19.
프로세스 상태 전이도 요약 1) new : 프로세스가 생성되고 있는 상태 2) ready : 프로세스가 프로세서에 할당될 수 있고, 할당되기를 기다리는 상태 3) running : 프로세스가 실행되고 있는 상태 4) waiting : 특정 이벤트(I/O 등)의 발생/완료를 기다리는 상태 *특정 이벤트가 선행되어야 CPU를 사용할 수 있다면, CPU는 이를 기다리지 않고 프로세스를 wait queue에 넣어버린다. 바로 ready queue에 넣는 것이 아니다. 넣어봐야 다시 running 상태가 되면 또 이벤트를 기다릴 것이 뻔하니... 5) terminated : 프로세스가 실행을 마친 상태 아래는 queueing이 이루어지는 과정을 묘사한 다이어그램이다. 2022. 8. 19.
멀티스레딩의 장점과 과제 멀티스레딩은 크게 4개의 장점을 가진다. 1. 응답성 (Responsiveness) 싱글스레드로 서버와 클라이언트 간의 통신을 처리하려고 하면 서버는 다수의 통신을 순차적으로 처리하게 된다. 그러나 멀티스레드로 처리한다면 아래 사진처럼 병렬로 처리할 수 있게 된다. 통신이 연결될 때마다 새로운 스레드를 생성하고, 그 스레드에서 통신을 처리하도록 한다. 그러면 뒷 순서의 클라이언트들도 기다릴 필요 없이 빠르게 응답을 받을 수 있다. 응답성이 의미하는 바는 이런 것이다. 2. 자원 공유 (Resource Sharing) 프로세스들 간의 자원 공유는 Shared memory나 Message passing으로 이루어 지는 반면, 스레드 간의 자원 공유는 비교적 간단하다. 위 사진처럼 스레드들은 스택을 제외한 나.. 2022. 8. 13.
매개 변수 탐색(parametric search, 파라메트릭 서치) 매개 변수 탐색은 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 해주는 기법이라고 한다. 최적화 문제란 말그대로 어떠한 함수값을 최적화시키는 변수를 찾는 문제, 그리고 결정 문제는 예-아니오의 형태로 답안이 나오는 문제를 말한다. 매개 변수 탐색의 기저는 이분 탐색인데, 이것을 결정 문제로 바꾼다고 해서 mid가 가리키는 값이 정답인지 바로 알 수 있는건 아니다. 다만 그 값이 정답이 될 수 있는지 정도는 바로 알 수 있다. 매개 변수 탐색은 그 결과를 이용해 탐색 범위를 좁혀가며 답을 찾는 기법이다. 마치 스무고개와도 같다. 문제를 통해 이해해보자. 아래 문제는 백준 단계별을 따라갔을 때 처음으로 만날 수 있는 매개 변수 탐색 문제이다. 문제에 대한 설명은 생략하겠다. 하지만 아래 풀이를 이해하기 위해.. 2022. 8. 9.

티스토리툴바