문제 풀이

[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]와..

[Programmers 알고리즘, C++]#Level 2_오픈 채팅방 Programmers 알고리즘 문제 풀이, Level2_오픈 채팅방 STL 컨테이너와 String 클래스를 활용하여 풀이하는 문제입니다. 문제 풀이 1. [유저 아이디] + [닉네임] 을 묶어서 기억하기 위해 STL 컨테이너 중 "map"을 활용합니다. [Basic C++] #38_map, 연관 컨테이너 [Basic C++] #38_map, 연관 컨테이너 C++ 개발에서 표준 라이브러리(STL)의 "map"에 대해 알아보겠습니다. "전문가를 위한 C"의 16 항목, "컨테이너와 반복자 이해하기"에 해당하는 내용입니다. map, 연관 컨 webddevys.tistory.com 2. 주요 포인트는 닉네임이 변경되는 시점은 두 가지입니다. ..

[Programmers 알고리즘, C++]#Level 2_문자열 압축 Programmers 알고리즘 문제 풀이, Level2_문자열 압축 String 클래스 활용과 규칙을 찾아 풀이하는 문제입니다. 문제 풀이 1. 최대 압축 단위는 전체 길이의 1/2까지 가능합니다! 2. 압축 단위를 증가시키며(1, 2, 3...N/2) 문자열의 압축 가능 여부를 확인합니다. 3. 각 압축 단위마다 최종적으로 압축된 문자열 길이를 기억해서 비교합니다. 4. 이때, 마지막에 남아 있는 가장 작은 문자열 길이를 반환합니다. 코드 #include #include using namespace std; int solution(string s) { int len = s.size(); int answer = len; int n = ..

[Programmers 알고리즘, C++]#Level 1_키패드 누르기 Programmers 알고리즘 문제 풀이, Level1_키패드 누르기 STL 컨테이너 활용과 규칙을 찾아 풀이하는 문제입니다. 문제 풀이 먼저, "1 - 4 - 7"은 "L", 그리고 "3 - 6 - 9"는 "R"이 확정입니다. 따라서, C++가 제공하는 STL 컨테이너 중 "map"을 활용해봤습니다. key 는 키패드의 숫자로 설정하고, 미리 확정된 손을 value로 하였습니다. 예를 들면, {1, "L"}, {3, "R"}, ... etc 물론, "2 - 5 - 8 - 0"은 정해진 손이 없기 때문에 "U(Undefined)"로 value를 저장합니다. 더불어, '*', '0', 그리고 '#'은 편의상 각각 10, 11, 그리고 ..

[Programmers 알고리즘, C++]#Level1_크레인 인형 뽑기, 2차원 배열, stack, STL 컨테이너, adjacent_find() Programmers 알고리즘 문제 풀이, Level1_크레인 인형뽑기 2차원 배열의 개념과 STL 컨테이너 활용 문제 문제 풀이 문제는 스택 자료구조에대한 이해와 2차원 배열의 활용을 요구합니다. 먼저, 주어진 2차원 배열에서 탐색을 진행하고, 스택에 차례대로 "push_back" 합니다. 간단하게 stack(바구니)에 저장된 이전 항목과 현재 저장할 항목을 비교할 수 있지만, STL 알고리즘을 활용해보고자 "adjacent_find"를 사용해보겠습니다! 굉장히 간단합니다. 바로 코드를 살펴보겠습니다. * 주의할 점은 "N x N" 격자 밑에 있는 숫자는 ..

[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; ..

[BOJ 알고리즘, C++] #1181 단어 정렬 BOJ 알고리즘 문제 풀이, 15649번 문제 : N과 M(1) DFS&BFS를 이용하여 주어진 자연수 범위 내에 가능한 수열의 개수 구하기 문제 그래프 문제 풀이에 앞서, 자료 구조 중 그래프에 대해서 먼저 알아보겠습니다. 자료 구조에서 그래프란, 단순히 정점과 정점들을 연결하는 간선을 하나로 모아놓은 비선형 자료 구조입니다. 객체와 객체 간의 관계를 표현하는 자료구조로 볼 수 있습니다. 그래프 자료구조를 탐색하는 방법으로, "DFS(깊이 우선 탐색)"과 "BFS(넓이 우선 탐색)"이 있습니다. DFS 깊이 우선 탐색이란, 하나의 정점을 기준으로 모든 정점을 차례대로 방문합니다. 탐색 과정은 한 방향으로 깊이 제한(위 그림에선 2, 5, 11, 4 등의..