일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 파이썬 강좌
- 프로그래밍
- 알고리즘
- it
- 2020
- 자작시
- C++
- 다이나믹프로그래밍
- mmcv
- 강좌
- 철학
- python
- 라즈베리파이
- 공부
- python 강의
- dp
- 백준
- python 강좌
- 라즈베리파이3
- 라즈베리파이 모니터
- dynamic programming
- BOJ
- 2021
- 머신러닝
- 파이썬 강의
- 강의
- IOT
- mmdetection
- 계획
- 파이썬
- Today
- Total
목록
전체 글
(105)
반응형
Stargazer
접근: 트리를 이용해서 푸는 문제 트리를 순회하는 순서만 생각하면 된다. 전략: 우선 트리 저장을 배열 형태로 저장하는데, 저장 방식은 다양하나 나는 각 알파벳을 숫자로 치환해서 저장하도록 하겠다. (공간을 많이 잡아먹지 않는 문제이기 때문에, 편한 대로 쓰도록 하겠다. 즉, 최적화된 건 아님) 순회할 때 필요한 정보는 현재 위치와 자식 노드의 유무이다. 구현: #include #include using namespace std; struct Node{ int left; int right; }; vector nod; int n; int c2n(char a){ return (a != '.') ? static_cast(a - 'A') : -1; } char n2c(int a){ return (a + 'A')..
접근: 일반적으로 계산하면 시간 초과가 뜨는 문제이다. 반복적으로 더해주는 작업을 하는 것이기 때문에 DP로 접근하여서 푸는 것이 적절해 보인다. 전략: 구간 합을 입력 받을 때 마다 (0,0) 부터 (x2,y2)를 구해주어 2차원 배열로 저장하고, 구간 합이 주어지면 구해준 구간 합의 조합{(0,0) ~ (x2,y2)}으로 해결해주면 된다. (x1 - 1 , y1 - 1) (x1 - 1, y2) (x2 , y1 - 1) (x2 , y2) 구하고자 하는 값이 (x1,y1)부터 (x2,y2) 까지의 구간 합 이므로, (x2, y2) - (x1-1 ,y2) - (x2 ,y1-1) + (x1 - 1 , y1 - 1) 이런식으로 구해준 값으로 겹치는 영역을 빼고 더해주면 원하는 구간의 값이 나온다. 구현: #i..
접근 이름부터 플로이드 이지만, 단순히 문제만 바라보면, 도시의 가장 빠른 길을 찾는데, 모든 도시를 대상으로 찾아야 한다. 이렇게 모든 대상에 대해서 최단 경로를 구하려면, 플로이드 워셜(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 밖에..