개발일지

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

문제설명 입출력 예제 개념 학점의 평균을 계산하는 문제다. 학점을 계산하는 방법은 다음과 같다. 전공 학점: 학점 * 과목 평점 전공 학점 평균: 전공 학점 / 총 학점 P 과목은 제외 따라서 전공 학점들을 계산하여 모두 더한 후 총 학점으로 나눠주면 문제를 해결할 수 있다. 풀이 (1) #include int main() { int count = 0; float sum = 0; float grades[9] = { 0 }; std::string str[9] = { "A+", "A0", "B+", "B0", "C+", "C0", "D+", "D0", "F"}; 신청한 총 학점을 계산할 count, 학점의 총합을 계산할 sum, A+부터 F까지 학점을 계산할 grades 변수를 선언한다. for (int i..

컨테이너 어댑터(Container Adapter)개요　앞서 살펴본 컨테이너들은 완전 바닥부터 직접 만들었다. 하지만 이미 존재하는 컨테이너를 기반으로 새로운 컨테이너를 만드는 작업, 즉, 래핑(wrapping)하여 새로운 인터페이스를 만드는 것이 더욱 효율적일 때가 있다. 이것이 바로 컨테이너 어댑터다. C++ 표준 라이브러리에서 제공하는 대표적인 컨테이너 어댑터를 간략하게 설명하고 구현하는 시간을 가져보자.std::stack 　스택(stack)은 데이터의 처리와 저장을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하는 컨테이너다. 기능적인 측면에서 스택은 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 괄호를 검사하거나, 뒤로 가기 버튼, 컴파일러를 구현할 때 사용된..

문제설명 입출력 예제 개념 겹친 색종이를 제외한 나머지의 색종이의 넓이를 구하는 문제다. 전체 넓이에서 색종이가 차지하고 있는 곳을 빼는 방식과, 색종이가 차지하고 있는 곳의 개수를 찾으면 간단하게 해결되는 문제다. 풀이 #include int main() { int ary[100][100] = { 0 }; int n, result = 0; std::cin >> n; 먼저 2차원 배열 ary를 선언해 주고, 색종이의 개수를 n으로 초기화한다. 그리고 넓이를 출력할 result 변수도 선언해 준다. while (n--) { int y, x; std::cin >> y >> x; for (int i = y - 1; i < y + 9; i++) { for (int j = x - 1; j < x + 9; j++)..

std::deque개요　앞서 살펴본 자료구조들은 연속된 자료구조 거나, 연결된 자료구조였다. 하지만 std::deque(Double-ended queue)는 두 가지 방식이 섞여있는 형태며, 양방향 삽입/삭제가 모두 가능한 자료구조다. 따라서 deque는 배열과 리스트의 장점을 모두 가지고 있어, 둘의 단점을 보완할 수 있는 자료구조다. 여기서 queue는 추후에 다룰 자료구조이니, 이런 것이 있구나 정도만 짚고 넘어가자.구조　앞서 부분에서 deque의 구조가 조금 특이하다는 것을 알았다. 이를 가시적으로 확인하기 위해 다음 그림을 보자.  　위 그림은 deqeue의 전체 덱 자료구조를 나타내고 있다. Chunk는 여러 개의 메모리 청크 중 하나를 나타낸다. 각각의 청크는 연속된 메모리 블록으로 구성되..

std::forward_list개요　앞선 자료구조 포스트의 std::forward_list는 아주 기본적인 형태로 구현된 연결리스트다. 따라서 리스트 끝에 원소를 추가하거나, 역방향으로 이동하는 기초 기능 외에는 지원하지 않는다. 따라서 C++에서는 이러한 단점을 보완하기 위해 양방향 연결 리스트(doubly-linked list) std::list를 제공한다. 이를 사용하기 위해선 헤더파일을 임포트 해야 한다.구조　연속된 자료 구조와 연결된 자료구조 (2) with C++에서 그림을 하나 가져와보자.  　보면 알겠지만, 노드끼리 서로 연결되어 있기 때문에 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터, 해당 노드에 있는 데이터를 갖고 있다. 간략하게 형태를 코드로 파악하자면 다음과 같다...

함수와 인자 전달 방식 Call by Value 정의: 호출하는 코드에서 넘겨주는 실인자 값이 함수의 매개 변수에 복사되어 전달되는 방식 특징 함수 내에서 실인자를 손상시킬 수 없음 실인자의 크기가 크면 오버헤드가 발생하여 복사하는 시간이 길어짐 생성자는 실행되지 않고, 소멸자만 실행됨 (생성자와 소멸자 비대칭 문제) Call by Address 정의: 주소를 직접 포인터 타입의 매개 변수에 전달하는 방식 특징 의도적으로 함수 내에서 실인자의 값을 변경시킬 때 사용 원본 객체를 복사하는 시간 소모가 없음 생성자와 소멸자의 비대칭 문제가 없다 함수 호출 시 객체 전달 다음 예제에 있는 각각의 출력문 cout에서 waffle의 radius 값을 생각해보자. // 예제 5-1 #include using nam..

문제설명 입출력 예제 개념 특정 구간까지의 수열의 합을 구하는 문제다. 단순히 반복문을 중첩시켜 결괏값을 얻으려 하면 십중팔구 시간초과에 걸린다. 이러한 문제처럼 연속된 값을 더하는 문제를 풀 땐 구간합 개념을 이용하면 쉽게 해결할 수 있다. 구간합(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 ..