본문 바로가기

알고리즘

 (305)
[백준] 1781번 : 컵라면 1781번: 컵라면 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 🤔 문제분석 두 가지의 풀이방식이 존재하는데 저번에 풀었던 문제의 유형중에서 완전 똑같은 문제의 유형이라 쉽게 문제를 풀이 하였습니다. 첫번째 방법으로는 서로소 집합을 활용하여 문제를 해결합니다. 서로소 집합으로 풀때에는 컵라면의 개수를 기준으로 내람차순 정렬하고 배열을 순회하면서 해당 노드의 (데드라인, 데드라인-1)을 유니온하여 다음의 리터레이션에서 부모노드를 데드라인-1 을 가르키도록 만들어 여러개를 넣을 수 없게 만듭니다. 두번째 방법으로는 우..
[백준] 1939번 : 중량제한 1939번: 중량제한 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 🤔 문제분석 데이크스트라를 활용하여 문제를 풀면 된다. 간선을 입력받을때에 다 입력받은 뒤에 무게를 기준으로 내림차순 정렬한다. 그 이유는 탐색을할때에 가장 무게가 많이 나가는 다리부터 방문을 해 나아가야 하기때문이다. 첫번째 섬으로부터 시작하여 가장 무게가 많이 나가는 다리부터 방문해나아가면서 방문값을 갱신해 나아간다. 방문을 해나아가면서 두번째 섬에 도착했을때는 방문을 종료하고 ..
[백준] 1135번 : 뉴스전하기 1135번: 뉴스 전하기 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 🤔 문제분석 깊이우선탐색, 다이나믹프로그래밍 문제의 유형으로 지금까지 접하지 못했던 문제의 유형이다. 최상위노드로부터 리프노드까지 방문한뒤에 자기자신의 값을 갱신하는 깊이우선탐색 방식으로 문제를 해결하였다. 탐색을 해가면서 해당 노드는 자기자신의 자식노드로부터 가장 오래 걸린 시간을 갱신해나아간다. 여기서 자기자신의 자식노드들을 리스트에 담아내고 리스트에 담기전에 자기자신의 자식노드는 걸리는시간이 계산이 되어야한다. 담아낸 리스트로부터 가장 ..
[백준] 2141번 : 우체국 2141번: 우체국 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 🤔 문제분석 그리디 유형 문제로 마을의 위치 기준으로 오름차순 정렬한뒤에 사람의 수를 더해가면서 (모든 마을사람들의 수 / 2) 보다 커질경우 그 마을은 우체국의 위치가 된다. 마을 사람들이 절반이 되었을때가 우체국의 최적의 위치가 된다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) village =..
[백준] 1826번 : 연료 채우기 1826번: 연료 채우기 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 🤔 문제분석 데이터를 거리는 오름차순 기름은 내림차순으로 정렬하고, 데이터를 순회하면서 우선순위큐를 활용하여 문제를 해결하였습니다. 배열을 순회하면서 우선순위큐에 기름을 가장 많이 넣을 수 있는 주유소를 넣습니다. 그리고 탱크의 오일이 다 바닥날 수 있는 거리에 도달하면 우선순위 큐에서 기름을 가장 많이 넣을 수 있는 주유소에서 기름을 넣습니다. 여기서 중요한점은 단 한번을 넣을 수 있는게 아니라, ..
[백준] 3649번 : 로봇 프로젝트 3649번: 로봇 프로젝트 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 🤔 문제분석 이분탐색 혹은 투포인터로 문제를 해결 할 수 있으나 이분탐색 풀이법으로 문제를 해결하였습니다. 레고를 사이즈 오름차순으로 정렬한뒤에 순회하는데 i번째를 순회할때 (i+1, N)까지 이분탐색을 통하여 (arr[i] + arr[mid])값이 블록의 사이즈랑 맞을경우는 후보에 두고, 블록 사이즈보다 작다면 start를 mid+1로 크다면 end를 mid-1로 두어 좁혀가며 탐색을 한다. 후보들을 모두 구..
[백준] 1374번 : 강의실 1374번: 강의실 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 🤔 문제분석 정렬한 데이터를 우선순위큐를 이용하여 문제를 해결하였다. 정렬은 시작위치, 끝나는위치 순서대로 오름차순으로 정렬하였고, 배열을 순회하면서 우선순위큐를 활용하여 강의실 개수를 구한다. 우선순위큐에는 끝나는시간을 넣는다. 끝나는 시간을 넣게되면 다음 시작시간과 끝나는시간을 비교한다. 시작시간 ≥ 끝나는시간 : 강의실을 이어서 사용 할 수 있음 시작시간 < 끝나는시간 : 강의실을 이어서 사용 불가능 함 💻 코드 impor..
[백준] 1083번 : 소트 1083번: 소트 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 🤔 문제분석 골드5치고 어려웠던 문제였다. 문제의 요점은 정렬이 되어있지 않은 수 중에서 S보다 작거나 같게 움직였을때 가장 큰 수를 골라야한다. 가장 큰 수를 골라야함으로 그리디 유형의 문제이다. 배열을 순회하면서 현재 리터레이션에서 멀리있으면서 가장 큰 수를 찾는다. 현재 값에서 가장 멀리있으면서 가장 큰수의 인덱스와 값을 찾는다. 현재 인덱스와 가장 큰 인덱스를 교체한뒤 움직인 만큼 S값을 갱신한다. (S -= (가장큰인덱스 - 현재 ..

티스토리툴바