개발/알고리즘

'백준 5719번 : 거의 최단 경로'를 풀고 드디어 골드를 달성했다! 최근에 지루하다고 해야할까? 알고리즘에 손이 잘 안 가서 꽤 힘들었다. 실력을 제대로 쌓아가고 있는지도 모르겠고, Solved.ac 의 Class 내에 있는 Essential 문제들은 다양한 주제의 문제를 조금씩 풀어보는거라 그런지 수박 겉핥기만 하는 느낌이었다. 그래서 한 주제를 잡고, 깊게 파보기로 결정했는데 이게 답이었다. 내가 손이 안 갔던 건 한 주제에 익숙해질만하면 다른 주제로 넘어가면서 막히는 게 계속 반복되다보니까 힘들었던 것 같다. 한 주제를 잡고 진행해보니 플레티넘 문제도 생각해보면서 충분히 풀 수 있었고, 재미가 있으니 술술 잘 풀렸다. 앞으로 이런 식으로 공부하려고 한다. 일단은 내가 가장 약했던 그래프부터 계속..

문제 접근 처음에는 일단 구현부터 해보려고 단순하게 최단 경로를 지우고 다시 최단 경로를 찾는 걸 생각했다. 이때 첫 번째 최단 경로의 길이를 변수에 할당해서 다음 최단 경로의 길이가 이와 같으면 이 또한 기존의 최단 경로라고 생각해서 지우기를 반복했다. 하지만 첫 번째 시도의 최단 경로를 지우는 순간, 다른 최단 경로가 최단 경로가 아니게 될 수 있기에 이 방법은 틀렸다. 그래서 두 번째로, 최단 경로를 다 모아서 한 번에 지우는 방식을 구현했다. 어떻게 구현해야 할까 고민하던 중 다익스트라 알고리즘의 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