begong블로그

백트래킹 문제 하나씩 진행하며 가능성이 없는 경우의수를 제거하며 진행한다. (0,0)부터 -> (0,1)->(0,2) 차례로 진행하며 비숍을 놓을수 있는지 없는지 검사하는 것이다. 체스판 전체를 검사하면 시간초과가 일어나므로 흰칸, 검은칸을 구분하여 검사를 진행하면 된다. 다른 분들의 풀이를 보면 M퀸 문제에서 사용하는 X,Y 좌포를 활용해 대각선에 말이 있는지 없는지 검사를 하던데 나는 잘 모르겠어서, 칸을 진행할 때마다 대각선위쪽을 확인해 어디에 말이 있는지 전달하게 코드를 작성하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringToken..

bfs로 푸는 문제 조건에 맞게 구현만 하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; import java.util.StringTokenizer; class Node{ int n,m,dir,dist; public Node(int n, int m, int dir, int dist){ this.n=n; this.m = m; this.dir = dir; this.dist = dist; } } class Main{ public static in..

유니온 파인드 문제 바로 직전에 푼 문제와 비슷하게 dfs,bfs로 탐색하면 노드가 최대 20만개이기때문에 시간초과가 난다 섬을 제거하는 순서를 받아놓은 뒤, 하나씩 섬을 추가하면서 섬의 부모노드를 비교해가면서 그룹의 개수를 파악한다. 주의할 점은 n,m 이 1부터라 예외처리를 해줘야 하는 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Graph { Map graph; public Graph(int num) { graph = new HashMap(); for (int i = 1; i

단순하게 본다면 dfs bfs로 풀리는 문제 처음 시도때는 그래프와 dfs로 구현했지만 당연하게도 시간초과가 뜨고말았다. union find를 응용해서 풀어야 하는 문제이다. 제거하는 연결을 제외하고 미리 Union find를 통해서 전부 이어준다. root에는 초기 값으로 전부 -1을 넣어준다 (음수 *음수 = 음수, 본인 노드 포함 1개) union을 하면서 Root노드에 계속해서 갯수를 더해준다. (음수그대로 더한다) Root노드가 아닌 노드에는 root노드 번호 가 들어가 있다. 제거되는 연결을 반대 순서로 결합해 준다. 이때 x,y가 Root노드가 같다면 비용이 0이고, 다르다면, root노드에 저장되어있는 하위 노드의 갯수를 곱해주면 된다. import java.io.BufferedReader..

지난 문제와 같이 위상정렬을 이용하는 문제이다. 단, 간단한 위상정렬 구현만으로 풀리지 않는다. 5번 물약을 만드는 레시피가 1,2 또는 3,4라고 하자 단순 위상정렬로 구현한다고 할때 5번 노드로 진입경로는 4개가 된다. 그럼 1,2 또는 3,4 가 둘중 한쌍만 들어왔을때 아직 잔여 진입경로는 2가되므로 답이 되지 않는다. 따라서 기존과 약간 다르게 위상정렬을 구현해야 한다. 경로를 바로 저장하지 말고, 레시피를 그래프에 저장해 보자 5번 물약은 0번재 래시피를 만드는데 쓰인다 이런식으로 말이다. 그리고 진입경로는 N번째 래시피로 도달하는 진입경로의 개수를 저장해 준다. 추후 L을받고 y를 받으면 Y를 스택 또는 큐에 넣어준다. 큐에서 하나씩 Y를 꺼낸다. 그래프의 y번째에는 y번물약이 쓰이는 레시피들..

위상정렬 문제이다. 위상정렬에 대해 참고한 블로그 https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting [알고리즘] 위상 정렬 (Topological Sorting) 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방 velog.io 위상정렬에 대해 간단히 요약하면 본인으로 들어오는 경로(진입차수)가 없으면 출력해 준다는 것이다. 따라서 진입차수가 0인 노드들을 먼저 queue에 넣고 하나씩 빼면서 이어져 있는 노드들의 진입차수를 하나씩 감소시켜 준다. 위의 과정을 반복하..

우선순위 큐를 활용하는문제 1. 보석의 무게를 기준으로 오름차순 정렬하기 위해 priority queue를 생성해 보석의 무게와 가치를 넣어준다 2. 가방의 무게를 오름차순 정렬하기위해 priority queue를 생성해 넣어준다 3. 가치를 내림차순으로 넣어둘 priority queue를 넣어준다. 2번에서 생성한 가방의 무게 큐에서 하나를 뽑는다 (가장 적은 무게를 담을 수 있는 가방) 1번에서 생성한 보석들의 무게로 정렬되어있는큐에 가장 위에 요소와 가방이 담을수 있는 무게를 비교한다 가방이 담을수 있는 무게의 보석들을 전부 3번큐로 이동시킨다(가치만 전송하면 됨) 이렇게 되면 3번 큐에는 가방에 담을 수 있는 보석들만 있고, 가치가 높은 순으로 정렬되어 있다. 3번큐에 가장 위에잇는것을 뽑아 가방..

카탈란 수 문제라고 한다. 카탈란수에 대한 정리는 https://suhak.tistory.com/77 카탈란 수(Catalan number) 카탈란 수(catalan number)로 불리는 수열이 있다. 핀란드 수학자 카탈란의 이름이 붙인 이 수열을 기호로는 $C_n$으로 나타낸다. 이 수열은 여러 가지 다른 문제를 풀이하는 과정에 나타난다. 카탈란 suhak.tistory.com 이 블로그를 참고하였다. 추후 카탈란수에대한 공부를 추가적으로 해야될듯하다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main{ static long mod = (int) Math.pow(10..

다이나믹 프로그래밍 문제 처음에는 Factorial을 이용해 해당 순번 string을 구하려 했으나, 연산량이 불필요하게 많아져 포기 dp기법을 이용해 n개의a와 m개의 z로 만들 수 있는 string의 갯수를 기록하여 연산량을 줄임 dp점화식은 dp[n][m] = dp[n-1][m]+dp[n][m-1] string을 찾는 방법은 k가 n,m으로 가능한 갯수보다 크면 z를 붙이고 k-chekc(n,m)을 통해 순번을 줄여주고 z의개수 감소(m-1) 아닐경우 a를 붙여주고 a의 갯수감소 계속 위와같은방법으로 재귀를하다 끝낸다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import j..

간단한 stack을 활용하는 문제 뭔가 문제가 헷갈리게 되어있는듯 한데 음이 N까지 프랫이 P까지 범위이다. 따라서 스택을 N개 만들어주어야 한다. P는 내가 푼 방법에서는 쓸 필요가 없는데 stack의 가장 위에있는 요소와 비교를해서 손가락을 때는지, 안때는지 파악을 한다. 그래서 굳이 P를 사용할 필요가 없다. 조건을 잘 맞춰서 조건문을 작성하고 count를 해주면 쉽게 정답이 나온다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; class Main{ public static vo..