전체 글

백트래킹 알고리즘

백트래킹 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾는 알고리즘 DFS는 가능한 모든 경로를 탐색하지만 백트래킹은 해를 찾아가는 도중 경로가 해가 될 거 같지 않으면 그 경로를 더 이상 찾아가지 않고 되돌아 간다. 가지치기 - 불필요한 부분을 쳐내고 최대한 올바른 쪽을 간다 백트래킹은 모든 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이다. 해가 될 만한지 판단 후 유망하지 않으면 가지치기 후 이전(부모) 노드로 돌아간다. N-Queen public class NQueen{ static int N = 4; static int[][] board = new int[4][4]; public static void main(String[] args){ if(put_queen(0) ..

숨바꼭질 3 -13529번

풀이 방법 2배로 갈때와 1칸 이동할때 가중치가 다르다고 생각해서 다익스트라 알고리즘을 사용해서 풀어야 겠다고 생각했다. Node에 위치와 그 위치에 도달할 때 1초가 걸리는 지 0초가 걸리는지 넣어주었다. 위치에 도달하기 위해 걸리는 총 시간은 sec배열에 넣어서 구현했다. 풀다보니 BFS로도 가능할거 같다는 생각이 들어서 BFS로도 풀어보았다. BFS에선 Node에 sec를 그 위치에 걸리는 총 시간을 넣어서 sec 배열을 사용하지 않았다. 가중치가 다르긴 하지만 규칙이 있는 가중치라서 BFS로도 가능하게 풀이된 것으로 보인다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node { private int N; priva..

DFS와 BFS - 1260번

풀이 방법 전형적인 bfs, dfs 문제로 풀어보면 둘의 차이점을 잘 알 수 있다. 방문할 수 있는 정저미 여러개인 경우 정점 번호가 작은것을 먼저 방문한다는 조건으로 정렬한번만 해주면 되는 문제 였다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static ArrayList graph = new ArrayList(); static Boolean[] visited; static int N, M, V; static void dfs(int V) { visited[V] = true; System.out.print(V + " "); for (int i = 0; i < graph.get(V).size(); ..

그래프 탐색 알고리즘 - DFS / BFS

스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조 (입구, 출구 동일) 큐 자료구조 먼저 들어온 데이터가 먼저나가는 형식의 자료구조 DFS 깊이 우선 탐색 (깊은 부분을 우선적으로 탐색) 스택 자료구조 또는 재귀 함수를 이용한다. 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리, 인접 노드가 없으면 스택에서 최상단 노드 꺼냄 2번을 수행할 수 없을때까지 반복 DFS 예제 코드 import java.util.*; public class Main { public static boolean[] visited = new boolean[9]; public static ArrayList graph = n..

저울 - 10159번

풀이 방법 모든 물건에서 비교 결과를 알 수 없는 물건의 개수를 출력해야 되기 때문에 플로이드-와셜을 사용했다. 일단 비교 결과를 저장할 테이블을 만들고 100으로 채워넣었다. (그냥 비교 할 수 없는 경우를 100 으로 사용했음) 자기 자신과 비교는 0으로 바꿔주었다. 내가 비교하는 수보다 크면 1, 작으면 -1 로 두었다. 플로이드-와셜을 사용해서 두 수를 비교할 때 중간에 낄수 있는 수가 있으면 넣어 주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..

백도어 - 17396번

풀이 방법 다익스트라로 최단 경로를 구하는 문제이다. 최단 경로를 구하는 과정에서 지나간 지점인지 확인할 때 시야가 보이는 지점인지 확인해서 경로를 지나가지 않도록 설정하고 시야가 보이더라도 넥서스라면 경로가 지나가도록해서 최단경로를 구하도록 구현했다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { private int index; private Long distance; public Node(int index, Long distance) { this.index = index; this.distance = distance; } public int getIndex() { ret..

최단경로 - 1753번

풀이 방법 전형적인 다익스트라 문제이다. 우선순위 큐를 이용한 다익스트라 알고리즘을 구현해서 풀이했다. 2021.10.01 - [분류 전체보기] - 최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜) 내 코드 package com.company; import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable { private int distance; private int index; public Node(int index, int distance) { th..

최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 단일 출발 최단 경로 : 어떤 하나의 지점에서 나머지 모든 지점으로 경로 단일 도착 최단 경로 : 모든 지점에서 어떤 하나의 지점으로 경로 (간선을 뒤집으면 단일 출발 최단 경로 문제와 같음) 단일쌍 최단 경로 : 모든 지점 쌍들 사이의 최단 경로 BFS 가중치가 없거나 모든 가중치가 동일한 그래프에서 사용 다익스트라 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 에서 사용 벨만-포드 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착에서 사용 플로이드-워셜 전체 쌍 최단 경로에서 사용 다익스트라 최단 경로 ..

동전 2 - 2294번

풀이 방법 동적 계획법으로 bottom-up 방법을 사용했다. 우선 100001로 초기화 시켜주고 만들수 있는 coins 에 넣은 수들로 비교해가며 최소 횟수를 구해주었다. 내 풀이 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(s..

1로 만들기 - 1463번

풀이 방법 생각 DP 문제로 점화식을 생각해야 했다. 일단 0과 1은 0번으로 고정이라서 값을 넣어주었다. Bottom-up 방식으로 2부터 n까지 계산해 주었다. 이전 수에서 1을 더하는 경우를 생각해서 이전 수의 횟수에서 1을 더해주는 경우 2로 나누어 떨이지기 때문에 2로 나눈 수의 횟수에 1을 더하는 경우 3으로 나누어 떨어지기 때문에 3으로 나눈 수의 횟수에 1을 더하는 경우 이 세가지를 비교해서 최솟값을 만들어 주었다. 내 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Mai..