본문 바로가기

CS

 (56)
OS - 메모리관리: 페이징 위 사진은 CPU의 논리주소를 RAM의 물리주소로 바꾸는 작업을 수행하는 일반적인 컴퓨터구조이다.외부 단편화램은 하나하나 프레임으로 구성된다. 그리고 각 하나의 같은 크기를 갖고 있는데 만약 위처럼 4바이트로 구성되었다고 하자. 그리고 빨간색으로 칠해진 곳은 사용중이라 하면 8바이트짜리 프로세스가 램에 로드하려 한다. 지금 4바이트 짜리 프레임이 3칸 12바이트가 있으니까 로드할 수 있을까? 로드할 수가 없다! 왜냐하면 CPU는 연속적으로 램에 들어있어야 읽을 수 있기 때문이다. 그럼 지금 램에는 3칸의 빈칸이 있는데도 램에 자리가 없다고 판단되어 시스템에 지장을 준다. 이것을 외부 단편화라 한다. 페이징위의 외부 단편화를 해결하기 위한 방법으로 페이징이 있다. 페이징은 프로세스를 페이징 단위로 나눈다...
알고리즘 - 에라토스테네스의 체(C++) 최근 코딩테스트에서 소수를 판별해야하는 문제가 나왔다. 그래서 에라토스테네스의 체를 사용해야함을 바로 알았지만 아쉽게 떠올리지 못하여 정리해두려고 한다. 원래 소수를 판별하는 방법은 대학교 1학년 C언어 시간에 배울 정도로 쉽다. N까지 모두 나눠보며 나눠 떨어지는 수가 2이면 소수이다. 그러나 이것은 매우 시간이 오래걸린다.  에라토스테네스의 체는 이 수가 소수인지 아닌지 판별하는 것이 아니라 1~100만 등 어떠한 범위내에서 소수인지 아닌지 판별할 때 유용하다. 즉 1~100만 중 소수가 몇개인가? 이러한 것을 해결하는 방법이다. 알고리즘은 다음과 같다. 1.  2 ~ N까지 2의 배수를 false 처리한다. 2. 3 ~ N까지 3의 배수를 false 처리한다.4. 5 ~ N까지 5의 배수를 fals..
VScode Git 계정 이름 바꾸기 VScode 에서 Private 레포지토리를 클론해야할 일이 생겼다. 어떠한 이유로 내 깃허브 계정이 아닌 그 Private 레포지토리의 주인의 깃허브 계정을 받아 클론해야했는데 VScode 에서 그 계정으로 로그인 했는데도 깃클론이 되지 않았다. VScode 에서 사용자는 아직 나였기 때문이다. 그래서window 자격증명에서 github 연동을 지우고 나서야 새로운 계정의 자격이 내 PC에 부여되었다.
unordered_map을 이용한 노드 개수 최적화 알고리즘 문제를 풀다가 이런 문제를 발견했다. 다익스트라 문제인데 노드는 50개 뿐이지만 노드의 번호 범위가 무려 1~10억이었다. 다익스트라는 dp기반이기 때문에 dp[노드의개수]로 맞춰놓는 것이 일반적이다. 그런데 dp[10억]은 엄청난 메모리 낭비를 초래한다. 그래서 사용할 수 있는 방법이 바로 unordered_map을 이용한 노드 개수 최적화이다. unordered_map는 자동으로 키값으로 정렬하는 맵과 달리 정렬하지 않는 해싱기법이다. unordered_map nodes; int get_idx(int v) { return nodes[v]; } 먼저 맵을 선언해두고 인덱스를 겟할 수 있는 함수를 만들어준다. for (int i = 0; i < N; i++) { if (nodes.count(원래..
문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 아이디어는 접미사와 접두사이다. 접미사와 접두사는 단어를 반으로 잘라 왼쪽이 접두사 오른쪽이 접미사가 된다. ABCDAB 가 있으면 ABC는 접두사 DEF는 접미사가 된다. 자, 이걸 어떻게 쓸 수 있을까. 위 단어는 접두사와 접미사가 일치하는 것이 없다. 그러니 다른 예제를 보자. ABA 라고 생각하자. 접두사와 접미사에 모두 A가 있다. 그리고 ABAABA 라는 인풋에서 ABA를 찾는다고 생각해보자. ABAABA ABA 1개를 찾았다. 원래같으면 ABAABA ABA ABA 이런식으로 슬라이딩 윈도우처럼 ..
최소 스패닝 트리 (MST) - 프림 알고리즘 최단거리 알고리즘에는 우리가 익히 잘 아는 다익스트라 알고리즘, BFS가 대표적이다. 그러나 이 두개의 알고리즘은 모든 정점을 지나지 않고 무조건 최단거리를 찾는다. 그래서 모든 정점을 방문해야하는 문제를 해결할 수 없다. 때문에 MST 최소 스패닝 트리가 필요하다. 그래프에서 모든 정점을 지나는 트리를 그린다는 의미이다. 1. 프림 알고리즘 프림 알고리즘은 "정점" 을 아무거나 한 개 선택한다. 그리고 정점의 인접 정점들 중 가장 거리가 가까운 정점으로 이동한다. 그리고 지금까지 지나온 정점들 중 가장 가까운 곳으로 간다. 그림을 통해 이해하자. 자세히 설명해보면, 스탭1: 아무 정점이나 넣는다. 보통 1을 넣는다. 그리고 1에서 가장 가까운 곳으로 이동하면서 dist 배열을 업데이트한다. 스탭2: 현..
방향 그래프에서 사이클 찾기 Cycle? 사이클은 모두 알다시피 그래프에서 시작과 끝이 같은 형태를 말한다. 그래프에서 사이클은 언제나 성가신 존재인데, 무한루프를 발생 시킬 수도 있고, 쓸 대 없이 몇 번 돌다가 나와서 성능이 안 좋아질 수도 있다. 이것은 현업에서도 골치이고 PS에도 자주 등장하는 문제이다. 이것을 어떻게 판별할 수 있을까 방향 그래프에서 싸이클 판별 방향 그래프에서 사이클을 판별할 수 있는 방법은 가장 익숙한 DFS 이다. dfs는 방향이 계속 같기 때문에 다음 노드를 판별하기 용이하기 때문이다. 그리고 방향 그래프에서의 사이클이란 Back Edge가 존재하는 것과 같다. 이제 문제는 Back Edge를 판별하는 것으로 바뀌게 된다. void dfs(int NowNode) { visited[NowNode] = ..
벨만-포드 알고리즘 (Bellman-Ford Algorithm) Bellman-Ford Algorithm 벨만 포드 알고리즘은 음수 간선이 존재하고 그것이 사이클을 만들어낸다고 해도 최단거리를 만들 수 있는 알고리즘이다. 다익스트라 알고리즘은 익히 알다시피, 음수 간선이 존재하면 사용할 수 없는 것을 알고 있을 것이다. 다익스트라와 벨만 포드의 차이 다익스트라와 벨만 포드는 둘 다 1차원 dist 배열을 갱신하며 최소치를 기록하는 스킬은 똑같다. 그러나, 다익스트라는 모든 노드를 살펴보지 않는다. 가능한 경우에만 다음 노드로 이동하기 때문이다. 그러나 이 효율적인 방식 때문에 음수 간선이 있으면 다익스트라를 사용할 수 없다. 그러나 벨만 포드는 효율적이지 않게도 모든 노드를 살펴본다. 그래서 시간복잡도가 N*M이다. 그리고 음수간선이 있어도 사용이 가능하다. 바로 아..

티스토리툴바