알고리즘77 [알고리즘] 퍼즐 (백준 1525번) 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 비트마스킹 문제를 찾고 있었는데 비트마스킹으로 풀기엔 시간이 너무 오래걸려서 그냥 배열을 이용해서 풀었다. BFS를 이용해야 하는 문제다. Solution 우선 고려해야할 것은 1차원 배열의 index와 2차원 배열의 row, column을 왔다갔다 해야되는 것이다. 여기서 핵심은 visited, 즉 방문 처리를 무엇으로 할 것이냐 인데 난 int형 배열을 이용해서 처리했다. 문자열을 사용하는 사람도 있는데 문자열로도 성공은 하지만 메모리 사용량 측면에선 int형 배열이 훨씬 효율적이다. 1. 전역 변수 static HashSet visi.. 2020. 10. 3. [알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘 플로이드 와샬 (Floyd-Warshall) 유향 그래프에서 '모든 정점' → '모든 정점' 까지의 최단 경로를 구하는 알고리즘이다. 시간복잡도 : O(N ^ 3) , (N은 노드의 수) 삼중 반복문을 사용하기에 N의 크기가 상대적으로 적을 때 사용해야한다. 알고리즘 정점 i → 정점 j 까지의 최단 거리를 저장하는 dist[][] 배열을 둔다. dist 초기화 i == j : 0 i → j 까지의 간선이 존재한다면 dist[i][j] = w[i][j] i → j 까지의 간선이 존재한다면 dist[i][j] = INF (무한대) 삼중 반복문 실행 첫번째 반복문 k = 1 ~ N : 거쳐가는 정점 두번째 반복문 i = 1 ~ N : 시작점 세번째 반복문 j = 1 ~ N : 도착점 dist[i][j] = .. 2020. 10. 3. [알고리즘] 다익스트라 (Dijkstra) 알고리즘 다익스트라 (Dijkstra) 모든 간선의 가중치가 '음이 아닌 경우' 의 유향 그래프 최단 경로 알고리즘 '한 정점' → '모든 정점' 까지의 최단 경로 구하기 우선순위 큐 사용O 시간복잡도 : O(E log V) 우선순위 큐 사용X 시간복잡도 : O(V ^ 2 + E) 정점 수 대비 간선의 수가 많은 경우 (간선 밀도가 높은 경우)에는 우선순위 큐를 사용하지 않는 경우가 더 빠르다. 모든 간선의 가중치가 같다면 BFS로 최단 경로를 구할 수 있지만 그렇지 않은 경우엔 다익스트라 사용 BFS 기반 그리디 알고리즘 (Greedy Algorithm) 알고리즘 시작점 start로부터의 정점들까지의 최단거리를 나타내는 dist 배열을 둔다. dist[start] = 0, 나머지는 무한대로 설정한다. queue.. 2020. 10. 2. [알고리즘] 최소비용 구하기 (백준 1916번) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 한 시작점에서 나머지 노드까지의 최소 거리를 구하는, 전형적인 다익스트라 문제다. 사실 다익스트라 문제는 이번이 처음 풀어보는데 생각보다 시간이 오래걸렸다. 계속 8%에서 넘어가질 않아서 한참 고민하고 있었는데 알고 보니 버스는 단방향인데 나는 양방향으로 생각하고 문제를 풀었다.... Solution dist 배열에서 시작점 dist[start] = 0이고 나머지는 무한대로 초기화한다. 각 노드의 edge 정보들을 저장해놓는다... 2020. 10. 2. 이전 1 ··· 4 5 6 7 8 9 10 ··· 20 다음
