본문 바로가기

알고리즘/문제26

[자바] 백준 1717 - 집합의 표현 유니온 파인드 문제 1. 내 부모가 누구인지 담는 배열 parent[i]을 일단 나 자신으로 초기화 한다. 2. 파인드 - 내 부모가 정말 최상위 부모인지 계속 찾아 나가면서, 최상위가 아닐 때에는 상위의 부모로 값을 교체한다. private static int find(int x) { if(parent[x]==x) return x; else return parent[x] = find(parent[x]); } 3. 유니온 - 두 숫자의 부모를 확인해서, 부모 값이 다르다면 부모 값을 a나 b의 부모값으로 교체해준다. 어떤 값의 부모를 넣을 것인지는 상관없다. private static void union(int a, int b) { a = find(a); b = find(b); if(a!=b) { par.. 2020. 12. 29.

[자바] 백준 1956 - 운동 시작점과 도착점이 정해져 있지 않고, 경로의 합이 가장 작은 사이클을 찾으면 된다. 사이클을 어떻게 찾아낼지에 대해 어렵게 생각했는데, 플로이드 워셜 알고리즘 이용해서 dist[1][1], dist[2][2], ..., dist[V][V]의 값들을 확인하면 되는 문제였다. 도시의 개수는 최대 400개이고, 간선의 개수도 최대 V(V-1)라고 했으니 최대 16만개로 보면 된다. 최대값들을 기준으로 생각했을 때, 간선은 16만번을 읽으면 되고, 플로이드 워셜 알고리즘은 400 x 400 x 400이니까 6천 4백만 정도의 연산만 필요하다. 이 문제가 플로이드 워셜을 이용하면 된다는 걸 알고 나면 엄청 쉬운데, 그걸 알아챌 짬이 부족하다 /* 2020.12.24(목) */ import java.io.Buffe.. 2020. 12. 24.

[자바] 백준 11404 - 플로이드 플로이드 와샬 알고리즘에 대한 문제. 모든 정점에서 모든 정점에 대한 최단 거리를 구할 때 사용하는 알고리즘으로, 일종의 DP라고 한다. 3중 for문으로 해결을 하는데 1번째 for문 : 경유지 k 2번째 for문 : 시작점 i 3번째 for문 : 종료점 j 이렇게 모든 N에 대해 3중 for문을 돌리기 때문에 정점의 개수가 적은 문제에서만 적용이 가능하다. 기본적인 아이디어는 경유지의 입장에서 생각을 하는 거다. 시작점 i가 나한테 오는 최단거리 + 내가 종료점 j로 가는 최단거리가 시작점 i에서 종료점 j로 바로 가는 최단거리 보다 작으면 값을 갱신해준다. 처음 조금 의심이 들었던 부분은 정말 모든 경우에 대해서 최단 거리로 갱신이 가능한지 였다. 예를 들어 2 →4(경유)→1(경유) →5 로 가는.. 2020. 12. 19.

[자바] 백준 2206 - 벽 부수고 이동하기 ㅎㅎㅎㅎ메모리도 너무 많이 사용하고 속도도 느려서 이렇게 저렇게 나름 바꿔봤지만 변하지를 않았다. 속도는 그렇다 쳐도 메모리가 너무 의아했다. class하나 생성해서 큐에 집어넣어줘야 하나..?는 생각이 들었지만, 예전에 풀었던 소스도 int배열로 풀었는데 뭐가 문제지 고민했다. 근데 방금 이유를 하나 찾아냈는데 너무 어이가 없다. BFS할 때 꼭 들어가는 dir[] 배열을 que안에서 매번 선언/생성하지 않고 que만 밖에다가 선언해서 썼더니 1/3이 줄었다 ㅎㅎ,,어이없네 코드는 그냥 맨 처음 시도해서 성공한 코드라 최적화 전혀 안 되어 있다. 처음 시도할 때에는 틀렸었는데, 방문 여부를 부수고 들어왔을 때, 부수지 않고 들어왔을 때 나눠서 생각하지 않아서 틀렸다. 어차피 그 지점에 도착한 거면 상관.. 2020. 12. 12.

이전 1 2 3 4 5 6 7 다음

티스토리툴바