HwangHub

문제 문제 링크 해석 누적합이 음수로 변환되는 부분은 계속 더하는 것보다, 다시 구간을 설정하는게 누적합 입장에서 "반드시" 더 좋은 결과가 나올 수 밖에 없다. 따라서 이 문제를 그리디로 풀면 전체 배열을 단 한번만 선형 순회하여 답을 구할 수 있으므로 O(N)으로 도출된다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = Stream.of(br.readLine().split(" ..

JUNGOL code_blocks 코드 보기 jungol.co.kr 풀이 stack을 사용하면 "stack을 한번 거친 소는 다신 들어올 수 없으므로" 넣는거 N번, 빼는거 N-1번 해서 O(N + N - 1번)의 연산만으로 해결이 가능하다. 코드 package algorithm.jol; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque; /** * 수행 시간 : 209ms * 메모리 : 43.4 MB */ public class JOL_1141_불쾌한날 { public static void mai..

문제 문제 링크 접근 세 가지 풀이로 접근했습니다. DFS 판단 근거 : 그냥 행렬 보자마자 무지성으로 떠오른 풀이입니다. 시간복잡도 : O(NM); 인접행렬로 전체탐색 실행시간 : 344 ms 중복조합 판단 근거 : 격자상 이동 방식에 따라 visited를 검사할 이유가 없으니 이동 방향들의 조합으로 풀 수 있을 것으로 봤습니다. 시간복잡도 : O(NM); 중복조합 nHr == (n + r - 1) C (r) 이므로 (n + r - 1)! / (n - 1)! * (r)! 입니다. 실행 시간 : 160 ms DP 판단 근거 : 점화식이 간단할 것 같았고, 경로가 매 회마다 누적되는 느낌이니 DP로 가능할 것으로 봤습니다. 시간복잡도 : O(NM); 2차원 loop 돌면서 dp matrix tabulati..

✨ 문제 코드트리 문제 링크 📈 해석 구간을 구분하는 유형은 +1 / -1 테크닉을 이용하여 풀 수 있다. 이 문제에서는 구간별 크기의 합을 묻고 있으므로, 모여있는 구간들을 하나의 연속된 구간으로 구분하여 그 크기를 계산하면 된다. +1 / -1 테크닉을 사용하기 위해 입력되는 x의 값을 기준으로 정렬한다. 이 때, x좌표의 범위가 1 이상 10억 이하이므로 +1 / -1 값을저장하는건 모든 x에 대하여 배열 크기를 잡기보다는 좌표 개수만큼만 저장할 수 있도록 자료구조를 사용하면 된다. 나는 어차피 정렬+선입선출로 x를 사용해야 할 것으로 보여서 바로 우선순위큐를 이용하여 관리해 주었다. 이후 +1 / -1 값을 이용하여 0이 되는 지점을 체크하여 연속 구간을 구분하고, 구간이 시작되는 지점의 값을 i..

문제 문제 링크 해석 해당 문제는 기본 구현으로도 가능하고, 누적합으로도 가능하다. 한번 살펴보자. 기본 구현 제외되는 숫자들이 B 개만큼 존재한다고 하면, 그 숫자들을 Hash Set을 이용하여 관리하고, 1부터 n까지 슬라이딩 윈도우 느낌으로 k의 길이만큼 연속된 수열을 한칸 한칸 밀면서 매 이동마다 다음에 추가되는 숫자가 B개의 숫자 중 하나이면 cnt++, 그리고 이동마다 다음에 빠지는 숫자가 B개의 숫자 중 하나이면 cnt--로 연산한다. 이렇게 계산하면서 매 이동마다 cnt의 최소값이 뭔지만 갱신해주면 답을 찾을 수 있다. 누적합 하지만 잘 생각해보면 이 방식은 매번 이동마다 수행해야 하는 연산량이 (상대적으로) 많다. 하지만 이를 미리 계산해둘 수 있다면 어떨까? 각 구간별로 누적 cnt 값..

문제 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 해석 개인적으로는 헤맨 문제인데... 로직은 이진탐색의 기본 유형이다. 내가 나눠주고자 하는 과자 길이 X가 무엇인가를 찾는 문제로, 단순하게 for loop만을 이용하여 모든 길이에 대하여 탐색하는 로직은 O(n)인데 10억까지 탐색해야 하므로 불가능한 로직이다. 따라서 내가 찾는 X를 찾는 로직을 O(logN)으로 찾을 수 있는 이진탐색이 가능한지 봤는데, 가능했다. 헤..

문제 링크 문제 해석 트리 구조에서 공통된 조상 중 가장 가까운 조상을 찾는 건 그래프 알고리즘 중 유니온파인드 알고리즘의 '파인드' 부분을 활용하면 될 것으로 보았다. 아울러 그 노드 기준으로 자식 노드의 개수를 세는 건 dfs로 간단하게 구현할 수 있다. 문제 풀이 시간복잡도 : DFS를 인접리스트로 구현하였고(O(V+E)), 파인드 로직에서 최소 공통 root 노드를 찾기 위한 로직에서 트리 높이(h)가 최악의 경우 노드 개수(V)에 근사해지므로 O(V + E)이다. package ssafy.사전학습; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 출발점부터 도착점까지 이동할 때 "최단 거리"를 구해야 함 격자 공간 위에서 이동 조건이 존재 이동할 때마다 가중치(이동 시간)는 기본 1 하지만 소용돌이 구간은 가중치가 달라짐 (시간이 더 오래 걸림) n은 2 이상 15 이하 위 조건을 고려했을 때, 모든 간선의 가중치가 양수이며 최단거리를 구하는 것이므로 다익스트라로 푸는 것을 먼저 고려해봤다. 다만, 아직 다익스트라가 익숙치 않은 탓에 우선순위 큐는 사용하지 않았고, 기본적인 BFS 로직 위에 최단 거리로 각 노드를 갱신하는 로직만 추가하여 구현하였다. 이렇게 할 경우에는 다익스트라의 시간복잡도가..

해석 이 문제는 인접 리스트를 이용하여 relation group의 개수를 묻는 문제이다. 따라서 그래프 탐색을 통해 연관 노드를 한번에 방문하는 방식으로 로직을 전개하면 마을의 개수를 구할 수 있다. 보통 격자 상에서의 그래프 알고리즘이 아닌, 이 문제와 같이 인접 행렬 또는 인접 리스트를 활용하는 그래프 알고리즘의 시간복잡도는 인접 행렬과 리스트 각각 O(v^2), O(v + e)이다. 이는 아래 구현된 로직에서도 확인할 수 있다. 노드의 개수가 최대 100개라고 주어져 있으므로, 인접 행렬이든 리스트든 관련 없이 문제를 풀 순 있었을 것이다. 간선의 개수는 n(n-1)/2개라고 되어있으므로 인접 행렬로 구현하였다. 풀이 DFS package ssafy.사전학습.그래프; import java.io.B..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 해석 이 문제는 시작 노드와 끝 노드가 정해져 있는 상태에서, 최단 거리를 구하는 문제이므로 기본적으로 BFS를 이용한 그래프 알고리즘 문제일 것이라 가정하였다. 여기서 처음에 문제를 이해할 때에는 가중치가 양수라 생각했기에 다익스트라 알고리즘이 적절할 것이라 보았다. 다익스트라는 시간복잡도가 O(ElogV)이므로 N = 100인 문제에서는 문제 없다. -- 근데 나중에 생각하니, 가중치의 범위에 대한 언급이 없어서 문제가 명확하게 조건을 제시하고 있는 것 같지는 않다. 근데 출제 의도는 다익스트라 였던 것 같다. 다익스트라 알고리즘은 특정 노드를 기준으로, 이와..