stonesy

해결방법최단 경로를 구해야하므로 BFS를 사용한다.이때, visited를 3차원으로 만들어야 한다. 더러운 칸을 방문하는 순서를 고려해야 하기 때문이다. → visited배열을 3차원으로 관리해야한다. → 비트마스킹을 사용해야 한다.그래프를 모두 순회했음에도 답을 구하지 못한 경우는 방문할 수 없는 더러운 칸이 존재하는 것이므로 -1를 출력한다.모두 방문: curD==((1방문 처리: curD | (1 코드import java.util.*;import java.io.*;// 396ms// BFS + 비트마스킹 + dppublic class Main_4991_G1_로봇청소기_BFS비트마스킹 { static int h,w; // w: 방의 가로크기, h: 방의 세로 크기 static char[][..

해결방법3차원 visited 배열이 문제 풀이의 핵심이라고 생각한다.visited[r][c][i]는 (r, c) 위치에 도달했을 때, 방향 i(상, 하, 좌, 우 중 하나)로 이동한 경우에 사용된 거울의 수이다. 이때, visited가 3차원이어야 하는 이유는 같은 (r,c)라도 레이저가 상,하,좌,우 어느쪽에서 들어왔는지에 따라 다음 위치로 이동할 때 필요한 거울의 수가 달라질 수 있기 때문이다.따라서 BFS + 3차원 방문처리를 통해 풀었고, O(W*H)로 풀 수 있다. 코드import java.util.*;import java.io.*;public class Main_6087_G3_레이저통신 { static int H,W; static char[][] map; static List point; st..

해결 방법먼저, 전체 문자열에서 폭발 문자열을 찾고 다시 문자열을 이어붙여 탐색하는 풀이가 떠오른다. 최악의 경우 전체 문자열의 길이가 N, 폭발 문자열의 길이가 1d일때, N*(N-1)(N-2)…*1의 연산이 필요하다. 즉, O(N^2)이 되어 시간초과가 발생할 것이다. 그래서 스택을 사용해서 O(N)으로 문제를 해결해야 한다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..

해결 방법완전 탐색으로 접근하면 시간 초과가 발생한다. 한 지점에서 3방향으로 이동할 수 있고, 지점이 NM개 있으므로 O(3^(NM))의 시간복잡도가 소요되기 때문이다.첫 번째 행의 경우 오직 왼 → 오 방향만 가능하므로 따로 계산해주고 두 번째 행부터는 왼 → 오 / 오 → 왼을 비교해주어야 한다. 즉, 이전 단계의 최적 결과를 바탕으로 다음 단계에서의 최적 결과를 구해야하므로 DP로 접근한다고 볼 수 있다. 따라서 O(N*M)의 시간복잡도로 해결할 수 있다. 코드import java.util.*;import java.io.*;public class Main { static int MIN_VAL = -987654321; static int N,M; // (1≤N, M≤1,000) st..

해결방법서로소 집합을 통해 여행 계획인 도시들의 대표자가 모두 같으면 “YES”, 하나라도 다르다면 “NO”를 출력한다.서로소 집합시에 경로 압축 + 랭크 기반 유니온을 사용하면 find 및 union시 거의 상수시간이 소요되므로 O(N+M)의 시간복잡도로 해결할 수 있다. 코드import java.util.*;import java.io.*;// 160ms, Disjoint Setpublic class Main_1976_G4_여행가자_서로소집합 { static int N; // N: 도시의 수 static int M; // M: 여행 계획에 속한 도시들의 수 static int[][] graph; static int[] plan; static int[] parents; s..

해결방법스택을 이용하여 문제를 O(N)의 시간 복잡도로 해결할 수 있다.핵심은 스택에 자신보다 작은 높이만 유지해야 한다.현재 높이를 스택의 peek() 값과 비교하여, 만약 peek() 값이 현재 높이보다 크다면, 스택에서 해당 값을 pop() 한다. 이때 pop()할 때마다 정답을 증가시킨다.스택에 값을 넣을 때는 다음 조건을 확인한다.현재 높이가 0이 아닌 경우스택의 peek() 값이 현재 높이와 다른 경우 코드import java.util.*;import java.io.*;// 216ms, 스택, O(N)public class Main_1863_G4_스카이라인쉬운거_스택 { public static void main(String[] args) throws IOException{ ..

해결방법뽑힌 정수들의 idx들의 집합 = 뽑힌 정수들의 집합을 동일하게 만들어야 한다.감이 잘 안 잡혀서 풀이를 먼저 읽었는데 ^^ ..뽑힌 숫자들의 특징은 싸이클을 이루는 숫자들이라고 한다.문제에서 주어진 숫자들을 예시로 보면1 → 3 → 13 → 1 → 35 → 5따라서 dfs를 통해서 target(처음 시작 인덱스)를 만나면 정답배열에 넣어주도록 코드를 작성하면 되고, O(N^2)의 시간복잡도로 문제를 해결할 수 있게 된다. 코드import java.util.*;import java.io.*;// DFS, O(N^2)public class Main_2668_G5_숫자고르기_DFS { static int N; static boolean[] visited; static int[] num..

해결방법서로소 집합 / 랭크 기반 유니온(Rank Based Union)rank → 친구 네크워크의 크기를 나타내며, 친구 네트워크의 큰 쪽에 편입시킨다.rank 기반 union을 사용하므로 union시 O(1) → 상수시간에 가깝게 동작한다.따라서 O(N)=O(F)의 시간복잡도에 문제를 해결할 수 있다. 코드import java.util.*;import java.io.*;// 1668ms// union 연산에서 랭크 기반 union을 사용하므로 O(1)에 가깝게 동작한다,// 따라서 대략 O(N)=O(F)public class Main_4195_G2_친구네트워크_서로소집합 { static final int N = 200005; static int F; // F: 친구 관계의 수 stat..

*Openvidu v2 기준📌Openvidu의 구성요소Openvidu의 구성요소는 크게 Openvidu Server, Application Server(BE), Application Client(FE)로 구분할 수 있다.Openvidu Server: 실시간 오디오 및 비디오 스트리밍에 필요한 모든 인프라를 제공한다. 화상회의 서비스 개발을 위해서 단순히 배포만 하면 된다.Application Server(BE): client의 요청에 따라 openvidu server와 상호작용하며 세션을 생성하고 관리한다. Openvidu Server에서 제공하는 REST API를 통해서 Openvidu Server와 통신한다.Application Client(FE): 사용자와 직접 상호작용하는 부분으로, Openvi..

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