본문 바로가기

전체 글79

백준 2075번: N번째 큰 수 (C++) https://www.acmicpc.net/problem/2075 해당 문제는 굉장히 쉬워 보이나 그 쉬운 생각으로 풀게 되면 메모리를 초과하게 된다. 따라서 가장 큰 N개의 수 만큼만 담고 있으면 메모리를 초과할 일이 없게 된다. #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int N, num; priority_queue pq; cin >> N; for (int i = 0; i > num; pq.push(num); if (N < (int)pq.size()) pq.pop(); } cout 2024. 2. 2.
백준 1927번: 최소 힙 (C++) ttps://www.acmicpc.net/problem/1927 해당 문제는 실제 최소힙 자료구조를 사용할 수 있게 구현되어있는 prioriry queue STL 자료형을 사용하는 문제다. 코드는 다음과 같다. #include #include using namespace std; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, x; cin >> n; while (n--) { cin >> x; if (x > 0) pq.push(x); else { if (!pq.empty()) { cout 2024. 2. 2.
백준 1715번: 카드 정렬하기 (C++) https://www.acmicpc.net/problem/1715 이 문제는 어떻게 카드를 합쳐 나갈 때 비교 횟수가 적어지는지 파악하는 그리디 알고리즘 문제라고 볼 수 있다. 정말 쉽게 생각하면 방법은 매우 간단합니다. 가장 작은 수의 카드 묶음을 더 해나간다면 자연스럽게 제일 비교 횟수가 적은 방법을 찾게 됩니다. EX1) 30 50 100 300 320 30+50 sum = 80 80 100 300 320 80+100 sum= 80+180 180 300 320 180+300 sum= 80+180 + 480 320 480 320+480 sum= 80+ 180 + 480 + 800 (가장 비교 횟수가 적은경우) 800 EX2) 10 20 40 10+20 sum = 30; 30 40 70 sum = 30.. 2024. 1. 31.
백준 2948번: 2009년 (C++) https://www.acmicpc.net/problem/2948 해당 문제를 가장 쉽게 접근하는 방법은 2009년 1월 1일부터 몇 일이 지났는지 계산하고 월, 화, 수, 목, 금, 토, 일 이 주기적으로 반복되는 원리를 이용하여 특정 날짜의 요일을 찾을 수 있다 코드는 아래와 같다. #include using namespace std; int main() { string day[7] = {"Wednesday","Thursday","Friday","Saturday","Sunday","Monday","Tuesday"}; int m,d, arr[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; cin >> d >>m; for(int i=1;i 2024. 1. 31.
백준 1924번: 2007년 (C++) https://www.acmicpc.net/problem/1924 해당 문제를 가장 쉽게 접근하는 방법은 2007년 1월 1일부터 몇 일이 지났는지 계산하고 월, 화, 수, 목, 금, 토, 일 이 주기적으로 반복되는 원리를 이용하여 특정 날짜의 요일을 찾을 수 있다 코드는 아래와 같다. #include using namespace std; int arr[13] = {0, 31, 28 ,31 , 30, 31, 30, 31,31,30,31,30,31 }; int main() { int sumDay=0; int x,y; cin >> x >> y; for(int i=1 ; i 2024. 1. 31.
백준 11286번: 절댓값 힙 (C++) https://www.acmicpc.net/problem/11286 해당 문제는 두가지 조건을 만족시키는게 핵심이며 두 가지 조건을 만족시키는 정렬 조건을 만들면 된다. 배열에서 절댓값이 가장 작은 값을 출력한다. 절댓값이 가장 작은 값이 여러 개 일 때는 가장 작은 수를 출력한다. 코드는 아래와 같다. #include using namespace std; class cmp { public: bool operator()(int a, int b) { if (abs(a) == abs(b)) return a > b; // 두 수의 절대값이 같다면 값이 작은수를 top()쪽으로 정렬한다. else return abs(a) > abs(b); // 두 수의 값이 다르다면 절대값이 작은수를 top()쪽으로 정렬한다... 2024. 1. 31.
백준 11718번: 그대로 출력하기 (C++) https://www.acmicpc.net/problem/11718 해당 문제는 getline 메소드를 통해서 공백도 문자열로 입력 받아야한다. 또한 while문 조건문안에 getline을 선언하여 입력이 없을때 프로세스가 종료되게 만들어야한다. #include #include using namespace std; string s; int main() { while( getline(cin, s)) { cout 2024. 1. 31.
백준 23326번: 홍익 투어리스트 (C++) ttps://www.acmicpc.net/problem/23326 이 문제를 접근 할 때 map STL을 통해서 key값을 구역으로 두고 value값을 명소 여부인 0,1을 저장하려고 하였다. 하지만 이렇게 접근하면 실제로 시계 방향으로 이동하거나 시계 방향으로 최소 몇 칸 움직여야 하는지 출력하는 과정에서 map내부의 값을 다 돌아야 하므로 시간 복잡도가 최대 O(500,000*100,000)으로 초과하게된다. 그렇지만.. 풀이 방법이 떠오르지 않아서 아래와 같은 풀이로 시간 초과가 발생하였다. 아래 풀이는 참고하지 말자....! #include #include //#include using namespace std; map m; int main() { ios::sync_with_stdio(false).. 2024. 1. 31.

티스토리툴바