LCA 처음에는 단순하게 두 정점의 깊이를 맞추고 한 칸씩 올라가면서 LCA를 확인하는 풀이로 맞았는데 시간이 1초가 넘어갔다. 그래서 어떻게 최적화를 할 지 고민하다가 트리를 그려보니 느낌이 왔다. 정점 7과 2 사이의 거리 = (1과 7 사이의 거리 + 1과 2 사이의 거리 - 1과 4사이의 거리 * 2) 1. 처음에 깊이를 초기화해주는 동시에 거리값도 따로 저장해둔다. 2. LCA를 구하고 위 식과 같이 계산해준다. 소스 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #incl..
특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘. - 간선의 가중치가 음인 경우에도 사용가능 하다. - 음의 사이클이 있는지 확인 할 수 있다. V : 노드의 갯수D[i] : 출발점에서 K 정점 까지의 최소 비용 (D[출발] = 0, 나머지는 무한대로 초기화) 1. 모든 간선을 (V - 1)번 확인한다. D[now] != INF 이고 D[next] > D[now] + W (간선의 가중치) 이면 D[next] = D[now] + W 로 갱신한다. 2. V번째 간선을 확인했을 때 D가 갱신된다면 음의 사이클이 존재한다. 시간복잡도 : O(VE) 12345678910111213 D[1] = 0; // 출발점의 비용은 0 FOR(i, 1, V) { for (info edge : v) { /..
다익스트라 알고리즘 다익스트라를 사용해서 푸는 기본 문제. D[i] : 출발점에서 i 까지 갈 때 최소 비용. 출발점을 제외하고 모두 아주 큰 값으로 초기화해준다. 예제 입력을 그림으로 나타냈다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #define FOR(i,a,b) for(int i = a; i b.second; }};int D[20001];int N, M, start, X, Y, W;vector edge[20001];priority_queue q;int main() { sws; cin >> N >> M; cin >> start; FOR(i,..
머지 소트를 이용한 문제 풀이 풀이 설명을 들었을 땐 이해가 갔지만 정작 머지 소트를 구현하지 못해 시간을 많이 소모했다. ㅜㅜ 53번째 줄처럼 정렬한 배열을 원래 배열에 업데이트를 해줘야 하는데 안해서 혼란에 빠졌다.... 풀이의 핵심은 머지 소트 과정에서 배열을 두 조각으로 나눴을 때 각각 맨 앞에 있는 원소끼리 대소 비교를 한다. 이 때 오른쪽 수가 더 크다면 임시 배열에 넣고 왼쪽에 남아있는 숫자들의 갯수 만큼 순위를 빼주면 된다. 자신보다 앞에 있는 선수만 보면 되기 때문이다. 세그먼트 트리로 풀 수도 있다고 하는데 감이 안온다.... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495..
- Total
- Today
- Yesterday
- 운영체제
- Fast Campus
- #패스트캠퍼스 #프로그래밍대학생서포터즈 #올인원패키지 #컴퓨터공학 #성공하는프로그래밍공부법
- c언어
- 컴퓨터공학
- 패스트캠퍼스
- 프로그래밍 온라인 강의
- 개발자 취업
- 올인원 패키지
- 코딩 면접
- 자료구조
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |