begong블로그

단순하게 본다면 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..

그리디 알고리즘과 우선순위 큐를 사용하는 문제이다. 입력을 받은 후 시작시간 순으로 정렬을 한다. (시작시간이 같으면 끝나는 시간이 빠른 순으로) 순서대로 우선순위 큐에 끝나는 시간을 넣어준다. 만약 다음 수업의 시작이 우선순위 큐 맨위에있는 끝나는 시간보다 늦다면 하나의 강의실에 배치 가능한것 이때는 우선순위 큐 맨 위에있는 수업을 빼고 다음 수업의 끝나는 시간을 넣어준다.( 큐에서 빠진다는 것은 한 강의실에 배치 가능하다는 것) => 새로 수업을 넣으면 재정렬이되어 끝나는시간 순서대로 배치가 된다. => 앞에 수업이 큐에서 빠지면 다음으로 끝나는 시간이 빠른 수업이 맨 위로 올라온다. 계속 진행하다 종료되었을 때, 큐에 남아있는 수업들이 강의실에 함께 배치하지 못하는 수업이다. import java...

처음 볼땐 감이 안잡히던 다이나믹 프로그래밍 문제 절차는 다음과 같다 1.전봇대 A를 기준으로 정렬을 한다(B기준이여도 됨) 2.전봇대 A기준으로 정렬된 배열에서 [N][1]번째 (전봇대B) 배열의 가장 긴 증가하는 부분수열을 구한다 3.총 갯수에서 2에서 푼 가장 긴 증가하는 부분수열의 길이를 빼준다. 가장 긴 증가하는 부분수열이 다른 일을 안해도 유지될 수 있는 전깃줄의 개수이다. 가장 긴 감소하는 부분수열은 안되나? => 안된다. 1 => 10, 2=>9로 될시에 x자로 교차해버리기 때문에 틀리다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arr..

스택을 활용하는 자료구조 문제 stack의 크기가 3이상이고, 새로 들어오는 토큰이 "P", 스택의 가장 위에 있는 토큰이 "A"일때 하나씩 꺼내며 검사를 시작한다. 스택의 상위 요소가 "PPA"였다면 (코드에서는 굳이 Reverse를 안해서 "APP"로 검사) "P"만 넣어주면 된다. 만약 아니라면 다시 원상복귀 시킨다 1차적으로 스택에 넣으며 검사를 했다면 그다음은 뒤에서부터 거꾸로 검사를 해야한다. (반례는 찾지 못했는데 뒤에서 검사를 해야 정답이 나왔다) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; class Main { public ..