전체 글 (125) 썸네일형 리스트형 14938 서강그라운드 처음에 이 문제를 접근할 때, 어려웠던 점은 양방향 그래프를 표현하는 방법이 헷갈렸다. map과 2차원 배열 중에 어느 걸로 나타낼 지 고민하다 두 가지 방식을 다 해봤는데, map을 사용했을 때의 문제점은 한 정점과 다른 정점 사이의 최단 경로를 표현하기 애매했다. 그리고 DFS, BFS로 접근하려 했기 때문에 모든 정점들에 대해 탐색을 시도하려 했다. 하지만 그럴 필요 없이 이 문제에 딱 알맞는 알고리즘이 존재했는데, 플로이드 와샬 알고리즘이다. 플로이드 와샬 알고리즘을 사용하는건 다음과 같다. 모든 정점에서 다른 정점들까지 최단 경로를 알고 싶음 음수의 가중치를 갖는 간선에서의 최단 경로르 알고 싶음 단, 제약 조건도 있는데 다음과 같다. 음수 가중치를 갖는 사이클에서는 알고리즘의 정당성을 보장 못.. 2751 수 정렬하기 2 STL에서 제공하는 sort 함수는 템플릿 기반으로 quick sort를 수행한다. quick sort는 다른 정렬들에 비해 nlogn의 수행속도를 가지는데, 분할 정복이라는 방법을 사용하기 때문이다. 예를 들어, 버블 정렬과 비교해보면 버블 정렬은 n^2의 시간복잡도를 가지는 반면, quick sort는 pivot을 기준으로 탐색 범위를 절반으로 줄여가기 때문에 nlogn의 시간복잡도를 가질 수 있다. 참고 : gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html [알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 정답 코.. 2638 치즈 코드 길이가 길어질수록 실수할 확률이 높아지는건 불변의 진리같다... BFS 코드길이를 최대한 짧게 시도해 봐야할거 같다. 정답코드 더보기 #include #include #include using namespace std; #define MAX_SIZE 102 int N, M; int field[MAX_SIZE][MAX_SIZE] = { {2, 2} }; int dirRow[] = { 0,0,1, -1 }; int dirCol[] = { 1, -1, 0, 0 }; void bfs(int row, int col) { queue q; for (int i = 0; i < MAX_SIZE; i++) { for (int j = 0; j < MAX_SIZE; j++) { if (field[i][j] == 2) {.. 이전 1 ··· 32 33 34 35 36 37 38 ··· 42 다음
