개발일지

문제설명 입출력 예제 개념 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..

문제설명 입출력 예제 개념 단어를 길이를 기준으로 정렬하는 문제다. std::sort에 비교 구문을 추가하여 해결하면 쉽게 해결할 수 있다. 풀이 #include #include #include int main() { int N; std::cin >> N; std::vector v; while (N--) { std::string str; std::cin >> str; v.push_back(str); } 단어의 개수 N을 초기화하고, 문자열을 넣을 벡터 v를 초기화해 준다. struct { bool operator() (std::string a, std::string b) const { if (a.size() == b.size()) return a < b; return (a.size() < b.size()..

문제설명 입출력 예제 개념 좌표를 오름차순으로 정렬하는 문제다. 이때 x좌표가 동일하다면 y좌표가 증가하는 순서로 정렬해야 한다. 구조체와 연산자 오버로딩을 이용해 데이터가 큰 경우 효율적으로 좌표를 정렬하는 방법이 있고, std::pair를 이용해 좌표를 정렬하는 방법이 있다. std::pair는 처음 등장하는 개념이므로 간략하게 이해하고 가자. std::pair는 간단하게, 두 객체를 단일 객체로 처리하는 기능을 제공하는 구조체다. 풀이 (1) #include #include #include int main() { int N; std::cin >> N; std::vector v; 점의 숫자 N을 초기화하고, Coordinate라는 구조체를 받는 벡터 v를 초기화해 주자. struct Coordinat..

문제설명 입출력 예제 개념 2751번과 마찬가지로 우선순위 큐를 이용하면 쉽게 해결할 수 있다. 이전 문제와 다르게 비교자를 less를 이용하면 내림차순으로 정렬된다는 점을 유념하자. 풀이 #include #include int main() { std::priority_queue que; std::string str; std::cin >> str; 우선순위 큐를 선언하고, 숫자를 문자열로 받아준다. for (char c : str) { que.push(c - '0'); } while (!que.empty()) { std::cout > str; for (char c : str) { que.push(c - '0'); } while (!que.empty()) { std::cout

문제설명 입출력 예제 개념 우선순위 큐(priority_queue)를 이용해 비교자를 설정하면 쉽게 해결할 수 있는 문제다. 풀이 #include #include int main() { std::priority_queue que; int n; std::cin >> n; 우선순위 큐를 초기화하고, 문제에서 오름차순으로 정렬하라 하였으므로 비교자를 greater로 설정한다. for (int i = 0; i > num; que.push(num); } while (!que.empty()) { int num = que.top(); std::cout n; for (int i = 0; i > num; que..

문제설명 입출력 예제 개념 자연수 M과 N 사이의 소수를 찾는 문제다. 소수를 구하는 알고리즘을 효율적으로 구하지 않는다면, 시간 초과가 걸리는 문제다. 풀이(1) #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); int m, n; std::cin >> m >> n; for (int i = m; i