전체 글533 [알고리즘] 다익스트라 (Dijkstra) 알고리즘 다익스트라 (Dijkstra) 모든 간선의 가중치가 '음이 아닌 경우' 의 유향 그래프 최단 경로 알고리즘 '한 정점' → '모든 정점' 까지의 최단 경로 구하기 우선순위 큐 사용O 시간복잡도 : O(E log V) 우선순위 큐 사용X 시간복잡도 : O(V ^ 2 + E) 정점 수 대비 간선의 수가 많은 경우 (간선 밀도가 높은 경우)에는 우선순위 큐를 사용하지 않는 경우가 더 빠르다. 모든 간선의 가중치가 같다면 BFS로 최단 경로를 구할 수 있지만 그렇지 않은 경우엔 다익스트라 사용 BFS 기반 그리디 알고리즘 (Greedy Algorithm) 알고리즘 시작점 start로부터의 정점들까지의 최단거리를 나타내는 dist 배열을 둔다. dist[start] = 0, 나머지는 무한대로 설정한다. queue.. 2020. 10. 2. [알고리즘] 최소비용 구하기 (백준 1916번) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 한 시작점에서 나머지 노드까지의 최소 거리를 구하는, 전형적인 다익스트라 문제다. 사실 다익스트라 문제는 이번이 처음 풀어보는데 생각보다 시간이 오래걸렸다. 계속 8%에서 넘어가질 않아서 한참 고민하고 있었는데 알고 보니 버스는 단방향인데 나는 양방향으로 생각하고 문제를 풀었다.... Solution dist 배열에서 시작점 dist[start] = 0이고 나머지는 무한대로 초기화한다. 각 노드의 edge 정보들을 저장해놓는다... 2020. 10. 2. [알고리즘] 구슬 탈출 2 (백준 13460번) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 기출 문제이다. 삼성 기출에서 자주 나오는 맵에서 물체들을 동시에 움직이는 시뮬레이션 유형이다. BFS를 활용하여서 빨간 공이 구멍에 빠지는 최단 시간을 알아내야한다. Solution 시뮬레이션 문제 중 물체를 동시에 움직이는 문제는 항상 까다롭다. 이 경우는 보드를 기울일 때 고려해야할 상황이 많다. 상하좌우로 기울일 때, 어떤 공을 먼저 움직여야 동기화가 될 지 움직이다 다른 공을 만나면 멈춰야 됨 움직이.. 2020. 10. 2. [운영체제] 메모리 관리 기법 메모리 관리 기법 다중 프로그래밍 시스템에서는 메모리의 사용자 영역을 여러 프로세스가 상주할 수 있도록 세분화해야된다. 이러한 세분화 작업을 메모리 관리라고 한다. 메모리 할당 정책 정책 설명 반입 정책 메인 메모리에 적재할 프로세스의 반입시기를 결정하는 방법 배치 정책 프로세스를 메인 메모리 어디에 저장할 것인지 결정하는 방법 - 최초 적합 : 사용가능 공간 중 첫 번째 공간에 할당 - 최적 적합 : 사용가능 공간 중 가장 작은 크기의 공간에 할당 - 최악 적합 : 사용가능 공간 중 가장 큰 크기의 공간에 할당 대체 정책 메인 메모리의 어떤 프로세스를 제거할 것인가를 결정하는 기법 1. 연속 메모리 할당 방식 프로그램을 메모리 공간 한 곳에 연속적으로 할당하는 방법 MMU를 이용해서 프로세스의 논리 메.. 2020. 10. 1. 이전 1 ··· 87 88 89 90 91 92 93 ··· 134 다음
