일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 백준
- 2021
- dp
- 알고리즘
- python 강좌
- 다이나믹프로그래밍
- 계획
- C++
- 자작시
- mmdetection
- IOT
- python 강의
- 라즈베리파이 모니터
- python
- 프로그래밍
- mmcv
- 라즈베리파이
- 공부
- 강의
- 파이썬
- 라즈베리파이3
- 철학
- 2020
- 파이썬 강좌
- dynamic programming
- 머신러닝
- 강좌
- BOJ
- it
- 파이썬 강의
- Today
- Total
목록
Undergraudate basics(학부생 기초)/자료구조, 알고리즘
(27)
반응형
Stargazer
접근 이름부터 플로이드 이지만, 단순히 문제만 바라보면, 도시의 가장 빠른 길을 찾는데, 모든 도시를 대상으로 찾아야 한다. 이렇게 모든 대상에 대해서 최단 경로를 구하려면, 플로이드 워셜(Floyd-Warshall) 알고리즘을 이용하면 된다. 그렇지만 나는 이 알고리즘을 제대로 이해하지 못해서 다른 방식으로 해결했다. 전략 플로이드 워셜 알고리즘의 전략은 각 정점을 조사해서 해당 정점을 사이로 지나는 두 정점을 찾아서 만약 더 짧은 거리이면 짧은 거리로 갱신한다(두 정점의 직접 경로가 없는 건 ∞ 로 가정) 본인은 잘못 이해 해서 시간 복잡도가 조금 더 증가했다. 각 도시 간 거리를 매트릭스의 형태로 저장해서 각 행에 대해서 조사를 하는데, 만약 경로가 있는 도시가 있다면, 그 도시로부터 다른 도시를 ..
#include #include using namespace std; int n, k; // n: 물품의 수, k: 버틸 수 있는 무게 int DP[101][100001]; int W[101]; int V[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i > W[i] >> V[i]; } for (int i = 1; i
접근 3가지의 선택: -1, +1, x2 그리고 가장 작은 weight를 가지는 길을 찾아야 한다. 그래서 일단은 너비 우선 탐색을 선택했다. 왜냐하면 가장 짧은 길을 탐색하기 위해서 너비를 우선으로 탐색해야 하기 때문이다. 그렇게 하기 위해 큐를 이용하기로 했다. 그리고 가중치가 0,1 로 다르기 때문에 다익스트라 알고리즘을 이용하기로 했다. 전략 큐에 n의 위치를 넣고, 3가지 선택 중에 선택을 할 수 있는 조건을 만족하면(범위 내 이고, 가중치가 더 작으면) 선택을 하여 큐에 삽입을 한다. 이때, 중요한 건 선택 순서가 중요한데, 2배를 하면 가중치가 0이기 때문에, 3가지 중에 2배를 하는 것을 먼저 선택하도록 순서를 정해야, 최소의 가중치를 구할 수 있다. 방향성이 음수로 가는 방향은 -1 밖에..
단순 합병 문제: 두 시퀀스 A, B를 오름차순으로 주어진다고 할때, 두 시퀀스를 하나로 합병한, 정렬된 시퀀스 C를 구하라(C 크기 = n) 합병 전략: A,B의 최소값 중 더 작은값을 C에 넣는데, 만약 최소값이 A 에 있다고 가정하면, A의 최소값을 C에 넣고, A의 나머지와 B, 그리고 C 를 재귀적으로 함수를 호출하여 합병을 한다.(분할 정복) 합병 수도코드: Merge(A,B,C) if(A is empty) rest of C = rest of B else if(B is empty) rest of C = rest of A else if (first of A
추가 공간을 일반 퀵소트보다 줄이는 알고리즘 추가 공간: $O(n)$->$O(1)$( 재귀적일때는 $O(lgn)$을 사용) 전략은 이전 퀵소트와 같이, 분할 정복을 이용할 것이다. 다만 공간을 추가적으로 사용하지않고, 해야하므로, 요소끼리 스위칭하는 방식으로 해야한다. In-place Quick sort 수도코드: Algorithm inPlaceQuickSort S, l, r Input sequence S , ranks l and r Output sequence S with the elements of rank between l and r rearranged in increasing order if l >= r return i
특징: Worst case에 대해서는 $O(n^2)$ 시간이지만, Average case 에 대해서는 $O(n\log n)$ 시간이 걸린다. 전략: Divide and Conquer(분할 정복): 큰 문제를 여러개의 작은 문제로 분할하여 재귀적으로 처리 후 합쳐서 해결하는 방법 *단계: 1. 분할: 작게 문제를 나눈다.(이때, 나눈 것도 해결전략이 동일한 문제여야한다.) 2. 정복: 재귀적으로 계속 작게 나누면서, 문제를 해결한다.(문제를 해결할 수 있는 가장 작은 단위 까지 나눔) 3. 조합: 해결한 문제들을 조합하여 원래 input에 대한 결과값을 리턴한다. * 분할 정복 알고리즘 수도 코드: solve(I) n=size(I) if(n
*자료구조 시간에 문제풀다가 배운 내용을 정리한 것입니다. 입력: 후위 순회한 결과와 그 노드의 깊이 출력: 전위 순회한 결과 예를 들어 후위 순회한 결과가 다음과 같이 주어 졌을때, 값: 5 2 8 9 10 6 7 3 4 1 깊이: 2 1 3 3 3 2 2 1 1 0 출력은 다음과 같다 1 2 5 3 6 8 9 10 7 4 트리를 그림으로 그리면 다음과 같다. #솔루션 우선 깊이의 개념을 이해해야한다. 깊이는 노드가 루트에서부터의 간선의 개수이다. 그리고 후위 순위는 가장 왼쪽 것부터 그리고 가장 깊이가 깊은 것부터 처리한다. 따라서 깊이의 변화로 이들의 관계가 무엇인지 알 수 있다. 우선 노드 1의 자식은 깊이가 1인 녀석들이다. 그래서 입력값으로부터 2 3 4 임을 알 수 있다. 여기서 더 내려가면..