백준

[1722번] 순열의 순서 구하기(수학, 구현)

1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 분석 4! = 24 3! = 6 2! =2 1! =1 제일 앞 자리에 사용할 수 있는 숫자 경우의 수 4가지, 다음 3가지, 다음 2가지, 다음 1가지 ➔ N자리의 수로 만들 수 있는 순열의 모든 경우의 수 N! 1. K번째 순열 출력 1) 로직 1. 주어진 값(K)과 현재자리(N) -1에서 만들 수 있는 경우의 수를 비교 2. 1에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킴(순열의 순서를 1씩 늘림) 3. K가..

[2042번] 구간합 구하기 (세그먼트 트리, 리프노드, 값 변경)

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 1. 트리 초기화하기 ➔ setTree(idx) 트리 크기(treeSize) = 2^(K+1) ..

[11438번] 최소 공통 조상 구하기 (트리, 제곱수 LCA, LCA 시간초과)

11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 분석 최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과) 최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식 karla.tistory.com 풀이 """ 두 노드 쌍 M개 LCA 구하기 노드의 개수 N(2~100,000) N-1줄 트리상 연결된 두 노드 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 ..

[11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드)

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 시작점 X 모든 노드간에 최단 경로 탐색 시간복잡도 O(V³) 안좋음 ➡️ 노드의 개수 100~200까지 사용 가능 문제 유형 시작점이 없고 모든 도시간의 최단거리, 모든 도시 100개 이하 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 원리 리스트를 선언하고 초기화하기 최단 거리 리스트에 그래프 데이터 저장하기 점화식으로 리스트 업데이트하기 더보기 [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 ..

[11003번] 최솟값 찾기 (슬라이딩 윈도우, 덱)

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 분석 일정 법위에서 최솟값을 찾는 문제 : 슬라이딩 윈도우/ 정렬 정렬 N과 L의 범위가 5,000,000인 문제에서 정렬 사용 불가 슬라이딩 윈도우 덱으로 구현하여 정렬 효과 i-L+1 ~ i 까지 이므로 윈도우 크기는 L로 생각 예시 N: 12, L : 3, A: 1 5 2 3 6 2 3 7 3 5 2 6 1. 새 노드 (3,2)가 저장될 때 뒤에서부터 비교 시작 : (2,5)는 (3,2)보다 숫자가 크므로 덱에서 제거 (최솟값..