빠똥빠똥

#문제링크 : 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의 과정은 뒤에서부터 계산을 더하는 식이지만, 앞에서부터 생각해도 결과는 같다는 걸 알 수 있다. 무슨 말이냐면, 앞의 도시부터 기름을 사나가는데, 지금 내가 있는 도시보다 싼도시가 나올때까지 현재 도시의 가격으로 기름을 사나가는 것이다.

#문제링크 : www.acmicpc.net/problem/9184 1. 단순 재귀로 위의 함수를 수행하면 이미 구했던 함숫값을 다시 구해야하는 경우가 여럿 생긴다. 2. 이미 구했던 함숫값을 배열에 저장하여 동적코딩이 가능하게 한다. 3. 조건문으로 이미 구했던 함숫값이라면 check배열에서 꺼내오고 아니라면 check배열에 저장한다.

#문제링크 : www.acmicpc.net/problem/1655 1. 힙 배열을 둘로 나누어 관리한다. 앞배열과 뒷배열로 나눈다. 2. 모든 앞배열의 수는 모든 뒷배열의 수보다 작다. 단, 앞배열의 최댓값과 뒷배열의 최솟값은 같을 수 있다. 3. 전체 수열에서 중간값으로 될 수 있는 후보는, 앞배열의 최댓값 or 뒷배열의 최솟값이다. 4. 앞배열에서는 최댓값을 살펴봐야하므로 앞배열은 최대 힙으로 구성한다. 5. 뒷배열에서는 최솟값을 살펴봐야하므로 뒷배열은 최소 힙으로 구성한다. 6. 입력을 받고, 앞배열과 뒷배열에 저장할때, 앞배열과 뒷배열의 크기가 비슷해야한다. 더 정확하게 말하면 앞배열의 크기가 뒷배열의 크기와 같거나 뒷배열보다 하나 더 커야한다. (반대로, 뒷배열을 하나 더 크게 구현해도 상관없다..

#문제링크 : www.acmicpc.net/problem/11286 1. 최소 힙과 같은 방식으로 구현하되, 절댓값을 먼저 비교하고, 절댓값이 같다면 대소비교를 한다. 2. 절댓값이 같은데, 부모가 더 작거나 같으면 바로 루프를 종료해도 된다. 안그러면 무한루프를 돌게 된다.

#문제링크 : www.acmicpc.net/problem/1927 1. 최대힙과 동일하게 구현한다. 2. pop함수에서 두개의 자식노드중 더 작은 녀석을 선택해야 한다. (주의)