본문 바로가기

분류 전체보기

 (64)
[C++] 우선순위 큐(PRIORITY_QUEUE) & 페어(PAIR) 사용법 개요우선순위 큐는 컨테이너 안의 자료들을 내림차순 혹은 오름차순으로 정렬해주는 자료형이다. 그런데 pair와 같이 자료가 두 개 이상이 되면 어떻게 될까??  간략하게 알아보도록 하자.  1. 기본 사용법(내림차순)첫 번째 인자를 기준으로 내림차순으로 정렬된다.첫 번째 인자가 같다면 두 번째 인자를 기준으로 내림차순 정렬된다.#include #include #include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); priority_queue> pq; pq.push({1, 1}); pq.push({1, 2}); pq.push({2, 3}); pq.push..
[C++] 백준 3109: 빵집 문제 이해- 첫째 열: 근처 빵집의 가스관- 마지막 열: 원웅이의 빵집- 파이프는 그러므로 첫째 열에서 시작하여 마지막 열에서 끝나야 함- 파이프의 방향은 우측 위, 우측, 우측 아래만 가능- 각 칸을 지나는 파이프는 1개만 존재할 수 있다. - 시간 제한: 1초- 메모리 제한: 256MB - R: 행의 개수 (1 ~ 10,000, 10^4)- C: 열의 개수 (5 ~ 500, 10^2) - 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수 문제 풀이DFS를 써야함은 문제를 보면 알 수 있다.근처 빵집에서 시작해서 원웅이의 빵집까지 연결해야 하니 말이다.  그런데 파이프의 최대 개수를 어떻게 구할 수 있을까???답은 바로 그리디 알고리즘의 적용이다.  그렇다면 그리디 알고리즘은 어..
[C++] 백준 17420: 깊콘이 넘쳐흘러 문제 이해- 기프티콘이 N개 있으며 사용 가능 기한이 존재한다.- 기한은 연장이 가능한데 한 번 연장하면 30일이 늘어난다.- 기한 연장은 최소한으로 하려 한다.- 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용 가능하다.- 기한이 같은 게 여러 개면 아무거나 사용할 수 있다.- 하루에 여러 개를 사용하거나 연장하는 것 모두 가능하다. - 시간 제한: 1초- 메모리 제한: 512MB - N: 기프티콘의 수 (1 ~ 100,000, 10^5)- Ai: 기프티콘의 남은 기한(1 ~ 1,000,000,000, 10^9)- Bi: i번째 기프티콘의 경우 Bi일 뒤에 사용할 계획이다.(1 ~ 1,000,000,000, 10^9) - 기한 연장을 해야 하는 최소 횟수를 출력하라.※ 32비트 정수를 넘을 수 있다..
[C++] 백준 2637: 장난감 조립 문제 이해- 완제품: 기본 부품 + 중간 부품 - 시간 제한: 1초- 메모리 제한: 128MB - N: 완제품의 번호 (3 ~ 100, 10^2)- M: 관계의 개수 (3 ~ 100, 10^2)- 관계(완제품, 중간 부품 or 기본 부품, 필요한 개수) - 하나의 완제품을 만들기 위하여 필요한 기본 부품의 종류별 개수  문제 풀이기본 부품과 중간 부품을 조합하여 완제품을 만든다는 점에서 선행 관계가 있다고 볼 수 있다.즉 위상 정렬을 사용하여 푸는 문제이다.  개수를 구해야 하므로 DP를 사용해야 할 거 같은데 시간을 구하는 여러 문제들과 달리 개수를 구하는 문제였다. 문제의 입력이 주어지는 것에서 힌트를 얻을 수 있는데,완제품에서 시작하여 위상정렬을 시작하면 문제를 쉽게 풀 수 있다.   1. dp[n..
[C++] 백준 1948: 임계경로 문제 이해- 모든 도로가 일방 통행인 도로이고, 싸이클이 없다 => 사이클이 아닌 방향 그래프(Directed Acyclic Graph)- 시작 도시부터 도착 도시까지 가능한 모든 경로를 탐색할 예정- 출발 도시: 들어오는 도로가 0개- 도착 도시: 나가는 도로가 0개 - 시간 제한: 2초- 메모리 제한: 512MB - n: 도시의 개수 (1 ~ 10,000, 10^4)- m: 도로의 개수( 1 ~ 100,000, 10^5)- 도로의 정보(출발 도시, 도착 도시, 걸리는 시간(1 ~ 10,000, 10^4))- 출발 도시, 도착 도시 - 임계 경로의 비용(마지막에 도착하는 사람이 도착하는 시간)- 이 시간까지 쉬지 않고 움직이는 사람들이 지나가는 도로의 개수더보기더보기임계경로위상 정렬을 진행하면 각 작업..
[C++] 백준 14567: 선수과목(Prerequisite) 문제 이해- 모든 전공 과목을 들어야 졸업할 수 있다.- 특정 과목은 선수과목을 모두 들어야만 들을 수 있다.- 한 학기에 들을 수 있는 과목 수에 제한은 없다.- 모든 과목은 매 학기 개설된다. - N: 과목의 수 (1 ~ 1,000, 10^3)- M: 선수 조건의 수(0 ~ 500,000, 10^5)- 시간 제한: 5초- 메모리 제한: 256MB - 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 출력하라.  문제 풀이각 과목에 대해 선수 과목이 있다는 지문은 선행 관계가 주어진 그래프라고 볼 수 있다.=> 위상 정렬을 사용해서 풀자!   이 문제의 특별한 점은 각 과목마다 이수하는 데 걸리는 학기의 수를 구해야 한다는 점이다.걸리는 학기의 수를 배열을 하나 설정해 DP를 써주면 쉽게..
[C++] 백준 3665: 최종 순위 문제 이해- 대회에 여러 팀이 참여했다.- 작년과 올해는 동일한 팀이 참여했으며, 작년의 전체 순위는 공개된다.- 올해는 전체 순위는 발표되지 않으며, 작년에 비해 상대 순위가 바뀐 팀만 발표된다. - n: 대회에 참가한 팀의 개수 (2 ~ 500, 10^2)- m: 상대적인 등수가 바뀐 쌍의 수(0 ~ 25,000, 10^4) 출력- 확실한 순위를 만들 수 없을경우: ? 출력- 일관성이 없는 잘못된 정보 : IMPOSSIBLE 출력- 확실한 전체 순위가 만들어질 경우: 1등 팀부터 차례대로 출력   문제 풀이작년에 비해 상대 순위가 바뀐 팀에 대해 알려주므로 순서쌍이 주어지는 것으로 볼 수 있다.즉, 위상 정렬을 사용하면 풀 수 있는 문제로 판단했다.  1. 선행 관계의 표현 하지만, 문제점이 있다.작..
[C++] memset 함수(메모리 초기화) 함수 이해C언어와 C++에서 쓰이는 memset 함수는 메모리의 내용(값)을 원하는 크기만큼 특정 값으로 세팅할 수 있는 함수 입니다. 주로 0으로 배열의 값들을 초기화할 때 자주 사용하는 함수입니다.   함수 원형void* memset(void* ptr, int value, size_t num);  1. 반환값: 정상적인 값이 들어온다면 첫 번째 인자로 들어온 ptr 포인터를 반환하지만,실패한다면 NULL을 반환합니다.  2. 첫 번째 인자(void* ptr): 바꾸고자 하는 메모리의 시작 주소가 들어가는 자리입니다.즉, 그 주소를 가리키고 있는 포인터가 위치하는 자리입니다. 흔히 사용하는 방법으로 배열을 초기화한다면 배열의 이름(배열의 시작 주소)이 들어갑니다.Ex)int Rank[500];memse..

티스토리툴바