https://www.acmicpc.net/problem/1162문제조건 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장포장하게 되면 도로를 지나는데 걸리는 시간이 0서울은 1번 도시, 포천은 N번 도시 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간은?접근방법 가중치가 있는 그래프에서 특정지점에서 시작해서 다른지점까지의 최단거리를 구하는 알고리즘인 다익스트라가 떠올랐다. 사실 이 문제는 푸는것 자체는 크게 어렵지 않았다. 다익스트라 알고리즘 자체가 dp를 기반으로 이때까지 계산된 거리와 새로운 거리를 비교해서 계속해서 기록하는 구조이므로, 엄청나게 큰값이 들어 갈수 있기때문엥 21억이 넘는 수 까지 처리해..

https://www.acmicpc.net/problem/2075문제조건N×N의 표에서 N번째 큰 수를 구해라.모든 수는 자신의 칸(행)보다 위에 있는 수보다 크다.접근방법 접근방법이라 할것도 없었고, 입력받고 냅다 내림차순정렬해서 N번째 순서의 숫자를 찾았다. 메모리초과는 잘 나지 않아서 당황했지만 어디서 생긴걸까 생각해보면 1500 x 1500 x 4(Byte) = 대략 9MB여서 메모리에 대해서는 아예 초과가 안날줄 알았지만, 내부적으로 사용되는 변수, 내가 사용하는 또 다른 변수들을 고려한다면, 아리까리한 메모리라는 것이다. 일단 해결하기 위해선, 입력으로 받는 표에 대해 전부 저장하면 안된다는것이다. 풀이 배열, 벡터, 큐 등 어떤 자료구조 하나를 선택하고, 그것의 크기가 N보다 커지면 계속 정..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제조건 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 우선 입/출력이 많이 일어나기 때문에 입출력에 대해서 시간을 줄여줘야한다. 다들 많이 알고 있는 단축 코드이다. ios::sync_with_stdio(false); cin.tie(0); https://dingcoding.tistory.com/62 ios::sync_with_st..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제조건 수빈이와 동생이 있다. 걷는다 : X+1 or X-1 (1초) 순간이동 : 2 * X (0초) ☞ 시간 안걸림 수빈이가 동생을 찾는 가장 빠른시간? 문제를 보고 수빈이와 동생이 아닌, 출발지와 목적지로 생각을 바꿔봤다. 그러면 문제가 평소에 익숙하게 보던 최단거리 찾기가 된다. 그러나, 일반적인 최단거리 찾기와 다른 점은 순간이동을 할때는 시간이 안걸..