본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 11000] 강의실 배정 (python) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 강의실 배정 문제 강의실을 배정하여 최소 강의실 수를 찾는 문제 # 사용 알고리즘 그리디 우선순위 큐 정렬 📌문제 접근 포인트 1. 강의실을 배정하기 위한 방법을 생각해보자. 그리디 방식을 생각하면, 먼저 시작시간 순서대로 강의실을 배정하고, 진행 중인 강의의 끝나는 시간과 새로운 강의의 시작시간을 비교해야한다. 2. 이를 위해 강의의 시작시간을 기준으로 정렬 후, 현재 사용 중인 강의실 중에서도 가장 먼저 진행한 강의(우선순위가 높은 강으)의.. 2023. 6. 18.
[백준 1735] 분수합 (Java) https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 분수합 문제 두 분수의 합을 기약분수의 형태로 구하는 문제 #사용 알고리즘 수학 📌문제 접근 포인트 1. 단순 분수의 합을 구하는 방법은 A/B + C/D 라고 하면 A*D + B*C / B*D 이다. 2. 기약 분수로 나타내야 한다는 것은 두 수의 최대 공약수로 나누어야 한다는 뜻이다. 두 수의 최대 공약수를 구할 수 있도록 함수를 구성하자. 3. 각 분자와 분수를 최대 공약수로 나누면 해결! ⚙ 내가 푼 정답 코드 public class Main.. 2023. 6. 14.
[백준 1967] 트리의 지름(python) https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리의 지름 문제 트리에 존재하는 경로들 중에서 가장 긴 것의 길이인 지름을 구하는 문제 #사용 알고리즘 깊이 우선 탐색 트리 📌문제 접근 포인트 1. 트리의 경로 중에 가장 긴 것을 찾아야한다. 가장 긴 것을 찾는 방법을 생각해보자. 2. 트리는 사이클이 없는 그래프이므로, 임의의 노드에서 가장 먼 지점은 항상 트리의 끝 노드이기에 임의의 노드(루트 노드)에서 가장 거리가 먼.. 2023. 6. 14.
[백준 18870] 좌표 압축(Java) https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 좌표 압축 문제 좌표 압축을 적용한 결과를 출력하는 문제 사용 알고리즘 # 정렬 📌문제 접근 포인트 1. 좌표 압축의 개념에 대해서 먼저 생각해보자. 좌표 압축은 쉽게 생각하면 중복을 제거하여 오름차순 정렬 후, 해당 순서 인덱스 값을 가져오란 뜻이다. 예를 들어 예제를 좌표 압축을 적용하면 2 4 -10 4 -9를 생각해보면 중복을 제거해서 오.. 2023. 6. 8.
[백준 9084] 동전 (python) https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동전 문제 동전의 종류가 주어 질 때 주어진 금액을 만드는 모든 방법의 수를 세는 프로그램을 작성하는 문제 사용 알고리즘 #다이나믹 프로그래밍 📌문제 접근 포인트 1. 동전의 종류가 오름차순으로 주어진다. 해당 동전들로 주어진 금액을 만들어보자. 2. 단순하게 다이나믹 프로그래밍을 구상해보자. 먼저 dp를 구상할때 0원으로 만들 수 있는 경우의 수는 무조건 1이므로 dp[0] = .. 2023. 6. 8.
[백준 1463] 1로 만들기 (python) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기 문제 주어진 숫자를 요구조건에 맞춰서 1로 만들 경우의 최소 연산 수를 구하는 문제 다이나믹 프로그래밍을 활용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 요구 제한 시간이 굉장히 짧다. 단순 완전 탐색 등의 방법이 아닌 다이나믹 프로그래밍 방법을 생각해보자. 2. 2가지 방향을 생각할 수 있다. 일반적인 다이나믹 프로그래밍 처럼 DP 1부터 X까지 규칙을 찾아 만들어 가는 방법이 있고, X부터 규칙에 맞춰 1로 찾아 갔을 때의 최소 연산을 찾는 방법이 있다. 3. 요구 조건 대로 X가 3으로 .. 2023. 6. 5.
반응형

티스토리툴바