본문 바로가기

알고리즘

 (305)
[백준] 1911번 : 흙길 보수하기 1911번: 흙길 보수하기 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net 🤔 문제분석 오름차순으로 정렬한뒤, 위치를 가르키는 임의의 변수를 활용하여 문제를 해결하였습니다. 여기서 포인트는 임의의 위치의 변수를 start가 더 클경우 pos를 start로 초기화 시켜줍니다. pos가 end에 도달 할때까지 개수를 증가시키며 pos에 L을 더합니다. 💻 코드 import sys input = sys.stdin.readline N, L = map(int, input().split()) w..
[백준] 13334번 : 철로 13334번: 철로 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 🤔 문제분석 처음에는 이분탐색으로 문제를 접근하였습니다. 우선 시작, 종료 위치를 오름차순으로 정렬합니다. start = 가장 작은위치, end = 가장 끝에있는위치를 시작으로 이분탐색을 시작합니다. mid값을 구한다음, (mid, mid +d) 범위안에 있는 위치들을 카운팅 해줍니다. (mid, mid+d) 기준으로 왼쪽으로 있는 개수, 기준으로 오른쪽에 있는 개수를 카운팅한뒤 왼쪽이 더많다..
[백준] 13164번 : 행복 유치원 13164번: 행복 유치원 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 🤔 문제분석 이전에 비슷한 문제의 유형을 풀어보아서 문제를 쉽게 해결 할 수 있었습니다. 정렬을 한뒤에 각 이웃하는 원소끼리 diff를 구한뒤 가장 큰 diff를 k-1개를 pop 시킨다면 k개의 그룹이 생깁니다. k-1개의 뺀 나머지 diff를 모두 합치게된다면 원하는 값이 나옵니다. 잘 생각해보면 diff를 모두 더한값이 정답이 되는 과정을 예를 들어본다면 1,3,5 가 있다고 한다면 diff 값은 2, 2가 ..
[백준] 8983번 : 사냥꾼 8983번: 사냥꾼 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 🤔 문제분석 이분탐색으로 문제를 해결하는것을 깨닫았으나, 어떻게 조건을 세워야할지 감을 못잡았습니다. 동물을 기준으로 L범위엔에 들어가는 사냥꾼을 찾아내고 L의 범위안에 들어왔을 경우만 카운팅 하면 된다. 범위를 계산하는 방법은 절대값의 수식에서 점화식을 도출 할 수 있다. 아래의 식에서 S와 E 범위안에 들어간다면 동물이 사냥꾼의 L범위안에 들어가게된다. 💻 코드 import sys input = sys.stdin.readline M, N,..
[백준] 2170번 : 선 긋기 2170번: 선 긋기 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 🤔 문제분석 우선순위 큐로 문제를 해결하였는데, 그럴필요없이 한번의 순회로 문제를 해결할 수 있습니다. 우선순위큐로는 모든 큐를 순회하면서 연결 될 수 있는 조건을 연결하고, 연결하지 못한경우 원소를 추가합니다. 조금 더 생각해보니 모든 큐를 순회함으로 사실상 우선순위큐가 의미가 없다 🥲 한번의 정렬으로 해결 할 수 있는데 이전상태의 끝나는 점을 가지고 있다가 그 끝나는 점이 그다음 시작점보다 클경우, 작을경..
[백준] 2230번 : 수 고르기 2230번: 수 고르기 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 🤔 문제분석 이분탐색을 이용하여 문제를 해결하였습니다. 내림차순으로 정렬한뒤에 원소를 순회하는데 순회 하고자 하는 위치 +1 부터 마지막 원소까지 이분탐색으로 mid 값을 조정하여 최소 M값을 찾아냅니다. M값보다 크거나 같을경우 최소값을 갱신하고 end 값을 mid - 1로 지정하여 더 작은 값을 찾아냅니다. 반대로 M보다 작을경우 start를 mid +1로 지정하여 M보다 큰 값을 찾게 만듭니다. 💻 코드 impor..
[백준] 2473번 : 세 용액 2473번: 세 용액 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 🤔 문제분석 한 용액을 선택한뒤에 투포인터를 활용하여 해당 용액과 더했을때 0과 가까운 수를 찾으면된다. 이것도 마찬가지로 더했을때 0보다 크다면 right값을 감소시키고 0보다 작다면 left값을 증가시키면서 값을 찾아나아가면 된다. 아래의 두 용액 문제를 풀면 세 용액도 위의 설명한대로 문제를 해결 할 수 있다. 2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 1..
[백준] 2470번 : 두 용액 2470번: 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 🤔 문제분석 정렬 + 투포인터 문제로 pleft, pright를 두고 data[pleft] + data[pright]를 더한 값이 0보다 클경우 pright값을 줄이고 0보다 작을 경우 pleft값을 줄여가며 최대한 0에 가까운 수를 찾는다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) data = list(map(int, input().spli..

티스토리툴바