CS

세그멘테이션(Segmentation)이란? 세그멘테이션 vs 페이징

세그멘테이션이란? 페이징은 프로세스를 물리적으로 일정한 크기로 나눠서 메모리에 할당하는 것을 의미한다. 반면, 세그멘테이션은 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치하는 것을 의미한다. 세그멘테이션은 프로세스를 세그먼트(segment)의 집합으로 표현한다. 이때 세그먼트는 논리 단위로 아래와 같은 것들이 해당된다. main program procedure function method object stack local variable global variable etc... 프로세스를 code영역, data영역, stack영역 등으로 나누는 것 또한 세그멘테이션이라고 할 수 있다. 세그멘테이션 계산 세그멘테이션도 페이징과 비슷하게 세그먼트 테이블을 가지고 있다. 페이징과 비슷하게 논리주소가 ..

SPFA (Shortest Path Faster Algorithm)

개념) 다익스트라 알고리즘은 O(ElogV)로 동작하며 (이론적으로는 O(E+VlogV) 음수 간선은 처리할 수 없다. 일반적으로 가장 많이 사용된다. 플로이드-와셜 알고리즘은 O(V3)으로 동작하며, 모든 정점들간의 거리를 모두 구한다는 특징이 있다. 음수 간선이 있어도 잘 동작하며 음수 사이클의 여부를 판단할 수 있다. 벨만-포드 알고리즘은 O(VE)이며 음수 간선이 있어도 잘 동작하고, 음수 사이클의 여부를 판단할 수 있다. 이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드 알고리즘의 성능을 향상시킨 것으로, 음수 간선이 있는 그래프에서 최단경로를 빠르게 구할 수 있다. 최악의 시간복잡도는 여전히 O(VE)이지만 실제로는 O(V+E) 정도로 동작한다. 벨만-포드 알고리즘에서는 ..

알고리즘 대회 (Competitive Programming)에서 애드혹(Ad-Hoc) 문제란?

일반적으로 경쟁적 프로그래밍(Competitive Programming) 대회, 이른바 알고리즘 대회에서는 종종 애드혹(ad-hoc) 문제가 출제된다. 일반적으로 애드혹 문제라고 하는 것은 해당 문제를 풀기 위해 잘 알려진 정교한(sophisticated) 알고리즘을 적용하지 않고 해결할 수 있는 유형의 문제를 일컫는다. 이러한 유형의 문제는 손으로 직접 해당 문제를 해결하기 위한 (해당 문제만을 위한) 아이디어를 찾아서 문제를 해결할 수 있다. 애드혹 문제들을 굳이 분류하자면 단순히 지시(instruction)를 따르면 되는 구현 유형이나 그리디 유형 알고리즘 혹은 수학 유형으로 분류할 수 있는 경우가 많다. 즉 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제라고 한다. 안경..

벨만 포드 (Bellman-Ford) 알고리즘

벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다. 따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 개념 다익스트라 알고리즘이 그리디 알고리즘이였다면, 벨만 포드 알고리즘의 기본 개념은 다이나믹 프로그래밍이다. 즉, 이전에 계산한 최단경로를 이용해 새로운 최단경로를 갱신하는 식으로 동작한다. 예를 들어 시작노드 s에서 v에 이르는 최단경로는 s에서 u까지의 최단경로에 u에서 v사이의 가중치(거리)를 더한 값이다. 위와 같은 그래프가 있다면, s에서 ..

DP(동적계획법)을 이용한 이항계수 (Binomial Coefficient)

이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dynamic progr..

최장 증가 부분 수열 (LIS)

개념 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로 몇 개의 숫자들을 뽑아서 부분수열을 만들 수 있다. 이렇게 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어 [5, 2, 1, 4, 3, 5] 라는 수열이 있다고 가정해보자. 해당 수열에서 최장 증가 부분 수열에 해당하는 수열은 무엇일까? 세번째에 있는 숫자 1을 꺼낸다. 다섯번째에 있는 숫자 3을 꺼낸다. 여섯번째에 있는 숫자 5를 꺼낸다. 이렇게 만들어진 수열 [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이 된다. 구할 수 있는 방법에는 크게 2가지가 있고 시간 복잡도에서..

[C++] STL container 시간 복잡도 및 특징 비교

※용어 설명※ amortized : 분할 상환하다는 뜻을 가지고 있는 이 단어는, 쉽게 설명하자면 최악의 경우는 더 높은 값의 시간 복잡도를 가질 수 있지만, 대체적으로는~ 으로 생각하면 될 것 같다. 점근적 분석(Asymptotic analysis)으로 보면 O(n)이 나오는 경우에, 분할상환분석(Amortized Analysis)으로 보면 O(1)이 나오는 경우도 있기 때문이다. ​ red-black tree: 레드블랙트리. Balanced Binary-Search Tree로 이루어진 구조. [출처] C++ STL container 시간 복잡도 및 특징 비교.|작성자 Chan

[C++] 순열 / 조합 구하기 (next_permutation/prev_permutation 함수)

순열 next_permutation C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있다. 기본은 오름차순이다, 즉 내림차순인 prev_permutation을 사용하기 위해서는 내림차순으로 정렬 되어있어야 한다. 중복이 있는 원소들은 제외하고 순열을 만들어준다. // default bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); // custom bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); next_permutation ..

[알고리즘] 순열과 조합의 차이

순열과 조합의 가장 큰 차이는 순서가 있고 없고 이다. 예를 들어 자전거의 번호가 있는 자물쇠를 연다고 가정해보자. 자물쇠 번호가 1234라고 한다면 순서에 대한 고려 없이 4321을 입력하면 자물쇠는 열리지 않는다. 이를 순열이라고 한다. (순서가 있음) 또 다른 예시로 닭가슴살 샐러드를 가정해보자. 닭가슴살 샐러드의 재료는 닭가슴살, 양상추, 소스, 토마토라고 한다면 우리는 샐러드를 담을 때 닭가슴살을 처음으로 넣고 두 번째는 양상추... 이런 식으로 넣지 않고 그냥 재료에 맞게 넣는다. 이를 조합이라고 한다. (순서가 없음) 이제 수학적으로 다가가 보자 1 2 3 4 배열이 있고 2가지 경우를 뽑는다고 가정해보자 순열의 경우에는 순서가 중요하기에 하기와 같이 다 뽑아 버린다. 1 2 1 3 1 4 ..

SDK, API의 개념과 차이점

API API란 Application Programming Interface의 약자로, 모듈화하여 만들어진, 어떤 기능을 제어/제공하는 인터페이스를 말한다. 우리가 사용하는 대부분의 애플리케이션은 API에 의존하고 있다. 예) - 차량 공유 앱에서 승차 거리와 시간을 계산하는 것 👉 API의 기능 - 차량 공유 앱에서 드라이버가 픽업 위치에 도착했음을 SMS로 알 수 있는 것 👉 API의 기능 SDK SDK란 Software Development Kit의 약자로, 소프트웨어 개발 도구 모음이라고도 한다. SDK는 API, IDE, 문서, 라이브러리, 코드 샘플 및 기타 유틸리티가 포함될 수 있다. SDK는 프로그램 및 응용 프로그램 개발의 복잡성을 줄이는 강력한 기능 집합이다. 예) iOS SDK를 다운..