문제 풀이/BOJ 문제 풀이

[BOJ 알고리즘, C++] #15649_N과 M(1), 깊이 우선 탐색 BOJ 알고리즘 문제 풀이, 15649_N과 M (1) 깊이 우선 탐색을 통해 중복이 없는 수열의 개수를 구합니다. # 문제 # 풀이 1. 깊이 우선 탐색(DFS) 루트 노드 혹은 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색하는 방법입니다. 2. DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태이다. 어떤 노드를 방문했었는지 방문 여부를 반드시 검사해야 합니다. 너비 우선 탐색보다 간단합니다. 검색 속도 자체는 너비 우선 탐색에 비해 느립니다. 3. 예제 0번 노드를 시작으로 깊이 우선 탐색을 시작합니다. 0번과 인접한 노드들을 순차적으로 순회합니다. 0번과 인접한 1번 노드를 방문합니다...

[BOJ 알고리즘, C++] #10816_숫자 카드 2, lower_bound, upper_bound BOJ 알고리즘 문제 풀이, 10816_숫자 카드2 정렬 알고리즘을 통해 주어진 숫자 카드가 존재하는지 탐색합니다. 문제 풀이 1. Map 컨테이너 활용 // 1. Map 컨테이너를 활용했지만, 2번 코드보다 소요 시간과 메모리 사용량이 비교적 훨씬 높음... #include #include #include typedef long long ll; using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; // 숫자 + 개수 map m; vector v; cin >> N;..

[BOJ 알고리즘, C++] #10815_숫자 카드, 이진 탐색, Binary Search BOJ 알고리즘 문제 풀이, 10815_숫자 카드 이분 탐색을 통해 주어진 숫자 카드가 존재하는지 탐색합니다. Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 이진 탐색(Binary Search) Details [정의] : 정렬된 원소 목록을 반으로 나누어 찾고자 하는 원소와 중심이 되는 원소를 비교하고, 작다면 왼쪽으로 크다면 오른쪽으로 중심 원소를 옮겨서 반복적으로 비교 작업을 수행합니다. 시간 복잡도는 O(log n)으로 선형 탐색보다 뛰어난 성능을 보여줍니다! 다만 몇 가지 단점들이 물론 존재합니다! [특징] : 정렬 상태의 자료구조에서만 가능합니다. 그리고, 연결 리스트에서 사용이 힘듭니다...

[BOJ 알고리즘, C++] #1008_C++ A/B, 부동 소수점, precision(), fixed BOJ 알고리즘 문제 풀이, 1008_A/B 나누기 값을 주어진 부동소수점 자리까지 출력하기 문제 풀이 1. stdio 사용 #include int main() { double a; double b; scanf("%lf, %lf", &a, &b); printf("%.13lf", a / b); return 0; } 2. iostream 활용 // 1. std::cout.precision(n) : 실수 전체 자리수를 n까지 표현 double a = 3333.333333; std::cout.precision(6); cout

[BOJ 알고리즘, C++] #25305_커트라인, 정렬 알고리즘, STL, 내림차순 BOJ 알고리즘 문제 풀이, 25305_커트라인 STL이 제공하는 정렬 알고리즘을 통해 커트라인 바로 위 점수를 출력하는 문제 문제 풀이 [Basic C++] #32-3_STL 정렬 알고리즘 [Basic C++] #32-3_STL 정렬 알고리즘 C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다. "전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다. 정렬 알고리즘 webddevys.tistory.com // greater() : 내림차순 정렬 // less() : 오름차순 정렬, Default sort ( begin(v), end(v), less() or greater..

[BOJ 알고리즘, C++] #11050_이항 계수 1, 이항 계수 공식, 재귀 문 활용 BOJ 알고리즘 문제 풀이, 11050_이항 게수 1 이항 계수 공식을 재귀문을 구현하는 문제 문제 풀이 1. 이항 계수 공식 ( N ) ( K ) = N! / ( K! (N - k)! ) 2. 팩토리얼 재귀문 int Factorial( int num ) { if(n == 0 || n == 1) return 1; else return num * Factorial(num - 1); } 결과 코드 #include using namespace std; int N, K; // 재귀문을 활용한 Factorial 구현 int Factorial(int num) { if(num == 0 || num == 1) return 1; e..

[BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법 BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 공배수를 구하는 문제   문제 풀이 1. 유클리드 호제법A = 106, B = 161.C = A % B = 106 % 16 = 10A 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다.A와 B를 나눈 나머지 값을 R이라고 한다면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다!이 성질을 이용하여, B(혹은 Determinant)를 이전의 나머지 값으로 나누는 작업을 반복합니다.최종적으로, 나머지 값이 0이 되었을 때, "마지막 B" 값이 A와 B의 최대 공약수..

[BOJ 알고리즘, C++] #11660_구간 합 구하기 5 BOJ 알고리즘 문제 풀이, 11660_구간 합 구하기 5 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 1. 먼저, 2차원 배열의 누적합을 "열" 순으로 누적 합을 계산하는 것이 아니라, "행" 순으로 계산해야 합니다. 2. 누적 합을 계산하는 방법은 아래와 같이 "[i-1][j] + [i][j-1] - [i-1][j-1]"입니다. prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] "행"을 기준으로 누적 합을 계산하다 보면 "중복"으로 누적된 값이 존재합니다! 위 그림을 살펴보면, prefixSum[4]를 위해 prefixSum[2]와..

[BOJ 알고리즘, C++] #2559_수열의 최대 구간 합, 누적 합 알고리즘 BOJ 알고리즘 문제 풀이, 2559_수열 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 수열 중 주어진 구간 중 최대 합을 찾는 문제입니다. 앞서 살펴봤던 11659번 문제와 풀이 과정이 같습니다(아래 링크를 참조하세요) [BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘 [BOJ 알고리즘, C++] #11659_구간 합 구하기 4, Prefix Sum(누적 합) 알고리즘 BOJ 알고리즘 문제 풀이, 11659_구간 합 구하기 4 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 과정 위 문 webddevys.tistory.com 먼저, 입력받은..

[BOJ 알고리즘, C++] #11659_구간 합 구하기 4, Prefix Sum(누적 합) 알고리즘 BOJ 알고리즘 문제 풀이, 11659_구간 합 구하기 4 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 과정 위 문제를 해결하기 위해 우리는 누적 합 알고리즘 두 가지를 선행할 필요가 있습니다. 1. 구간 합 (Prefix Sum) 2. 투 포인터(Two Pointers) Prefix Sum, 구간 합 /* 1. Prefix Sum을 계산하여 배열에 저장합니다. 2. i(left bound) ~ j(right bound) 구간의 합은 array[r] - array[l-1] 입니다. */ #include using namespace std; constexpr size_t n = 5; ..