키베이루's diary

sort, unique, erase를 사용해서 중복을 제거할 수 있다. unique : 인접한 중복된 요소가 있을 경우, 뒤에서 부터 제거 하고 나머지 요소의 첫번째 인덱스를 반환한다. ex) { 1, 1, 2, 2, 3, 3 } -> { 1, 2, 3, 2, 3, 3 }, index = 3 반환 (3부터 중복이 없기 때문) int main() { vector v{ 1,3,2,2,1,3 }; sort(v.begin(), v.end()); // 인접한 요소에서 중복을 제거하기 때문에 정렬 해야함 for (auto i : v) { cout

1. 최대 공약수 int gcd(int a, int b) { int n; while (b != 0) { n = a % b; a = b; b = n; } return a; } 2. 최소 공배수 int lcm(int a, int b) { return a * b / gcd(a, b); } ex) https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net #include #include #include #include #include #include using namespace std; int gcd(int a, ..

1) 문제설명 2) 아이디어 입력받은 문자들중 "."은 -1로 "c"는 0으로 다시 배열에 할당하여 0이 니왔을 때 순차적으로 숫자를 증가시키는 단순한 구현 문제이다. 3) 코드 // Algo.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다. // #include #include #include #include using namespace std; int h, w; char str[101][101]; int arr[101][101]; int cnt = 1; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> h >> w; for (int i = 0; i < h; i++) { for (..

1) 문제설명 https://www.acmicpc.net/problem/14246 14246번: K보다 큰 구간 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오. www.acmicpc.net 2) 아이디어 presum(누적합)을 이용하여 presum배열에 누적된 합을 저장하고 그것을 이용해서 구간의 합을 구한다. 구간의 합이 K보다 큰 경우에만 while문을 진입하여 k보다 큰 쌍의 개수를 +1 한다. ★ 실행이 O(n^2)이 되지 않게 구현해야한다. 3) 코드 #include #include #include #include using namespace std; long long presum[100001]; long long..

1) 문제설명 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 2) 아이디어 이전에 설명한 조합과 순열을 사용해서 문제를 해결하였다. 입력된 배열을 오름차순으로 정렬한뒤 순열 : 9명의 난쟁이의 키를 입력받고 이를 순열로 인덱스를 바꾸면서 도는동안 난쟁이들의 키의 합이 100이 될 경우 반복문을 멈추고 그대로 앞에 저장된 배열을 출력하였다. 조합 : 2중 for문을 돌면서 난쟁이의 키의 합에서 가짜 난쟁이 2명을 빼고 그 인덱스를 저장한뒤 다시 for문..

조합은 순서가 없이 몇개를 뽑느냐의 갯수를 샐떄 쓰인다. nCr : n명중에 r명을 고른다. = nCr = n! / r!(n-r)! C++에서 이를 재귀 or 반복문으로 표현할 수 있다. 재귀버전 int n = 5, k = 3, arr[5] = { 1,2,3,4,5 }; void print(vector v) { for (int i : v) { cout

합병정렬은 분할 정복(Divide and Conquer)의 알고리즘의 하나이다. 합병정렬의 핵심은 3가지이다. Divide : 입력된 배열을 절반 씩 계속 나눈다. void merge_sort(int left, int right, int[] arr) // 나눠! { // 왼쪽이 오른쪽보다 작을때만 실행하고 // 왼쪽이 오른쪽과 같아지거나 커질경우 재귀가 풀리면서 merge가 실행된다. if (left < right) { int mid = (left + right) / 2; // 처음과 끝을 반으로 갈라서 (처음 ~ 중간) / (중간 ~ 끝) merge_sort(left, mid, arr); // 처음부터 중간까지 나눈다 merge_sort(mid + 1, right, arr); // 중간부터 마지막 까지..

1) 문제설명 2) 아이디어 가로/세로 인접한 글자가 다를 때마다 바꾸고 인접한 문자의 개수를 센다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int n; char arr[51][51]; int check() { // 가로 세로 중복확인 함수 int maxt = 0; int v1_cnt = 0, h1_cnt = 0; for (int i = 0; i < n; i++) { int v_cnt = 0, h_cnt = 0; // 가로 중복확인 for (int j = 0; j < n; j++) { if (arr[i][j] == arr[i][j + 1]) { v_cnt++; } el..