개발일지

문제설명 입출력 예제 개념 최소 공배수를 찾는 문제다. 입력 A와 B에 대하여 두 수의 최소 공약수를 구하고, A * B / 최소 공약수를 하면 최대 공배수를 구할 수 있다. (유클리드 호제법) 풀이 #include int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } int main() { long long int A, B, gcd; std::cin >> A >> B; gcd = GCD(A, B); std::cout

문제설명 입출력 예제 개념 문자열 S에 대해 서로 다른 부분 문자열의 개수를 구하는 문제다. 여기서 연속된 일부분이라는 것에 주목해야 한다. 즉, S의 길이가 1인 부분 문자열은 a, b, a, b, c가 되고, 여기서 서로 다른 부분 문자열은 a, b, c S의 길이가 2인 부분 문자열은 ab, ba, ab, bc가 되고, 여기서 서로 다른 부분 문자열은 ab, ba, bc S의 길이가 3인 부분 문자열은 aba, bab, abc가 되고, 여기서 서로 다른 부분 문자열은 aba, bab, abc S의 길이가 4인 부분 문자열은 abab, babc가 되고, 여기서 서로 다른 부분 문자열은 abab, babc S의 길이가 5인 부분 문자열은 ababc가 되고, 여기서 서로 다른 부분 문자열은 ababc 따..

문제설명 입출력 예제 개념 집합 A와 B가 주어졌을 때 (A - B) ∪ (B - A)의 값을 구하는 문제다. 자료구조 map을 이용해서 푸는 방법도 있지만, 필자는 조금 다르게 풀었다. 두 집합의 원소를 벡터에 삽입 교집합을 이진 탐색을 이용하여 정수형 변수에 삽입 벡터의 크기에서 교집합의 원소의 차를 출력 풀이 #include #include #include int main() { int N, M, n, count = 0; std::cin >> N >> M; std::vector v(N + M); 집합 A, B의 원소의 개수 N, M, 입력받을 숫자 n, 교집합의 수 count를 초기화해준다. 그리고 N + M의 크기를 가지는 벡터 v를 초기화해 준다. for (int i = 0; i < N; i++..

문제설명 입출력 예제 개념 N개의 문자열과 M개의 문자열 중 겹치는 문자열을 출력하는 문제다. 여기서 사전순으로 출력해야 하기 때문에 set 자료 구조를 이용하여 저장과 동시에 정렬을 하면 편하게 해결할 수 있다. 풀이 #include #include #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; std::string str; std::vector v; std::set res; 문자열의 수 N, M, 입력받을 문자열 str, 초기에 N개의 벡터를 저장할 벡터 v, 최종 적으로 자료를 담을 res를 초기화한다. std::cin >> N >> M; while (N--) { std:..

문제설명 입출력 예제 개념 M개의 카드 중에 N개의 숫자 카드와 같은 것이 몇 개 있는지 출력하는 문제다. map 자료 구조에 저장하여 개수를 출력하면 시간 초과 문제에 걸리게 되는데, 이는 map 자료구조는 연산이 O(logN)의 시간 복잡도를 가지기 때문이다. 즉, M개의 숫자를 하나씩 확인할 때마다 시간 복잡도가 O((N+M) logN)이 되므로 다른 방법을 찾아야 한다. 따라서 시간 복잡도를 줄이는 과정이 필요한데, 이진 탐색을 이용한 std::upper_bound() 함수와 std::lower_bound() 함수를 사용하거나 map의 멤버 함수인 find() 함수와 반복자를 적절하게 이용하면 해결할 수 있다. 풀이 (1) map #include #include #include int main()..

문제설명 입출력 예제 개념 key와 value로 이루어진 map 자료구조를 사용하면 쉽게 해결할 수 있는 문제다. leave가 되어 있는 사원은 map에서 제거하고, enter만 되어있는 사원만 출력하면 해결할 수 있다. 마지막에 사전의 역순으로 출력하라고 되어 있음에 유의하자. 풀이 #include #include #include int main() { std::map m; int N; std::cin >> N; 사원의 이름과 상태가 문자열로 되어 있으므로 key와 value 모두 문자열로 받는 맵을 초기화 한다. 그리고 로그 수 N을 초기화한다. while (N--) { std::string name, log; std::cin >> name >> log; m[name] = log; } 이름과 로그를 ..

문제설명 입출력 예제 개념 이 전의 포스팅된 문제와 유사하게 해결할 수 있는 문제다. M개의 문자열 중에 N개의 문자열과 겹치는 게 있는지 개수를 카운팅 하는 문제다. 이진 탐색을 이용하여 개수를 늘리는 식으로 해결할 수 있다. 풀이 #include #include #include int main() { int N, M, count = 0; std::string str; std::vector v; std::cin >> N >> M; 문자열의 개수 N, M과 겹치는 문자열의 개수 count를 초기화한다. 그리고 입력으로 받을 문자열 str과 문자열을 저장할 컨테이너 v를 초기화한다. while (N--) { std::cin >> str; v.push_back(str); } std::sort(v.begin(..

문제설명 입출력 예제 개념 이 문제는 M개의 숫자 카드 중에서 N개의 숫자 카드와 겹치는 카드가 있는지 찾는 문제다. find 함수를 사용하면 최악의 경우, 시간 복잡도가 O(MN)이 되므로 시간 초과 문제에 걸리기 십상이다. 따라서 이진 탐색을 이용해 시간 복잡도를 O(M logN)으로 개선하여 해결하면 된다. 풀이 #include #include #include int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N, M, n; std::vector v; 카드의 개수 N, M, 숫자 카드 n을 초기화하고, 숫자 카드들을 담을 컨테이너 vector v를 초기화한다. std::cin >> N; for (int i =..

문제설명 입출력 예제 개념 좌표 압축은 주로 좌표 알고리즘에서 사용되는 기법 중 하나로, 입력으로 받은 좌표 값들을 작은 범위의 정수로 압축하는 것이다. 이를 사용하면 좌표 값이 매우 크거나 작은 경우에도 작은 범위의 정수로 압축해서 사용할 수 있어서, 메모리 사용량과 연산 시간을 줄일 수 있다. 예를 들어, 입력으로 10^5개의 좌표 값이 주어졌을 때, 이 값들이 10^9 이상의 큰 수라면, 메모리를 많이 사용하게 된다. 하지만 좌표 압축 개념을 사용하면, 이 값을 10^5 이하의 작은 수로 압축해서 사용할 수 있다. 문제를 푸는 데 핵심적인 요소는, 입력으로 받은 좌표 값들을 정렬해서 작은 값부터 차례대로 번호를 매길 수 있다는 것이다. 이때 각 값의 번호는 정렬된 배열에서의 인덱스 값과 일치하는데,..

문제설명 입출력 예제 개념 회원의 이름과 나이, 그리고 가입한 순서를 저장하는 구조체를 선언하고, 아래의 조건에 맞게 정렬하여 출력하는 문제다. 앞선 정렬 문제들과 같이 구조체와 연산자 오버로딩을 이용하여 풀었지만, 람다식도 이용하여 풀어보았다. 나이 순으로 정렬 나이가 같다면 가입한 순으로 정렬 풀이 (1) #include #include #include struct User { int _age, _index; std::string _name; }; int main() { int N; std::cin >> N; std::vector v; User라는 구조체 안에 나이에 관한 _age, 순서에 관한 _index, 이름에 관한 _name을 선언한다. 그리고 메인 함수에서 회원의 수를 N으로 초기화하고, U..