문제 풀이

[BOJ알고리즘, C++]#1676_팩토리얼의 0의 개수, 소인수분해 BOJ 알고리즘 문제 풀이, 1676_팩토리얼의 0의 개수 소인수분해의 성질을 이용해 N! 의 뒷자리 0의 개수를 구합니다. 문제 풀이 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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9..

[BOJ 알고리즘, C++] #11051_이항 계수 2, 파스칼의 삼각형 BOJ 알고리즘 문제 풀이, 11051_이항 계수 2 이항 정리와 동적 계획법을 통해 이항 계수를 구합니다. 문제 풀이 이항 정리 : N! / K!(N - K)! 첫 번째 조건, C(N - 1, K - 1) = C(N - 1, K) 두 번째 조건, N = 0 일 때, C(N, K) = 0입니다. 세 번째 조건, K = 0 일 때, C(N, K) = 1입니다. DP [ N ] [ K ], 이차원 배열을 통해 동적 계획법을 활용하면 문제를 푸는 것은 그다지 어렵지 않습니다. 코드 /* 문제: C(N,K) % 10007 결과 출력 설명: 1. N! / K!(N-K)! 2. 파스칼의 삼각형 or 파스칼 공식 이용 3. C(N-1, K-1)..

[BOJ 알고리즘, C++] #1764_듣보잡, Set BOJ 알고리즘 문제 풀이, 1764_듣보잡, Set 문제 Set 컨테이너를 활용해 두 집합의 중복 원소를 선별합니다. 문제 풀이 이 문제도 역시 Set 컨테이너를 활용하면 간단하게 풀 수 있는 문제입니다. 먼저, 입력으로 받은 문자열이 이전에도 입력으로 들어왔는지, 즉 중복된 문자열이 들어왔는지 체크하기 위해 Set 컨테이너에 선제적으로 문자열들을 삽입합니다. 중복되는 문자열일 경우 별도의 Vector 컨테이너를 생성해 항목들을 삽입합니다. "사전순으로 나열하라" 조건을 충족하기 위해 Vector 컨테이너의 정렬을 수행하고 답을 출력합니다! 코드 #include #include #include #include #include using namesp..

[BOJ 알고리즘, C++] #1269_대칭 차집합, Set BOJ 알고리즘 문제 풀이, 1269_대칭 차집합, Set Set 컨테이너를 통해 두 집합의 대칭 차집합을 구합니다. 문제 풀이 Set을 활용하면 아주 간단하게 풀 수 있는 문제입니다. 두 개의 집합 간 서로 중복되지 않는 원소들의 개수를 구합니다. Set 컨테이너는 항목들 간 중복을 허용하지 않습니다. 이러한 특징을 염두에 두고 풀이합니다. 코드 #include #include #include // find()를 활용하기 위해 헤더를 추가합니다. typedef long long ll; using namespace std; int main() { int N, T; set s; cin >> N >> T; int set1Num = N; int se..

[BOJ 알고리즘, C++] #11478_서로 다른 부분 문자열, Set BOJ 알고리즘 문제 풀이, 11478_서로 다른 부분 문자열 문제 Map 컨테이너를 활용하여 문자열이 갖는 총 부분 문자열을 계산합니다. 문제 풀이 Set 컨테이너를 사용하면 아주 간단하게 풀 수 있는 문제입니다. Set 컨테이너의 특징을 간략하게 설명하자면, 중복이 없는 "Key" 값을 원소로 갖는 자료구조입니다. Map과 달리 Set은 Key 값이 곧 Value이며, 간단하게 풀이하면, 중복 없는 항목들을 갖는 컨테이너로 볼 수 있습니다. 코드 #include #include #include using namespace std; // Set 사용 int main() { string str; set s; cin >> str; s..

[BOJ 알고리즘, C++] #14425_문자열 집합, Map BOJ 알고리즘 문제 풀이, 14425_문자열 집합 문제 Map 컨테이너를 활용하여 집합에 속해있는 문자열을 선별합니다. 문제 풀이 Map 컨테이너 자료구조를 활용하는 아주 간단한 문제입니다. 먼저, map 을 선언하고, 집합 S에 해당하는 문자열을 Key - 간단한 Boolean 변수를 Value로 삽입합니다 다음으로, 주어진 문자열을 Key로 Map 컨테이너에서 탐색을 진행하는 방향으로 구현했습니다. 이때, "operator []" 는 Map에 없는 새로운 "Key"값으로 수행하면 임의의 Value가 삽입되기 때문에, 집합 S의 문자열들은 모두 "true" 변수와 짝지어 놓도록 합니다! 코드 #include #include #include..

[Programmers 알고리즘, C++]#Level 2_다음 큰 숫자 Programmers 알고리즘 문제 풀이, Level 2_다음 큰 숫자 bitset을 활용한 이진 변환과 cmath 헤더 파일을 활용한 알고리즘 문제 풀이 1. bitset을 활용한 이진법 변환 Convert a Decimal to Binary in C++ | Techie Delight This post will discuss how to convert a decimal to binary in C++... The standard solution to convert a number to its binary format in C++ is using std::bitset. www.techiedelight.com 주어진 입력 값은 최대 1,..

[BOJ 알고리즘, C++] #14889_스타트와 링크, DFS, 깊이 우선 탐색 BOJ 알고리즘 문제 풀이, 14889_스타트와 링크 깊이 우선 탐색을 통해 차이 값이 최소가 되는 두 배열을 구합니다. 문제 풀이 1. 깊이 우선 탐색 알고리즘 활용 [BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색 [BOJ 알고리즘, C++] #15649_N과 M(1), 깊이 우선 탐색 BOJ 알고리즘 문제 풀이, 15649_N과 M (1) 깊이 우선 탐색을 통해 중복이 없는 수열의 개수를 구합니다. 문제 풀이 1. 깊이 우선 탐색(DFS) 루트 노드. webddevys.tistory.com 2. 풀이 깊이 우선 탐색을 통해 각 정점(각 선수)을 방문합니다. 더불어, 루트 노드를 시작으로 인접 노드들..

[BOJ 알고리즘, C++] #9663_N-Queen 문제, 백 트래킹 BOJ 알고리즘 문제 풀이, 9663_N-Queen 문제 백 트래킹을 통해 같은 행 혹은 대각선에 Queen이 위치하는지 확인합니다. 문제 풀이 1. 백 트래킹 깊이 우선 탐색을 기반한 알고리즘으로 "후보 해"의 집합에서 "최적해" 집합을 찾아내는 알고리즘입니다. 먼저, 깊이 우선 탐색은 트리 구조를 기반으로 수행되는 알고리즘입니다. 반면, 백 트래킹 알고리즘은 "조건"에 맞지 않는 정점 혹은 브랜치에 대한 "DFS"를 진행하지 않습니다! 정리하자면, "백트래킹 알고리즘 = DFS + 특정 조건"이라고 볼 수 있겠습니다! 2. 백트래킹 알고리즘의 대표 문제, N-Queen 문제 N x N 체스판에서 퀸들이 서로 공격할 수 없도록 배치..

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