운영체제에서 꼭 다루는 Page Replacement Algorithm 입니다. (PRA라고 줄여 부르겠습니다) 저희는 컴퓨터의 저장공간에 프로그램을 설치해두고, 이를 더블클릭하여 실행합니다.그렇게 실행된 프로그램은 프로세스가 되어 메모리 위해 올라가면서 실행되는 원리입니다. 이때 프로세스는 한 묶음으로 반드시 통채로 올라가는 것이 아니라, 분리된 채로 쪼개져서 메모리 위에 올라갑니다.그리고 그 분리되는 단위를 페이지라고 이해하면 됩니다. 하지만 메모리의 용량은 제한적이기 때문에, 무한개의 프로세스를 만들 수는 없습니다.따라서 프로세스의 특정 페이지는 회수(즉 메모리에서 해제)되어야만 메모리의 빈 공간이 생기고 그 곳에 새로운 페이지를 올릴 수 있게 됩니다. 이렇게 페이지를 회수하고 올리는 교체 과정을 ..

라인스위핑(line sweeping)빗자루 쓸 듯 하나의 라인을 탐색하는 알고리즘입니다. 보통 집합이나 교차점과 같은 기하 문제를 풀 때 사용되곤 하지만, 코딩테스트에서는 그 정도의 난이도로는 나오지 않습니다.따라서 보통 최대 구간, 횟수 등을 찾는데 많이 쓰이는 알고리즘입니다. 예제 문제철수는 도화지 위에 여러 번 선을 긋습니다.한 선은 두 점 (a, b)로 표현됩니다.여러 선이 겹쳐 그려지더라도, 겹친 구간은 한 번만 계산해야 합니다.즉, 모든 선분을 합쳤을 때 총 길이를 구하는 문제입니다. 입력 조건첫 줄: 선의 개수 N (1 ≤ N ≤ 1,000,000)이후 N개의 줄: 두 정수 a, b (-1,000,000,000 ≤ a ≤ b ≤ 1,000,000,000)출력 조건겹치지 않게 계산한 선분의 총..

그리디 알고리즘은 지역적 최적해들을 찾아서 전역적 최적해를 구하는 방식입니다.즉, 그 순간에 '탐욕적으로' 최선이라 생각하는 선택지들을 골라, 최종적으로 최선인 정답을 도출해내는 방법이죠. 참고로, 보통 문제 풀이에서 다음의 과정을 거치곤 합니다.무식하게 풀기 -> DP -> 그리디 즉 보통 그리디는 최후의 최후에 사용하곤 합니다.또한, DP로 풀이할 수 있는 것들은 대부분 그리디로도 풀이할 수 있긴 합니다.오직 그리디로만 풀리는 문제는 DP의 메모이제이션 용량이 너~무 커서 DP를 사용할 수 없는 경우입니다. 그리디가 성립하기 위한 조건1. 최적 부분 구조전체 문제를 작은 부분 문제로 나눌 수 있어야하며, 그 작은 부분 문제의 최적해들을 모아 전체 문제의 최적해를 이룰 수 있는 구조를 의미합니다.2...

정렬 비교 함수는 어렵지 않지만, 특별한 원리가 보이진 않습니다. "그냥 그렇게 설계됐다 - 라고 받아들여져서요"이해의 필요성이 떨어지니, 조금만 사용하지 않더라도 이내 헷갈리고 빠르게 디버깅하며 코드를 작성하게 되더라고요.그래서 관계성에 더 집중해서 기억해보고자 합니다. 물론 더 정확히 판단하려면, C++, JS의 sort 함수에서 사용하고 있는 정렬 알고리즘을 면밀히 파악해야합니다.C++ : IntroSort (불안정 정렬, QuickSort+HeapSort+Insertion Sort)JS: TimSort (안정 정렬), 작은 배열에는 Insertion Sort불안정 정렬은, 중복된 값이 있을 때 입력된 순서가 유지되지 않을 수도 있는 정렬을 의미합니다.를 사용하는데, 이 알고리즘 파악이 해당 아티클..

Bit란 Binary digit 의 약어입니다. 즉, 이진수라는 뜻입니다.컴퓨터는 이진수만 이해할 수 있습니다. 그리고 컴퓨터의 값의 최소 단위는 bit입니다. (메모리는 1byte = 8bit입니다.)따라서 비트 마스킹이란, 이런 bit를 끄거나 켜는 것을 의미합니다. (0: 끔, 1 : 켬) 비트마스킹을 배워야하는 이유는 무엇일까요?비트마스킹은 불리언 배열을 하나의 숫자로 대체할 수 있기 때문입니다. 예를 들어 [1, 0, 1, 0] 이라는 bool 배열이 있다면, 이는 1010(이진수, 10이라는 값)로 나타낼 수 있습니다. 이렇게 이진수로 나타낸 값에 비트 연산자를 적절히 활용하면, 다양한 기능을 쉽고 간편하게 구현할 수 있게 됩니다. 비트 연산자& (and)and 연산자, 두 비트 전부 1..

컴퓨터공학을 배우게 된다면 2진법, 10진법 혹은 1의 보수, 2의 보수와 같은 개념을 접하게 됩니다.오늘은 이 진법과 보수에 대해 튼튼히 개념을 쌓아보고자 합니다.숫자숫자는 '개수'를 세기 위한 아이디어에서 시작되었습니다. 그러다가 없는 것을 표현하는 0, 손실을 의미하는 - 같은 개념들도 추가되기 시작했죠. 진법 (= 기수, radix)진법은 한 자리에 몇가지 종류의 값이 들어갈 수 있는지를 의미합니다.2진법은 한 자리에 2가지 종류의 값이 들어갈 수 있고, 10진법은 한 자리에 10가지 종류의 값이 들어갈 수 있습니다. 예를 들어 10진법에서 138(백삼십팔)이라는 숫자를 예시로 들어보겠습니다. 138은 총 3자리로 이루어져 있으며, 각 자리는 다음과 같이 구성됩니다. [1][3][8] 이때 [ ]..

모듈러 연산 (나머지 연산)은 알고리즘에서 자주 쓰이는 개념입니다.모듈러 연산은 정수론에서 나온 개념이라 깊게 이해하려면 정수론을 조금 들여봐야하나, 지금의 저는 수학자가 아니에요. 간단하게 개념들만 알아봅시다.모듈러 연산(%) 이란?나머지를 구하는 연산.10 % 3 == 1 -> 10을 3으로 나누었을 때의 나머지, 즉 14 % 2 == 0 -> 4를 2로 나누었을 때의 나머지, 즉 0 혹은 %를 mod 라고 표현하기도 합니다.10 mod 3 == 14 mod 2 == 0 모듈러 연산의 합동 법칙 (Modular congruent)어떤 두 정수 a, b가 모듈러 m에 대해 합동이라면, 아래와 같이 나타낼 수 있습니다.a ≡ b (mod m) 이를 더 풀어서 설명하면, 결국 모듈러 연산에서 합동이란 같은..

완전 탐색 (brute force, exhausitive key search)완전 탐색은 모든 경우의 수를 탐색하는 알고리즘입니다. (즉, 노가다)경우의 수란? 순열 또는 조합을 의미합니다.그래서 완전 탐색은 보통 조합/순열 + 로직(DFS/BFS) 로 이루어져 있습니다.  그럼 언제, 완전탐색을 사용해도 될까요? 아주 명확하고 간단하게 정리하면 다음과 같습니다.시간복잡도가 1억 미만일 때! 즉, 대략 총 계산 횟수가 1억 미만이면 완전탐색으로 풀면 됩니다. (대부분 시간 제한이 1초이므로)그러나 1억 이상인 경우에는? 다른 방법이 떠오르지 않으면 완전 탐색을 사용하긴 하되, 의심하긴 해야합니다.   완전탐색의 구현 방법 2가지 (반복문 vs 재귀함수)만약 2가지 방법 모두로 풀 수 있다면, 무조건 반복..

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적이 방법으로 방문하는 과정을 트리 순회라고 합니다.일단 설명을 위해, 공통적으로 사용할 하나의 예시 그림을 제시하겠습니다.  후위 순회 (postorder traversal)자식 노드들을 먼저 방문하고, 본인 노드를 방문하는 방식입니다. (자식 노드들은 보통 왼쪽 -> 오른쪽 순서)//pseudo codepostorder( node ) if (node.visited == false) postorder( node->left ) postorder( node->right ) node.visited = true  직접 코드로 구현해보겠습니다. void postOrder(int here){ if(visited[he..