Next Permutation ? 다음 순열이란, 말 그래도 해당 숫자의 다음에 올 순열의 수를 의미한다. 123 -> 132, 132 -> 213, 213 -> 231 ... 와 같다. 그렇다면 우리는 123의 다음 순열인 132를 구하는 과정을 살펴보겠다. 1. 해당 수의 맨 오른쪽부터 왼쪽으로 차례대로 $ i $ > $  i -1 $  이고, $ A_{i} $ > $ A_{i-1} $인 수를 찾는다.$ ( $$ i $는 인덱스 번호, $ A_{i} $는 해당 자리의 값$ ) $  2. 두 수 분리하기. 찾은 두 수를 막대를 하나 긋고, 임의로 왼쪽, 오른쪽으로 분리시킨다. 3. 왼쪽 공간의 가장 오른쪽 숫자에 대하여 오른쪽 공간의 우측 끝 부분 부터 왼쪽으로 탐색하면서, 더 큰 수를 찾는다.  4...

이 글은 https://movingbean.tistory.com/17 의 블로그에서 작성된 내용을 바탕으로 정리 + @한 글입니다. 누적 합에 대한 내용이 너무 잘 정리되어 있습니다!!!!!! 꼭 보시길 바랍니다. 1차원 공간 vs 2차원 공간점 업데이트 vs 구간 업데이트 점 쿼리 vs 구간 쿼리 (특정 위치에 대한 개수만을 묻는가? vs 어떤 구간의 총합을 묻는가?)오프라인 쿼리 vs 온라인 쿼리 (질문을 업데이트가 모두 끝나고 하는가? vs 업데이트 도중에 질문을 하는가?1. 1차원 공간, 점 업데이트, 오프라인 쿼리점 업데이트라는 것은 초기 값만 세팅하는 경우도 점 오프라인으로 볼 수 있다고 한다. 가장 기본적으로 누적 합(PrefixSum)을 구하는 것을 떠올릴 수 있다.  시간 복잡도는 누적 ..

그래프(Graph)정점과 간선의 집합으로 구성되는 자료구조  방향 그래프간선에 방향이 있는 그래프A정점에서 B정점으로 향하는 간선과 B정점에서 A정점으로 향하는 간선이 서로 다를 수있다.무방향 그래프간선에 방향이 없는 그래프A-B를 연결하는 간선이 동일한 간선이다.가중치 그래프간선에 가중치(weight) 혹은 비용(cost)이 할당된 그래프연결된 정점들 간 탐색에 드는 비용이나, 연결 강도 등을 표현  그래프 표현 방법인접 행렬일반적으로 2차원 배열을 이용해서 표현adj[행][열] = 연결여부(or 가중치)공간 복잡도V개의 정점이 있다면, V*V 만큼의 공간을 사용한다.시간 복잡도연결관계(가중치) 조회/저장 : O(1)한 정점에 연결된 모든 간선 조회 : O(V)A와 B를 잇는 간선 존재 여부 확인 : ..

모노토닉 스택 (Monotonic Stack) 원소가 Increasing / Decreasing으로 정렬되어 있는 배열을 의미한다. 정렬되어 있지 않은 배열을 Monotonic 하게 만들거나 Monotonic Stack에 새로운 원소가 입력되었을 때, 정렬하는 과정에서 발생하는 정보들이 유용하다. 추천 문제 [백준] 옥상 정원 꾸미기 : https://www.acmicpc.net/problem/6198 [백준] 오큰수 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acm..

소수 판별 알고리즘 1. 1과 자기 자신을 제외한 나머지 수 중에서 약수가 있는 -> 시간 복잡도 O(n) 1을 제외한 2부터 n-1까지 탐색하면서 i로 나누어 떨어지는 수가 있는지 확인 static boolean isPrime(int N) { if (N < 2) return false; for (int i=2; i 시간 복잡도 : O(루트 n) 만약 N이 12라 할때, 12의 제곱근은 약 3.46이다. 12의 약수는 1, 2, 3, 4, 6, 12 이다. 여기서 1과 12를 제외했을 때 이는 2 * 6, 3 * 4, 4 * 3, 6 * 2의 결과이다. 따라서 N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수판별을 할 수 있다. static boolean prime(int n) { if(..

최소 공배수 import java.util.*; public class Main { private static int gcd(int a, int b) { if (a == 0) return b; return gcd(b%a, a); } private static void lcm(int a, int b) { System.out.println(a / b); } public static void main(String[] args) { // 여기에 코드를 작성해주세요. Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); lcm(n*m, gcd(n,m)); } } 최대 공약수 import java.util.*; public ..

https://www.acmicpc.net/problem/1068 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다www.acmicpc.net import syssi = lambda : sys.stdin.readline().rstrip()l = lambda : list(map(int, si().split()))def dfs(root) : # x의 subtree에 대해 leaf[x]를 계산해주는 함수 if not child[root] : # 아무것도 없다면 리프노드 leaf[root] = 1 for node in ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net 트리의 지름은 DFS 두 번으로 O(N)의 시간 복잡도로 구현이 가능하다.트리에서 아무 노드나 잡고 그 노드에 대한 먼 노드를 구하고 이 노드를 n1이라고 하자.n1에 대한 가장 먼 노드를 한번 더 구한다. 이 노드를 n2라고 하자.이제 n1과 n2의 거리가 트리의 지름이 된다.import sys, heapqfrom collections import dequesi = sys.std..

https://leetcode.com/problems/reverse-linked-list-ii/description/ LeetCode - The World's Leading Online Programming Learning PlatformLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.leetcode.com /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * Li..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net package Data_Structure.union_find; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; class Edge implements Comparable { int v1; int v2; int ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net import sys from collections import deque si = sys.stdin.readline def topology_sort() : q = deque([]) for i in range(1,n+1) : if indegrees[i] == 0 : q.append(i) dp[i] = times[i] while q : cur = q.popleft() for x in graph[..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import collections import sys from heapq import heappop, heappush si = sys.stdin.readline INF = float('inf') n,m,x = map(int,si().split()) graph = [[] for _ in range(n+1)] for _ in range(m) : u,v,w = map(in..