본문 바로가기
728x90

분류 전체보기138

순환의 개념과 기본 예제 1 순환이란 - 자기 자신을 호출하는 함수 순환함수를 잘못 만들게 되면 무한루프에 빠지게 되는 경우가 생긴다. 이런 경우를 방지하기 위해서 조건을 추가해줘야 한다. 1~n까지의 합을 순환함수를 이용해 구하는 원리 순환의 대표적인 예시1 : n! 0! = 1 n! = n*(n-1)! n>0 순환의 대표적인 예시2 : 피보나치 f0 = 0 f1 = 1 fn = f(n-1) + f(n-2) n>1 2021. 5. 1.
[백준 9370] 미확인 도착지[java] 이 문제는 처음에는 무조건 지나야하는 점들을 방문하며 풀려했었다. 하지만 그러면 dijkstra알고리즘을 너무 많이 사용하게 되는거 같아서 다른 방법을 찾아봤다. 방법을 찾던 중 반드시 가야하는 곳의 가중치를 *2 +1을 해주면 홀수가 되고 나머지 가중치들은 *2만 한다면 결국 가여하는 길을 지나서 목적지에 도달한다고 생각할 때 목적지의 값은 홀수가 되있을 것이다. 결국 시작점에서 모든 노드로 가는 가중치들을 구하고 목적지로 예상되는 노드들의 가중치를 구했을 때 짝수인 경우를 출력해주면 된다. 코드 package baekjoon; import java.io.*; import java.util.*; public class uncomfirm_destination { static class Node imple.. 2021. 4. 8.
[백준 1504] 특정한 최단 경로[java] dijkstra알고리즘을 조금만 응용한다면 쉽게 풀수 있는 문제였다. 하지만 그 조금의 응용이 어려워 다른 사람이 푼 방법을 찾아봤다... 우선 무조건 거쳐서 가야하는 노드들을 v1,v2라고 한다면 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 이렇게 거쳐가면 된다. 따라서 결과 1 += dijkstra(1,v1) 결과 1 += dijkstra(v1,v2) 결과 1 += dijkstra(v2,N) ------------------------------ 결과 2 += dijkstra(1,v2) 결과 2 += dijkstra(v2,v1) 결과 2 += dijkstra(v1,N) 후에 결과 1과 결과 2중 더 작은 값을 출력해주면 된다. 코드 package baekjoon; import .. 2021. 4. 8.
[백준1753] 최단경로[java] dijkstra알고리즘을 이용하여 문제를 풀었다. 처음에는 시작점을 기준으로 가중치를 모두 -1로 만든다. 이후 연결된 값들을 큐에 넣고 가중치를 바꿔준다. 이러는 과정에서 직접 연결된 가중치보다 돌아서 가는 가중치가 더 낮다면 돌아가는 것으로 바꿔준다. 코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class shortest.. 2021. 4. 7.
[백준17472] 다리 만들기2[java] 정말 어려운 문제였다. bfs와 크루스칼 알고리즘을 사용해야 했다. 우선 첫단계로는 입력받은 숫자들을 bfs를 이용해 섬의 번호를 붙여줬다. 두번째 단계로는 섬에서 상하좌우중 한 방향으로만 나아가다가 다른 섬을 만났을 때 시작섬과 끝섬, 그 길이를 edge클래스로 만들고 우선순위 큐에 넣는다. 마지막으로는 우선순위큐에서 하나씩 꺼내 크루스칼 알고리즘을 이용해 순환하지 않는 최단거리를 찾았다. 코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; im.. 2021. 4. 7.
[백준2887] 행성터널[java] 문제에서 최소비용을 계산할 때 x,y,z의 거리중 가장 작은 값의 비용이 든다고 했다. x,y,z로 각각 오름차순으로 정렬한 뒤 가중치를 구해서 한번에 저장한다. 그 후에 find-union알고리즘을 이용해 순환하지 않게 최소값을 구하면 된다. 코드 package baekjoon; import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class planet_tunnel { static class Point{ int num,x,y,z; Point(int num, int x, int y, int z){ this.. 2021. 4. 5.
728x90

티스토리툴바