본문 바로가기

알고리즘/백준

 (263)
[백준] 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 -= (가장큰인덱스 - 현재 ..
[백준] 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..

티스토리툴바