본문 바로가기

알고리즘

[백준/C++] 5347번 LCM 문제링크5347번 LCM 유클리드 호제법을 통해 최대공약수를 구현하고 최소공배수를 구하는 문제최소 공배수는 두 수의 곱을 최대공약수로 나눈 값으로 구할 수 있다. 제출코드#include using namespace std;// https://www.acmicpc.net/problem/5347long long gcd(long long a, long long b);long long lcm(long long a, long long b);int main() { long long a, b; long long n; cin >> n; while (n--) { cin >> a >> b; cout b) { A = a; B = b; .. 알고리즘/백준풀이 2024. 11. 14.
[백준/C++] 1912번 연속합 문제링크1912번 연속합 수열에서 연속된 수들의 구간합을 더하면서 최대값을 찾는 문제단순하게 브루트 포스 방식으로 이중for문을 사용하면 답이 나오기는 하지만 시간초과가 발생함동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있느냐를 물어보는 문제동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것을 의미하며 알고리즘이 아니라 문제 해결 방식이다.자세한 내용은 아래를 참고하면서 학습하는 게 좋다.https://hongjw1938.tistory.com/47 알고리즘 - Dynamic Programming(동적 계획법)1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 .. 알고리즘/백준풀이 2024. 11. 14.
[백준/C++] 2178번 미로 탐색 문제링크2178번 미로 탐색 문제를 읽고 2차원 배열을 이용한 4방탐색과 bfs를 떠올릴 수 있는가가 관건이런 유형의 문제는 많이 나온다.이를 더 응용한 문제로는 8방향을 이용한 SWEA 11315 오목 판정 등의 문제도 있다.  제출코드#include #include // https://www.acmicpc.net/problem/2178using namespace std;int N = 0, M = 0;// 동서남북 방향 배열int dx[4] = { 1, -1, 0, 0 };int dy[4] = { 0, 0, -1, 1 };// 미로 베이스 배열int arr[101][101] = { 0 };// 방문 배열bool visited[101][101] = { false, };// 이동한 칸 기록용 배열int d.. 알고리즘/백준풀이 2024. 11. 14.
[백준/C++] 1931번 회의실 배정 문제링크1931번 회의실 배정 정렬과 그리디를 통해 찾아낼 수 있음회의의 시작 시간과 끝 시간이 한 쌍으로 묶이기 때문에 pair를 사용하여 풀어 줌가장 많은 수의 회의를 하기 위해서는 시작시간 보다는 첫 회의가 끝나는 시간이 중요하기 때문에회의 종료 시간을 토대로 정렬을 해주고 그 시간을 기준으로 하며 다음 시작 시간을 찾고계속해서 일찍 끝나는 시간들을 찾아주면서 최대 회의를 할 수 있는 횟수를 찾아냄 제출코드#include #include #include // https://www.acmicpc.net/problem/1931using namespace std;int main(){ int N = 0, startT = 0, endT = 0, answer = 0; vector> vec; cin >> N; .. 알고리즘/백준풀이 2024. 11. 13.
[백준/C++] 1927번 최소 힙 문제링크1927번 최소 힙 직전에 푼 최대 힙 문제의 변형버전로직은 동일하지만 우선순위 큐를 오름차순, 내림차순으로 정렬할 수 있냐를 물어보는 문제우선순위 큐를 선언할 때 우선순위 기준에 대하여 greater, less를 사용하여 오름차순과 내림차순을 정의할 수 있다.priority_queue, greater> greater_pq; // 오름차순(낮은 수부터)priority_queue, less> less_pq; // 내림차순(높은 수부터) https://soorison-ks.tistory.com/20 [백준/C++] 11279번 최대 힙문제링크11279번 최대 힙 간단하게 봤을 때 구현만 친다면 vector를 사용하여 최대값을 구한다음 처리해주는 식으로 구현했지만, 시간제한에 걸리게 됨.따라서 최대값을.. 알고리즘/백준풀이 2024. 11. 13.
[백준/C++] 11279번 최대 힙 문제링크11279번 최대 힙 간단하게 봤을 때 구현만 친다면 vector를 사용하여 최대값을 구한다음 처리해주는 식으로 구현했지만, 시간제한에 걸리게 됨.따라서 최대값을 구해줄 때 스택이나 큐와 같이 순차적으로 데이터가 들어온 것을 순회하며 별도의 최대값 구하는 연산을 진행하는 것이 아닌 우선순위가 높은 데이터가 먼저 나가는우선순위 큐를 사용하여 연산에 수행되는 시간을 줄여 쉽게 풀어줄 수 있음.우선순위 큐 개념 정리된 위키 우선순위 큐 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 우선순위 큐(Priority queue)는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은ko.wikipedia.org  .. 알고리즘/백준풀이 2024. 11. 2.
[백준/C++] 2776번 암기왕
[백준/C++] 2776번 암기왕 문제링크2776번 암기왕  적은 범위였다면 배열의 인덱스로 쉽게 구현할 수 있지만 정수의 범위가 int이며 개수도 1,000,000개나 되기 때문에 시간초과를 주의해야 하는 문제해쉬테이블 unordered_map을 사용하여 key, value 쌍으로 값을 저장하고 탐색할 수 있게 사용한다.단 이것만 가지고는 시간초과가 나기 때문에ios_base::sync_with_stdio(false);를 통해 C 표준의 동기화를 끊고,cin.tie(NULL), cout.tie(NULL) 따위로 내부적으로 수행되는 연산을 줄여 시간을 확보한다.  제출코드#include #include using namespace std;int T, N, M;int main(){ ios_base::sync_with_stdio(false).. 알고리즘/백준풀이 2024. 10. 26.
[백준/C++] 1966번 프린터 큐 문제링크1966번 프린터 큐  큐에 pair를 통해 키와 밸류값으로 전달할 수 있고우선순위 큐와 비교연산자 greater, less 통해 오름차순/내림차순 정렬로 값을 담아낼 수 있다.기본 우선순위 큐는 내림차순으로 정렬된다.priority_queue, greater> ascendingPQ; // 오름차순priority_queue, less> descendingPQ; // 내림차순  제출코드#include #include using namespace std;int T, N, M, out;int main(){ cin >> T; for (int i = 0; i > N >> M; queue> q; // 큐에 인덱스와 중요도 값을 저장 priority_queue pq; // 우선순위 큐 (자동 내림차순) .. 알고리즘/백준풀이 2024. 10. 26.

티스토리툴바