728x90 전체 글140 lower_bound, upper_bound lower_bound & upper_bound std::lower_bound - cppreference.com std::upper_bound - cppreference.com Definition lower_bound : 찾고자 하는 값 이상의 수가 처음으로 나오는 곳의 index를 구할때 사용 upper_bound : 찾고자 하는 값보다 큰 수가 처음으로 나오는 곳의 index를 구할때 사용 How to use Binary search를 기반으로 탐색되므로, 탐색되는 vector 혹은 list 는 sort 되어있어야 한다. lower_bound, upper_bound는 구하고자 하는 곳의 iterator를 return 한다. 따라서 실제로 사용할 경우 구한 lower_bound 혹은 upper_bound.. 2021. 2. 4. 백준 No.11049 [행렬 곱셈 순서] Baekjoon Online Judge No.11049 [행렬 곱셈 순서] Problem 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 7.. 2021. 2. 4. Monge array (Monge matrix) Monge array (Monge matrix) Definition 아래와 같은 조건을 갖는 m-by-n matrix 이다. 의 조건에 대해서 를 만족하는 matrix 를 Monge array 혹은 Monge matrix 라고 한다. Example 위 사진을 보면 Monge array 의 정의를 직관적으로 볼 수 있다. 표시해둔 보라색, 연두색 점들로 예를 들어보자. 이 점들의 i, j, k, l 은 다음과 같다. i = 2 j = 3 k = 4 l = 5 A[2, 3] + A[4, 5] 2021. 2. 3. 백준 No.1912 [연속합] Baekjoon Online Judge No.1912 [연속합] Problem 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int N; vector nums; void input() { cin >> ::N; nums.assign(N, 0); for (int i = .. 2021. 2. 2. Programmers [가장 큰 정사각형 찾기] Programmers [가장 큰 정사각형 찾기] Problem 코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; int solution(vector board) { int width = board[0].size(); int height = board.size(); int answer = 0; for (int i = 0; i 2021. 2. 1. power 함수 구현 (분할 정복 이용) // Devide and Conquer algorithm 을 통한 power 함수의 구현. What is power function? Code 1 2 3 4 5 6 7 8 9 10 typedef unsigned long long ull; ull power(int num, int jisu) { if (!jisu) return 1; // num^0 = 1 이므로 if (jisu % 2) return (power(num, jisu - 1) * num) % p; ull half = power(num, jisu / 2) % p; return (half * half) % p; } Colored by Color Scripter cs Additional explanation 사실, 혹은 헤더파일에 있는 pow(a, n.. 2021. 1. 29. Pascal's triangle (파스칼의 삼각형) // Pascal's triangle What is Pascal's triangle? 좌측의 수식과 같은 이항계수의 값을 구할 때 사용할 수 있다. 하지만 아래 설명을 보면 알 수 있듯 점화식을 활용한 Dynamic Programming의 알고리즘을 사용하는 형태로, n의 값이 상당히 커진다면 사용하기 곤란한 알고리즘이다. n의 값이 상당히 커졌을 경우에는 Lucas Theorem (뤼카의 정리) 를 사용하면 된다. Explanation 위 파스칼의 삼각형을 나타낸 피라미드 모양의 그림에 연두색 값들은, 위에 있는 두 블록의 값의 합과 같다. 또한 양 변들은 nC0, nCn 이 되므로 값이 1이 된다. 이는 이항계수의 성질로서 증명이 된다. Dynamic Programming으로 C[n][k] 와 같은 .. 2021. 1. 28. Lucas's theorem (뤼카의 정리) // Lucas's theorem What is Lucas's theorem? 를 구하는 과정에서 n의 값이 상당히 클 경우 사용하면 유용한 정리이다. n의 값이 적당하다면, n!, ( n-k )!, k! 의 값을 각각 구하여 연산하면 되지만, n의 값이 10억만 되더라도 unsigned long lnog에 조차 담을 수 없게 된다. 이때 뤼카의 정리를 이용할 수 있다. Theorem 먼저, n과 k를 p진법의 전개식으로 나타내보자. 이때, 다음의 합동식이 성립한다. Example 따라서 아래와 같이 나타낼 수 있다. 따라서 답은 0이 된다. Proof // 아직 작성중인 글 입니다.. 2021. 1. 27. 백준 No.2603 [색종이 만들기] // Baekjoon Online Judge No.2630 [색종이 만들기] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #define DEVIDING_STANDARD 2 using namespace std; int N; vector paper; // 1 is blue, 0 is white int blue = 0; int white = 0; void DC(int len, int x, int .. 2021. 1. 24. 백준 No.2447 [별 찍기 - 10] // Baekjoon Online Judge No.2447 [별 찍기 - 10] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #include #include using namespace std; vector map; void solve(int n, int x, int y) { if (n == 1) { map[x][y] = '*'; return; } // cout 되는것이 아닌 map 에 입력을 하는 것. int div = n / 3; for (int i = 0; i num; map.assign(num, vector(num, ' ')); s.. 2021. 1. 24. 백준 No.10757 [큰 수 A+B] // Baekjoon Online Judge No.10757 [큰 수 A+B] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include using namespace std; int main() { string A, B; bool AisLonger = false; bool BisLonger = true; cin >> A; cin >> B; int maxLen = B.length(); int minLen = A.length(); if (A.length().. 2021. 1. 5. C++ Queue Container // Queue Container What is Queue Container? 선입선출(FIFO : First - In, First - Out)의 원리에 따라 객체의 삽입 및 삭제를 수행하는 자료의 저장 공간이다. ※ 선입선출 이란? 말 그대로 저장 공간에 먼저 들어간 데이터의 값이 먼저 나오는 형태를 말한다. 비유를 하자면, 휴지심같이 위아래가 뚫린 원기동 모양의 통이 있다고 할때 이 원통 위로 계속해서 테니스 공을 넣으면 원통의 아래 부분으로 공이 빠져나올 것이다. 또한 먼저 넣은 테니스 공이 아래로 먼저 나올것이다. 이러한 원리라고 생각하면 된다. How to use queue의 선언 #include // queue 헤더파일 내에 있다. using namepsace std; // queue는 std.. 2020. 12. 18. 백준 No.10844 [쉬운 계단 수] // Baekjoon Online Judge No.10884 [쉬운 계단 수] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include using namespace std; int N; int main() { cin >> N; vector SN; SN.assign(10, vector(N + 1, 1)); SN[0][1] = 0; for (int i = 2; i 2020. 11. 18. 백준 No.1932 [정수 삼각형] // Baekjoon Online Judge No.1932 [정수 삼각형] Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include using namespace std; vector tri; vector ground; int main() { int N; cin >> N; tri.assign(N + 1, vector(N + 1, -1)); ground.assign(N + 1, 0); for (int i = 1; i tri[i][j]; } } ground[1] += tri[1][1.. 2020. 11. 16. Greedy algorithm (탐욕 알고리즘) // Greedy algorithm What is Greedy algorithm? 답을 하나씩 골라가는데, 미리 정해놓은 기준에 따라 매번 가장 좋아 보이는 답을 선택하는 것이다. 하지만 을 이용하여 설계를 한다면 항상 최적의 해는 보장할 수 없다. Example 의 예시로 가장 많이 보여지는 것들 중 하나인 "거스름돈 문제"를 예시로 들어보자. "거스름돈 문제"란, 임의의 액수만큼 거스름돈을 주어야 하는데 최소한의 개수의 동전을 사용하여 주어야 할 때 해당되는 동전들을 고르는 문제이다. 예를 들어 만약 거스름돈으로 520원을 주어야 한다. 이때 520원을 줄 수 있는 방법은 다양하다. 하지만 상식적으로 10원짜리 동전 52개로 거슬러주는 것보단 500원짜리 동전 1개와 10원짜리 동전 2개로 거슬러주는.. 2020. 11. 10. 이전 1 ··· 6 7 8 9 10 다음 728x90
