윤깡패 블로그

문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 1. sort() 함수로 배열 정렬 ⇒ 시간 복잡도 O(nlogn) 2. 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾는다. ⇒ 정렬 전 index - 정렬 후 index의 최댓값 + 1 * 1 : swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 정렬..

문제 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 풀이 0. 자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산 1. K번째 순열 출력하기 ① 주어진 값(K)과 현재 자리(N) - 1에서 만들 수 있는 경우의 수를 비교한다. ② ①에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다(순열의 순서를 1씩 늘림). ③ K가 더 작아지면 순열에 값을 저장하고 K를 K - (경우의 수 * (c..

문제 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 풀이 점화식 정의 D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 L개, 오른쪽에서 R개가 보일 때 가능할 경우의 수 점화식 도출 : 가장 작은 빌딩 배치 D[N - 1][L - 1][R] : N - 1개의 빌딩에서 왼쪽에 빌딩을 추가할 때 왼쪽 빌딩이 1개 증가 D[N - 1][L][R - 1] : N -1개의 빌딩에서 오른쪽에 빌딩을 추가할 때 오른쪽 빌딩이 1개 증가 D[N - 1]..

문제 https://www.acmicpc.net/problem/13251 13251번: 조약돌 꺼내기 첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. www.acmicpc.net 풀이 조합(Combination) 알고리즘 조합(Combination) 알고리즘 순열과 조합 핵심 이론 순열(Permutation) : 서로 다른 n개의 숫자에서 r개를 선택하여 순서를 고려해 나열할 경우의 수 (순서 고려 O) 조합(Combination) : 서로 다른 n개의 숫자에서 서로 다른 r개를 선택 soobin0821.tistory.com 코드 #include #include using namespace std; int main() { ios::sync_wi..

문제 https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 풀이 a와 z로 만들 수 있는 모든 경우의 수 = N + M개에서 N개를 뽑는 경우의 수 = N + M개에서 M개를 뽑는 경우의 수 조합 점화식 D[i][j] = D[i - 1][j] + D[i - 1][j - 1] 문자 선택 기준 (T : 현재 자릿수에서 a를 선택했을 때 남은 문자로 만들 수 있는 모든 경우의 수) T ≥ K : 현재 자리 문자를 a로 선택 T < K : 현재 자리 문자를 z로 선택..

문제 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 풀이 1. 정방향 위상 정렬 수행 시작점 : 출발 도시 각 도시와 관련된 임계 경로 저장 2. 역방향 위상 정렬 수행 시작점 : 도착 도시 현재 임계 경로값 + 해당 도로값 == 이전 도시의 임계 경로값 ⇒ 1분도 쉬지 않고 달려야 하는 도로로 저장 위상 정렬(Topology Sort) 알고리즘 위상 정렬(Topology Sort) 알고리즘 위상 정렬(Topolog..

문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리까지 재귀 함수 형태로 탐색 ⇒ DFS의 형태로 탐색 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 탐색 알고리즘 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘 DFS(깊이 우선 탐색) 알고리즘 * DFS : Depth-First Search 그래프에서 깊은 부분을 우선적으로 탐색하는..

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 풀이 유니온 파인드(Union-Find) 알고리즘 유니온 파인드(Union-Find) 알고리즘 유니온 파인드(Union-Find) 알고리즘 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 + 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 유니온 파인드 알고리즘 핵심 이론 union 연 soobin0..

문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 투 포인터 이동 원칙 - A[i] + A[j] > K : j--; - A[i] + A[j] < K : i++; - A[i] + A[j] == K : count++; 프로세스 종료 투 포인터 알고리즘 투 포인터 알고리즘 투 포인터 알고리즘 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 투 포인터 알고리즘을 활용하여 2개의 그룹을 병합하는 과정 - 시간 복잡도 : O(N + M) (N, M : 정렬된 배열 A와..

문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 합 배열 공식 : S[i] = S[i - 1] + A[i] 구간 합 공식 : S[j] - S[i - 1] [코딩/알고리즘] - 구간 합 알고리즘 구간 합 알고리즘 구간 합 알고리즘 연속적으로 나열된 수가 있을 때, 맨 앞부터 특정 위치까지의 합을 미리 구해 놓고 사용하는 알고리즘 시간 복잡도 - O(1) 구간 합 핵심 이론 합 배열 S를 만드는 공식 S[i] = ..