개발일지

문제설명 입출력 예제 개념 단어를 길이를 기준으로 정렬하는 문제다. 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..

문제설명 입출력 예제 개념 특정 구간까지의 수열의 합을 구하는 문제다. 단순히 반복문을 중첩시켜 결괏값을 얻으려 하면 십중팔구 시간초과에 걸린다. 이러한 문제처럼 연속된 값을 더하는 문제를 풀 땐 구간합 개념을 이용하면 쉽게 해결할 수 있다. 구간합(Prefix Sum) - 수열에서 특정 구간의 합 풀이 #include using namespace std; int N, K, temp, sum[100001], ret = -2147483647; int main() { cin >> N >> K; 온도를 측정한 전체 날짜의 수 N, 합을 구하기 위한 연속적인 날짜의 수 K, 구간합을 구할 배열 sum, 구간합 배열의 최솟값 변수 ret을 초기화한다. 이때 ret의 값은 int의 최솟값이다. for (int i ..

문제설명 입출력 예제 개념 의상의 종류의 개수에 따라 경우의 수를 계산하는 문제다. 의상의 종류와 개수를 매칭시킬 수 있으므로 map 자료구조를 이용하여 카운팅할 때 사용하면 된다. 여기서 조합(Combination)의 개념이 등장하는데, 서로 다른 n개의 원소를 순서에 상관없이 r개의 원소를 선택하는 것이다. 예를 들어 headgear, headgear, eyewear, face를 골랐으면 다음과 같이 계산하면 된다. 풀이 #include #include using namespace std; int main() { int num; cin >> num; 테스트 케이스의 개수를 num으로 초기화한다. while (num--) { map _map; int n; cin >> n; int result = 1; ..

문제설명 입출력 예제 개념 수가 주어졌을 때 인접한 수가 등차수열을 이루는지 확인하는 문제다. 풀이 #include using namespace std; int main() { int num; cin >> num; int count = 0; 한수를 확인할 정수를 num으로 초기화시키고, 개수를 출력할 카운트 변수 count를 초기화해 준다. for (int i = 1; i

문제설명 입출력 예제 개념 문자열을 입력받아 숫자와 매칭시키는 문제다. 정해진 개수만큼 문자열 입력이 끝나면, 숫자를 입력했을 때 문자열을 출력하고, 문자열을 입력했을 때 숫자를 출력하면 된다. 따라서 2개의 값을 매칭시키는 문제이므로 map 자료구조를 이용해 주면 된다. 풀이 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 이 문제를 풀다 보면 시간 초과 문제가 빈번하게 일어난다. 따라서 이를 미연에 방지하기 위해 c언어와의 싱크를 해제해 주고, cin과 cout의 tie를 풀어 시간을 조금이라도 단축시켰다. int n, m; cin >..

문제설명 입출력 예제 개념 주어진 자연수 중 소수의 개수를 출력하는 문제다. 여기서 소수란 약수가 1과 자기 자신밖에 없는 수를 의미한다. 알고리즘 1부터 입력된 수까지 순회하며 나눠지는 수가 존재한다면 소수가 아니므로 break를 건 후 다음 반복으로 넘어가고, 나눠지는 수가 없다면 소수의 개수를 늘리는 식으로 접근하면 되는 간단한 문제다. 풀이 #include using namespace std; int N, cnt; int check; int main() { cin >> N; while (N--) { int num; check = 0; cin >> num; for (int i = 1; i < num; i++) { if (num % i == 0 && i != 1) break; check++; } if..

문제 설명 제한 사항 및 입출력 예제 알고리즘 개념 예제에서 주어진 원형 수열을 기준으로 연속 부분 수열을 구하면 다음과 같다. 따라서 이 합들을 저장할 벡터를 초기화한 후에 중복되는 값을 지워주면 해결된다. 여기서 첫 번째 문제는 연속된 합을 반복문을 이용해 하나 하나 저장하고 비교하려니 시간 초과가 걸린다. 두 번째 문제는 끝이 연결되어 끊기는 부분이 없다는 것이다. 이러한 문제를 해결하기 위해 특정 구간의 합을 구할 수 있는 구간합(Prefix sum) 개념을 이용하여 풀었다. 주어진 예제의 구간합을 표현해보면 다음과 같다. sum이 초기화되는 과정을 보면 다음과 같다. 여기서 구간합은 특정 구간의 합을 구할 수 있다고 했는데, 만약 내가 elements의 인덱스 n부터 k까지의 합을 구하고 싶다면..