윤깡패 블로그

문제 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]..

세그먼트 트리(Segment Tree) 자료구조 주어진 데이터의 질의값 구하기(구간 합, 최대・최소)나 데이터 업데이트를 빠른 시간 복잡도 안에서 수행하기 위해 고안해 낸 자료구조 * 더 큰 범위는 '인덱스 트리'라고 불린다. 세그먼트 트리 종류 구간 합 A[N] = A[2N] + A[2N + 1] 최대 A[N] = max(A[2N], A[2N + 1]) 최소 A[N] = min(A[2N], A[2N + 1]) 세그먼트 트리 핵심 이론 트리 배열의 크기 2ᵏ ≥ N을 만족하는 k의 최솟값을 구한 후 2ᵏ * 2를 트리 배열의 크기로 정의 (N : 데이터의 개수) [ 예시 ] N = 8의 경우, 2³ ≥ 8 ⇒ 배열의 크기 : 2³ * 2 = 16 시작 인덱스 : 2ᵏ [ 예시 ] k = 3의 경우 시작 ..

문제 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로 선택..

이진 트리(Binary Tree) 자료구조 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리 이진 트리의 종류 편향 이진 트리 노드들이 한쪽으로 편향돼 생성된 이진 트리 - 탐색 속도가 저하되고 공간이 많이 낭비된다. 포화 이진 트리 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리 완전 이진 트리 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 이진 트리의 순차 표현 1차원 배열의 형태로 표현 트리의 노드와 배열의 인덱스 사이 상관관계 (N = 노드 개수) 루트 노드 : index = 1 부모 노드 : index = index / 2 (제약 조건 : 현재 노드가 루트 노드가 아님) 왼쪽 자식 노드 : index = index * 2 (제약 ..

문제 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..

순열과 조합 핵심 이론 순열(Permutation) : 서로 다른 n개의 숫자에서 r개를 선택하여 순서를 고려해 나열할 경우의 수 (순서 고려 O) 조합(Combination) : 서로 다른 n개의 숫자에서 서로 다른 r개를 선택하는 경우의 수 (순서 고려 X) 조합 점화식 D[i][j] = D[i - 1][j] + D[i - 1][j - 1] * , 을 참고하였습니다.

문제 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 그래프에서 깊은 부분을 우선적으로 탐색하는..