분류 전체보기

문제 접근 처음에는 일단 구현부터 해보려고 단순하게 최단 경로를 지우고 다시 최단 경로를 찾는 걸 생각했다. 이때 첫 번째 최단 경로의 길이를 변수에 할당해서 다음 최단 경로의 길이가 이와 같으면 이 또한 기존의 최단 경로라고 생각해서 지우기를 반복했다. 하지만 첫 번째 시도의 최단 경로를 지우는 순간, 다른 최단 경로가 최단 경로가 아니게 될 수 있기에 이 방법은 틀렸다. 그래서 두 번째로, 최단 경로를 다 모아서 한 번에 지우는 방식을 구현했다. 어떻게 구현해야 할까 고민하던 중 다익스트라 알고리즘의 priority_queue 가 보여서 여기에도 사용할 수 있을 것 같았다. 갱신할 때 부등호 처리해주고 자동으로 정렬한 뒤 eraseEdge()에서 child까지의 최단 거리가 같으면 경로가 다른 최단 ..

문제 접근 한 주제에 대해 깊게 시도해보기 : 다익스트라편 시작이다. 경로를 저장하면 되는 골드2치고 생각보다 쉬운 문제였다. 문제 코드 #include #include #include using namespace std; vector adj[1001]; // 경로 저장하는 벡터 vector via(1001, -1); int N, M, A, B, C; void circuit() { vector dist(1001, 10000001); priority_queue q; dist[1] = 0; q.push(make_pair(0,1)); while(!q.empty()) { int here = q.top().second; int cost = -q.top().first; q.pop(); if(dist[here] < ..

문제 접근 처음에 바보같이 가장 많은 시간을 소비하는 사람..? 그럼 최장 거리지 하면서 다익스트라로 최장거리를 구하려고 했었다. 다익스트라 알고리즘 그대로 최장 거리 구하려고 하면 양수 사이클 있으니까 당연히 루프 돌텐데 "에..? 왜 루프 돌지..?" 이러고 있었다. 사람인가. 최단 거리 중 가장 긴 값이다. 요즘 내가 잘하고 있는건지 모르겠다. 그냥 열심히 하고 있기는 한데 몰두해있는 감각이 느껴지지 않는다. 여기서 잠깐 머리 쉬고 온다고 알고리즘을 안하면 분명 편할거다. 하지만 언제까지고 힘들때마다 기약없이 쉴 수는 없잖아. 계속 흥미를 붙이고 불태우는 연습을 해보자. 주의할 점! 1. 문제 조건 똑바로 읽기. 2. 다익스트라에서 단순하게 최장거리를 구현할 때 양수 사이클이 있을 수 있다는 걸 잊..

문제 접근 알고리즘 문제해결전략 책에서 플로이드-와샬 알고리즘 공부하고 풀었다. 이 알고리즘도 감은 오는데 직관적인 이해가 안 돼서 계속 풀어본 뒤 정리 한 번 해야 될 것 같다. 그래프를 하나씩 확장해나가며 갱신한다고 생각하면 될 것 같다. k 번 정점이 추가된 경로의 거리가 이 정점을 경유하지 않은 경로의 거리보다 짧다면 갱신하면서 결국에는 모든 정점쌍에 대한 최단 거리가 할당되는 것이다. 주의할 점! 1. 문제 조건 확실하게 확인할 것. 2. 범위 확실하게 지정할 것. 문제 코드 #include #include using namespace std; int n, m; int adj[101][101]; void floyd() { for(int i=1; i

문제 접근 음수 사이클을 찾는 문제이기 때문에 다익스트라 알고리즘로는 제대로 풀지 못할 수 있다. 알고리즘 문제 해결 전략 책에서 벨만-포드 알고리즘을 공부하고 이 문제를 풀었다. 벨만-포드 알고리즘은 각 정점까지의 최단 거리의 상한을 담은 배열 upper[] 를 relax 하는 과정을 통해 최단 거리를 찾는 알고리즘이다. 다만 최단 거리를 구할 때 특정 한 정점까지의 최단 거리를 갱신하면서 구하는 다익스트라와는 달리 벨만-포드 알고리즘은 relax(완화) 하는 과정을 V-1 번 거치기에 음수 간선이 있을 때의 최단 거리 또한 판단할 수 있으며, 음수 사이클의 존재 여부는 V 번째에 완화가 되는지로 판단해서 음수 사이클까지 확인할 수 있다. 동작 과정은 이해가 되는데 풀이에 대한 감각이 아직 느껴지지 않..

문제 접근 알고리즘 문제해결 전략 책에서 다익스트라 알고리즘을 공부하고 이 문제를 풀었다. 처음에 priority_queue 우선 순위를 잘못 고려하고, INF 값을 너무 작게 넣어주는 실수를 해서 고쳤는데 틀렸다고 계속 틀렸다고 나와서 하루 종일 고민했다. 어제 연등 시간 끝나서 일단 생활관으로 돌아가 잤는데 꿈에서 여러가지 시도를 하다가 이 문제 AC 를 받았다. 난 '어, 맞았네?' 라고 생각하고 있는데 꿈에서 깰 것 같아서 '빨리 코드를 확인해야 돼!' 라고 생각하다가 깼다 ㅋㅋㅋ 뭔 꿈이지 싶어서 아침에 사지방 와서 확인해봤는데 배열 크기 잘못 지정해서 틀린 거였다 ㅋㅋㅋ. 진짜... 진짜 너무 즐겁다~ 정점이 20000 개고 1부터 시작하면 20001 으로 잡아줘야지 ㅎㅎㅎ vector 라고 ..

문제 접근 예전에 비슷한 문제 푼 적 있었는데... 범위 내부 확인하고, 조건에 성립하지 않으면 재귀로 범위 나눠서 다시 확인하면 되는 간단한 문제였다. 문제 코드 #include using namespace std; int plane[128][128]; int blue=0, white=0; void count(int x, int y, int n) { // 해당 면이 전부 같은 색이면 true. bool check = true; for(int i=x; iN; for(int i=0; iplane[i][j]; count(0,0,N); cout

문제 접근 1967 번 코드를 재활용했다. 내가 내 코드를 재활용하는 날이 오다니! 완전 날로 먹는 문제자너? 흠흠.. 아무튼 1967 번과의 차이점은 다음과 같다. 1. 입력의 양식이 다르다. 2. 정점의 개수와 가중치 크기 제한이 다르다. 3. 1967 번에서는 단방향 그래프로 트리를 구현했는데, 1167 번은 양방향으로 입력을 한다. 1번은 양식에 맞게 바꿔서 해결했고, 2번 또한 크기를 바꿔서 해결했다. 1967 번은 지름이 최대 100 * 10,000 = 1,000,000 으로 int 형에 담을 수 있었고, 1167 번은 안 될 거 같았는데 지름이 최대 10,000 * 10,000 = 1,00,000,000 여서 마찬가지로 int 형에 담을 수 있었다. 3번의 경우, 1967 번의 diamete..