begong블로그

그리디 알고리즘 문제 카드가 겹쳐지며 계속 사용되는 구조이다. 따라서 합이 최소가 되기 위해서는 작은 카드들이 최대한 많이 쓰여야한다.priority queue에 넣어서 카드의 숫자가 작은 순서대로 카드를 합치면 최소치가 나온다. 단 덧셈의 횟수가 상당히 많으므로 자료형을 잘 고려해야한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { static PriorityQueue pq = new PriorityQueue(); public s..

유사문제 : https://begong313.tistory.com/44 이미 앞에있는 건물들은 신경안써도 된다. 이미 stack안에 존재하는 건물들이 새로 들어온 건물을 볼수 있냐 없냐에만 신경쓰면됨 => 이미" data-og-host="begong313.tistory.com" data-og-source-url="https://begong313.tistory.com/44" data-og-url="https://begong313.tistory.com/44" data-og-image="https://blog.kakaocdn.net/dna/C9ZLW/hyWg2fWBSW/AAAAAAAAAAAAAAAAAAAAAOr3ILd46RsZywSblIccd3T_yWAxRefS80P_Gv-Su7Gx/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1767193199&allow_ip=&allow_referer=&signature=Je%2B1QrAFRvK1xHMONiZK4RVGnDw%3D

dfs및 백트래킹문제 dfs를하면서 depth가 4일때(0부터 depth가 시작한다고 했을떄)인 경우가 생긴다면 조건을 만족하는 문제이다. 문제는 예상치 못한곳에서 생겨버렸다. 처음코드는 dfs안의 반복문에서 비효율적으로 값을 가져왔고 영향을 주는지 모르겠으나 매번 visit배열이 함수호출때 같이불려 비효율적이라 시간초과가 발생했다. //첫 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.StringTokenizer; class Main { static LinkedList[] graph; stat..

피보나치 수열을 활용한 dp문제이다. vip좌석은 고정된 좌석이므로 경우의수의 구분점이 된다 vip좌석 사이에 일반좌석 1개일때 : 1가지 2개일때 : 2가지 3개일때 : 3가지 4개일때 : 5가지 ... 따라서 경우의수는 피보나치 수열과 동일하다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.pa..

처음 접근 방법 : 가장 긴 감소하는 부분순열 - 서류심사 등수, 면접 등수가 주어지기 대문에 배열의 index를 서류심사 등수로, 면접등수를 배열의 값으로 넣어주어 가장 긴 감소하는 수열을 찾으면 될 것 같았다. => 시간초과 n^logN 다음 접근 방법 : 위의 방식과 같이 서류심사 등수로 정렬을 한다(등수를 배열의 index로 활용하기때문에 입력을 받으며 정렬이 된다) 1등의 면접등수를 min으로 기록하고, 그 값보다 작은 값들만 추린다. min값보다 값이 작다면 answer에 1을 더해주고 min값을 해당 값으로 바꿔준다.(이렇게되면 1등보다 면접등수가 낮고, 서류심사등수가 높은 사람만 선택됨) import java.io.BufferedReader; import java.io.IOException..

dfs를 활용한 구현문제이다. PriorityQueue를 활용해 가장 가까운, 거리가 같다면 행번호가 적은, 행도 같다면 열번호가 적은 승객을 구해 이동시킨다. 그 후 해당 승객이 원하는 지점에 데려다준다. 위의 과정을 계속 반복하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer; class Point { public int y, x; public Point(int y, ..

위상정렬 문제이다. 문제만 보면 N번째 장난감이 마지막에 해당될 것 같지만 역으로 N번째 장난감부터 탐색을 진행해야된다. 필요한 요소들의 개수를 판단하는 것이기 때문에 N번째 장난감부터 탐색을 해야 atomic한 장난감부품의 필요한 갯수를 알 수 있다. (atomic한 부품부터 N번째 장난감으로 탐색할 수 있지만 필요한 데이터가 너무 많아진다) inputRoot를 활용하여 더이상 해당 부품의 요구 갯수가 없을 때 까지 탐색을 하고, 해당 부품의 InputRoot가 0일때는 더이상 해당 부품이 추가될 일이 없으므로 해당 부품을 이루는 다른 부품이 몇개 필요한 지 탐색이 가능하게 된다. import java.io.BufferedReader; import java.io.IOException; import ja..

bfs + 구현문제 알고리즘은 어려운것이 없다. 기울이는 방향에 맞춰서 먼저 옮길 공을 구별하여 이동시키면 된다. ex ) -> 방향으로 기울임 : 둘중 우측 공 먼저이동. 나중에 이동하는 공은 먼저 이동한 공의 위치를 체크하며 이동. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; class Main { static int N, M; static char[][] map; static int[] moveX = {1, -1, 0, 0};..

다익스트라 알고리즘 문제 bfs를 하며 조건이 있다면 다익스트라라고 하는 것 같다. 길이 상관없이 도착점에 최소의 벽을 부수고 도달하면 되는 문제이다. 따라서 우선순위 큐를 선언한 뒤, 벽을 부순 횟수별로 정렬을하여 우선순위 큐에 넣어준다. 어디든 벽을 부순 횟수만 최소이면 되니, 방문처리까지 해준다. ex ) 벽을 부순 횟수가 0인 노드에서 탐색 => bfs로 탐색하며 주변에 벽이 있다면, 벽부순카운트 +1 및 방문처리 후 우선순위큐에 넣어줌. (이러면 지점이 벽을 최소로 부수는 횟수로 큐에 들어감.) 만약 0회 부순 경로가 다 소진된다면, 다음 최소인 1회부순 경로를 탐색, 위 절차반복 이런식으로 진행되다보니 도달점에 항상 최소치로 도달할 수 있다. 위의 로직으로 탐색을 하다 도착점에 도달하면 풀리는..

그래프 및 다익스트라 알고리즘 문제이다. 길의 길이 D가 주어지면 노드가 D만큼 있고 가중치 1으로 1크기차이로 이어져 있다고 생각하면 된다. 1- 2 는 가중치 1로 이어져 있음. 단 역주행이 안되니 단방향 그래프 노드를 1씩 증가시키며 해당 노드가 갈 수 있는곳에 길이를 기록해 놓는다. 이때 지름길이 있다면, 지름길 도착지점에 도달하기위한 거리를 기록해 놓는다. 지름길이 없다면 전 노드에 +1한 값을 기록해 준다(그래프가 크기 1차이로 이어져있다고 생각하기 때문에) 하나의 노드씩 증가하며, 해당 노드에 도달하기 위한 최소치를 알아낸 뒤, 최종적으로 도착점에 기록되어있는 수치를 출력해주면 된다. 필요없는 연산을 빼기위해 조건을 추가하여 입력을 받았다. import java.io.BufferedReade..