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://scrap.kakaocdn.net/dn/C9ZLW/hyWg2fWBSW/fcKQFKrwAT5ODDVX4A6cak/img.png?width=800&height=948&face=0_0_800_948,https://sc..

연산 시간을 최대한 죽여야하는 문제.N이 상당히 크기때문에 최소한의 연산으로 결과가 나오게 만들어야한다. 접근방법처음엔 union find를 생각했었으나, input이 2 4, 1 3 이런식으로 들어오게된다면 2 4에 대한 union find 연산을 한번 더 해야하므로 기각. 그렇다면 priority queue를 사용해 input을 미리 정렬해놓고 차례로 union find를 한다면 중복되는 union find연산을 피할 수 있을 것 같았다. 이렇게 된다면 union find를 굳이 쓸필요없이 그냥 입력의 앞에꺼를 덮어씌우면 되어 구조를 변경했다. priority queue로 시작점 기준 오름차순 종료지점 기준 내림차순으로 정렬한 뒤, 종료지점의 max를 저장한다.pq의 다음 요소가 max보다 작으면 굳..

"에라토스테네스의 체"를안다면 쉽게 풀리는 문제이다. 에라토스테네스의 체란 간단히 말해소수의 배수 = 소수가 아님을 이용한 것이다.반복문을 돌며 가작 작은 소수인 2부터 배수를 지워주고 그다음 3 , 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 Inpu..

백트래킹 및 재귀함수 문제 공을 뺄 때마다 배열을 새로만드는 방법은 너무 메모리와 시간을 많이 잡아먹는다 굳이 새로운 배열을 만들지 말고 방문처리를 하여, W번째 공을 뺀 효과를 준다. 또한 W+1,W-1번째 공도 방문처리가 되어있다면, W+2,W-2번째를 탐색하는 식으로, 다음 공을 찾으면 된다. 양끝 공은 절대 빠질 수 없기 때문에 배열 overflow가 나지 않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int max = 0; static int N; static boolea..

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..

백트래킹 문제 입력을 오름차순으로 정렬하고 전 단계에서 방문한 노드가 현재 노드와 같은지 확인을 한다(중복 방지를 위해) 만약 같으면 그 단계는 건너뛰고 아닐 경우 진행하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Main { static int N, M; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade..

그리디 알고리즘 문제 접근방식 - 전봇대의 왼쪽, 오른쪽 집의 갯수가 같아야 한다 = > 1 3 5 7 이라 가정했을 때 전봇대가 3->2로 이동한다고 치면, 오른쪽에 집이 3개가 있기 때문에 거리의 합이 +3-1이되어 +2가된다. 3~5에서 이동은 좌측, 우측 집이 2개씩이기때문에 총 길이의 합의 변화가 없다. 3~5에서의 이동만 총 길이가 늘어나지 않기 때문에 최소치이다. 집의 갯수가 홀수일 경우, 집들의 중간값에있는 위치만이 좌측 우측의 집의 갯수가 동일하므로 유일한 답 집의 갯수가 짝수일 경우 중간값 2개중 작은것이 답(문제의 조건때문에) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..

유니온 파인드 및 dp를 활용하는 문제 누가 누가 친구관계인지 union find를 통해 찾은 뒤, dp의 배낭문제 알고리즘을 통해 어떤 그룹을 선택할 수 있는지 고르는 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Node { int cost; int value; public Node(int cost, int value) { this.cost = cost; this.value = value; } } class Main { static int[] paren..