stonesy

해결방법서로소 집합(Disjoint Set)서로소 집합이란 집합들 간의 교집합이 없는, 즉 서로 겹치는 원소가 없는 집합들의 모음을 관리하는 자료구조이다. 집합 간의 연결 여부 확인시 서로소 집합을 활용할 수 있다.두 노드의 대표자가 같다면 연결되어 있음대표자가 다르면 연결되어 있지 않다.로직서로소 집합을 활용해 서로 연결된 파티를 구한다.각 파티의 대표자를 구한다.(대표자가 같다면 연결되어 있고, 대표자가 다르면 연결되어 있지 않다.)과장된 이야기를 하면 안되는 파티의 대표자들을 구한다.전체 파티의 수 - 과장된 이야기를 하면 안되는 파티 수union-find 시 선형으로 연결된 경우(최악의 경우) 시간복잡도가 O(M)이므로 시간복잡도는 대략 O(NM)이다. 코드import java.util.*;imp..

해결방법수를 순서대로 순회하면서 투 포인터로 서로 다른 두 수의 합으로 나타낼 수 있는 수의 개수를 구한다. ⇒ O(N^2) (N≤2000)*수의 위치가 다르면 값이 같아도 다른 수이다. 코드import java.util.*;import java.io.*;// O(N^2)public class Main_1253_G4_좋다_투포인터 { static int N; static int[] numbers; public static void main(String[] args) throws IOException{ // 1. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

해결방법2개의 용액을 골라야한다. 일반적으로 조합을 구하기 위해서는 O(2^N)의 시간복잡도를 가진다. 위 문제의 경우 2≤N≤100000이므로 적용불가능하다. (대략 N이 10을 넘어가면 불가능)투포인터로 접근한다.left+right의 절댓값이 answer보다 작다면 answer 갱신(left와 right 위치 저장)left와 right의 용액을 더했을 때 양수이면 → right-1left와 right의 용액을 더했을 때 음수이면 → left+1left결론적으로 투포인터로 O(N)의 시간복잡도로 문제를 해결할 수 있다.  코드import java.util.*;import java.io.*;// 308ms, 투포인터, O(N)public class Main_2467_G5_용액_투포인터 { stati..

해결방법최단 경로이므로 BFS로 접근한다.단, 이동하는 도중에 한개의 벽을 부수고 이동할 수 있다는 변수가 있다. 벽의 위치를 저장하고 먼저 벽을 부수고 출발하면 최악의 경우 시간복잡도가 O((N*M)^2)로 시간초과가 발생한다.따라서 3차원 배열로 거리/방문체크를 해야한다. 3차원 배열인 이유는 map 자체가 2차원 배열이고 벽을 부수지 않은 경우/벽을 부순경우를 나눠야 한다. 벽을 부수고 간 것이 먼저 도착하는 경우 벽을 부수지 않고 도착한 것이 방문처리되어 통과되지 못할 수 있기 때문이다. 코드1(거리 비교)import java.util.*;import java.io.*;public class Main_2206_G3_벽부수고이동하기_거리체크 { static int N,M; // N(1 ≤ N ..

해결방법기둥을 정렬한 후 가장 높은 기둥을 알아낸다.왼쪽 ~ 가장 높은 기둥까지 면적을 더한다. 왼쪽에서 가장 높은 기둥을 기준으로 가장 높은 기둥이 갱신될 때마다 면적을 더한다.오른쪽 ~ 가장 높은 기둥까지 위와 같은 로직을 반복한다.⇒ 정렬에 O(Nlog), 면적을 더하는데 O(N)의 시간복잡도가 소요된다. 코드import java.util.*;import java.io.*;// 112mspublic class Main_2304_S2_창고다각형 { static int N; static Tower[] tower; static class Tower{ int w, h; public Tower(int w, int h){ this.w=w; ..

스택해당 유형의 문제는 스택 자료구조를 사용하여 O(N)으로 문제를 해결할 수 있다.스택에는 항상 “현재 인덱스보다 높은 탑들의 인덱스들”만 들어있다. 1부터 N까지의 인덱스를 순회하면서, 현재 인덱스보다 낮은 탑들의 인덱스를 스택에서 제거한다. 스택의 최상위에는 레이저가 처음으로 도달하는 탑의 인덱스가 항상 위치하게 된다.Stack stack = new Stack();for(int i=1; i 코드import java.io.*;import java.util.*;//716ms, O(N)public class Main { static int N; static int[] tower; public static void main(String[] args) throws IOException{ ..

주요 로직영어 공부 문제(https://stonesy927.tistory.com/275)와 마찬가지로 ei 이분탐색을 통해서 특정 조건을 만족하는 바로 다음 값을 찾는다.int left = i;int right = N-1;while(left영어 공부 문제에서는 numbers[mid]-numbers[i]-p⇒ 연속 공부 기간보다 작거나 같은 idx 바로 다음 idx가 return되었다.광고 시간 구하기 문제에서는 ads[mid].end-ads[i].start⇒ 광고 시작 ~ 끝까지 L보다 작거나 같은 idx 바로 다음 idx가 return될 것이다. 또한 누적합 개념을 사용하였다.int ans = S[left]-S[i];if(left여기서 S[left]-S[i]는 i~left-1까지의 총 합이고, 마지막 ..

주요로직n개의 수가 정렬되어 있어 정렬 로직 없이 이분탐색을 사용할 수 있다.길이 n의 numbers 배열을 한번씩 순회하면서 + 이분탐색을 통해서 O(NlogN)으로 문제를 해결했다.int answer = 0;for(int i=0; i이분탐색을 통해서 특정 조건을 만족하는 idx 바로 다음 값을 찾았다.int left = i;int right = n-1;while(left그리고 연속으로 영어 공부를 할 수 있는 날 left-i+p을 계산하고, answer 값을 비교하며 최대값으로 update 해주었다.answer = Math.max(answer, left-i+p); 코드import java.io.*;import java.util.*;public class Solution_10507_binarySearc..

가장 긴 증가하는 부분수열(LIS)  가장 긴 증가하는 부분 수열을 구하기 위해 아래와 같이 DP를 이용해서 풀 수 있지만, 이 경우 시간복잡도가 O(N^2)이기 때문에 N값이 매우 커지면 위험하다고 생각했다.//1. dpfor(int i=0; iA[j]) dp1[i] = Math.max(dp1[i],dp1[j]+1); }} 이분탐색, O(logN)이분탐색을 이용하면 DP를 이용했을 때 O(N^2)이었던 시간복잡도를 O(NlogN)으로 줄일 수 있다.public static void binarySearch(List arr, int target){ int left = 0; int right = arr.size()-1; while(left=target){ right = mid-1; }else{ ..

외판원 순회(TSP)외판원 순회 문제란 모든 도시를 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소 비용을 구하는 문제이다.N(도시의 수) 값이 작으면, 순열로도 문제를 해결할 수 있지만 N 값이 매우 커지면 불가능하다. 순열의 시간복잡도가 O(N!)일 때 N의 값이 대략 11을 넘어가면 위험하기 때문이다. N 값이 매우 클 경우, DP를 이용해서 풀어야한다. DP + 비트마스킹dp[current][visited]: current 도시에서 남은 도시들을 모두 방문하여 출발점으로 되돌아가기 위한 최소비용current: current 현재 도시visited: 현재까지 방문한 도시들을 비트마스킹으로 표현해놓은 것 비트마스킹모든 도시를 방문한 경우 visited == (1(1 도시를 아직 방문하지 않은 경우v..