본문 바로가기
반응형

알고리즘 풀이164

[백준 9205] 맥주 마시면서 걸어가기(python) https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 맥주 마시면서 걸어가기 문제 맥주를 마시면서 1000m를 갈 수 있는지 체크하면서 최종적으로 축제까지 갈 수 있는지 확인하는 문제 #사용 알고리즘 너비 우선 탐색 📌문제 접근 포인트 1. 각각의 집, 편의점(n개), 축제장 위치의 정보를 입력받고, 갈 수 있는지 체크해보자. 맥주 20개를 사서 50m당 1개씩 먹을 수 있으므로, 최대 1000m 까지 이동할 수 있다는 점을 이용해보자. 2. .. 2023. 6. 22.
[백준 2108] 통계학(Java) https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 통계학 문제 산술평균, 중앙값, 최빈값, 범위를 구해서 출력하는 문제 # 사용 알고리즘 수학 정렬 📌문제 접근 포인트 1. 산술평균을 구해보자. 산술평균은 단순히 주어진 숫자를 다 더해서 N으로 나누어 주면 된다. 첫째 자리에서 반올림한 값을 출력하므로 round함수를 이용해주자. 2. 중앙값을 구해보자. 중앙값은 숫자를 배열에 넣은 후 정렬한 다음 전체 길이의 절반에 위치하는 숫자이므로 정렬을 사용해주자. 3.. 2023. 6. 22.
[백준 17141] 연구소 2 (python) https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 연구소 2 문제 연구소에 지정된 위치에 지정된 갯수 만큼 바이러스를 심을 때 걸리는 최소 시간을 찾는 문제 # 사용 알고리즘 백트래킹 (완전 탐색) 너비 우선 탐색 📌문제 접근 포인트 1. 바이러스를 2인 지점을 선택하여 퍼뜨려야 한다. 이를 위해서 우선 2인 지점을 찾아주자. 나는 백트래킹을 활용한 완전 탐색을 이용했고, 임의로 체크하기 위해 3으로 바꾸어주었지만, 조합을 사용하여 따로 2인 위치만 모.. 2023. 6. 20.
[백준 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.
반응형

티스토리툴바