Stargazer

접근: 일반적으로 계산하면 시간 초과가 뜨는 문제이다. 반복적으로 더해주는 작업을 하는 것이기 때문에 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 밖에..

요즘 코딩 하다보면 한글 경로를 사용해서 오류 생기는 일이 비일비재 해서 그냥 user 폴더를 영어이름으로 바꾸었다. 그러자 컴퓨터가 맛이 가기 시작했다. 대표적으로 vscode의 업데이트 오류, 재설치 오류 였다. 뭐가 문제인지는 모르겠는데, 재설치하려면, config폴더를 삭제하고 새로운 setup파일을 다운받아서 설치해야한다. go to %UserFolder%\AppData\Roaming\Code and delete the whole folder. Then uninstall and install it again. -> 해당 경로로 가서 폴더를 삭제하고 다시 설치하면 된다. 해결 레퍼런스: https://answers.microsoft.com/en-us/windows/forum/all/cant-ins..