본문 바로가기

CS

 (51)
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이다. 그리고 음수간선이 있어도 사용이 가능하다. 바로 아..
OS - 주기억장치 개요 운영체제의 역할 운영체제의 가장 중요한 역할은 프로세스 관리와 메모리 관리이다. 이제부터 알아볼 것은 메모리 관리이다. 메모리는 언제나 부족하다. IT 기술이 발전하면서 계속해서 메모리는 늘어나고 있지만 그와 동시에 다뤄야할 데이터와 프로그램들도 함께 거대해진다. 그래서 메모리는 언제나 부족하고 효율적으로 관리해야한다. 메모리 관리의 개념과 정책 메모리 관리는 메모리 관리자가 담당하며 운영체제의 관리 모듈과 메모리 관리 장치가 협업하여 관리한다. 메모리 관리자는 여러 정책을 수립하고 관리한다. 적재 정책 배치 정책 대치 정책 메모리의 구조: 주소, 데이터 주소는 논리적 주소와 물리적 주소로 나뉜다. 논리적 주소 - 프로그래머가 사용하는 공간으로 보는 논리적 관점의 주소. 목적 코드가 저장된 공간과 프로그..
플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 그래프 이론에서 모든 정점간의 최단 경로를 찾기 위한 알고리즘이다. 이 알고리즘은 두 개의 단계로 이루어진다. 위 그래프를 예로 들어 초기 배열을 만들어보자. 그리고 각 노드를 경유지로 지정한다. 즉 지금은 인접노드만 가지고 있지만 1 → 2 → 3 이러한 경우도 계산한다는 뜻이다. 먼저 1번 노드를 경유한다고 가정하자. 그렇다면 1행은 스킵하고 2행을 진행한다. DP[4][2] = DP[4][1] + DP[1][2] 이므로 다음과 같은 점화식을 얻을 수 있다. DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]) 위 점화식을 해석하면 정점 i 와 j의 최소 거리는 원래 지정되어 있던 값과 노드 k를 경유했을 때의 최소값이다. 그러므로 k도 1부터 N..
OS - 모니터 (멀티 스레드 프로그래밍) 프로세스/쓰레드 동기화 도구 중 하나이다. 세마포어는 너무 오래된 것이고 최근 자바는 모니터를 지원한다. Java의 모든 객체는 모니터가 될 수 있다. 베타 동기 - Common Variable 은 오직 하나만 접근할 수 있다. → synchronized 키워드 사용 조건 동기 - wait(), notify, notifyAll 메소드 사용 notifyAll 하면 모든 스레드가 풀려난다. 모니터는 사실 멀티코어 컴퓨팅 강의에서 배운 멀티 스레드 프로그래밍과 같은 것을 알게 되었다. 아래는 멀티코어 프로그래밍에서 과제로 해결한 소수찾기 문제이다. package Task; public class pc_dynamic { // 20만까지 테스트하기 위함 private static final int NUM_END ..

티스토리툴바