빠똥빠똥

#문제링크 : www.acmicpc.net/problem/1916 1. 노드 N개, 간선 M개인 그래프에서 최단거리를 구하는 문제. 그래프에서 최단거리를 구하는 알고리즘 중 가장 성능이 좋다고 알려진 다익스트라를 사용하면 됩니다. 2. 다익스트라는 먼저, 인접행렬 또는 인접리스트로 그래프를 표현한 뒤, dist배열과 check배열을 선언합니다. 3. dist[x] = 시작노드로부터 x번째 노드까지의 최소 거리를 의미하고, check[x]=1은 x노드를 방문했다.를 의미합니다. a[i][j]는 i번째 도시에서 j번째 도시로 가는 비용을 의미합니다. 4. 문제에서 살펴야할 조심해야하는 부분은 도시는 최대 1000개, 버스는 최대 10만개 입니다. 이말은, 중복되는 버스노선이 존재한다는 걸 의미하고, 문제에서..

#문제링크 : www.acmicpc.net/problem/11444 1. 피보나치 수3과 동일한 방법으로 풀었습니다.

#문제링크 : www.acmicpc.net/problem/17298 1. O(N^2)의 알고리즘 밖에 떠오르지 않아서 다른 블로그를 참조했습니다. 2. 개인적으로 생각하기 굉장히 어려운 알고리즘이었습니다. 요약하면 이렇습니다. 우선 스택을 만들고, 스택에, 문제에서 주어진 수의 범위보다 큰 수를 미리 하나 넣어놓습니다. 그리고 주어진 수열의 뒤에서부터 차례로 스택top의 숫자와 비교합니다. 3. 만약, 수열의 숫자가 스택top보다 작다면, 스택top에 들어있는 숫자가 오큰수가 됩니다. 따라서, 이때에는 스택top의 숫자를 해당 수열의 인덱스와 같은 정답 배열에 우선 복사하고, 수열 숫자를 스택에 push합니다. (이 과정에서 pop은 없습니다.) 4. 만약, 수열의 숫자가 스택top보다 크다면, 스택to..

#문제링크 : www.acmicpc.net/problem/13305 1. 처음엔, 도시 중 가장 싼 도시를 찾아 그 도시부터 뒤로 쭉 그 가격으로 구매, 도시 범위를 처음~가장 싼 도시로 수정하고 다시 그중에 가장 싼 도시를 찾아 그 도시부터 수정된 범위의 마지막 도시까지 그 가격으로 구매 ... 이런식으로 했었는데, 답은 맞았지만 시간초과가 나왔다. 2. 1의 과정은 뒤에서부터 계산을 더하는 식이지만, 앞에서부터 생각해도 결과는 같다는 걸 알 수 있다. 무슨 말이냐면, 앞의 도시부터 기름을 사나가는데, 지금 내가 있는 도시보다 싼도시가 나올때까지 현재 도시의 가격으로 기름을 사나가는 것이다.