이숭간 공부기록

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제유형 : 그리디, 정렬 문제풀이 : 가장 거리가 먼 구간부터 끊어주면 된다! 내가 좀 헤맷던 부분은 진짜 바보같은데 일단 거리를 기준으로 정렬까지 했는데, 해당 구간을 끊었을때 끊겨진 각 구간의 합을 어떻게 처리해야될지를 모르겠었다. 근데 그냥 거리를 저장한 배열에서 그 구간을 자를때마다 전체합에서 그만큼만 빼주면 최종결과가 그냥 최종답이다. k가 n보다 크거나 같을때..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제유형 : 정렬, 그리디, 우선순위큐 문제풀이 : 이전 회의의 종료시간과 현재 회의의 시작시간을 비교한다. 이때 서로 같은 강의실 이용이 가능하다면 큐의 원소를 다음회의로 갱신하도록 하고 서로 다른 강의실을 이용해야한다면 큐에 해당강의의 종료시간을 추가한다. 회의실 배정 문제와 비슷하다. 회의실배정문제에서는 연속된 회의를 가장많이 찾기만 하면 되는거였고 조건에 만족하지 않는애들은 버리면 되었는데, 여기서는 그런 애들도 다 체크해줘야되기때문에 ..

https://programmers.co.kr/learn/courses/30/lessons/42885# 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제유형 : 그리디, 투포인터 문제풀이 : 가능한 최대한 많이 담아서 보내야하므로 그리디 나는 큐를 이용해서 풀었다. ( 투포인터 느낌 ) 내림차순 정렬한 큐에서 왼쪽, 즉 가장 큰값부터 (popleft) 보트에 태우고, 더이상 큰값을 태울수 없을때 큐의 오른쪽, 즉 가장 작은값부터(pop) 보트에 태워서 한번 보낼때 가장큰애들과 가..

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제유형 : 그리디 문제풀이 : 스택을 이용한다. ( 숫자의 맨앞을 계속해서 더 크게 만들어주는것 ) 스택에 숫자가 있고 k가 0 이상이면 현재숫자와 비교해서 더 큰값이 스택의 앞쪽에 위치할 수 있도록 한다. 만약 현재숫자가 현재스택 최상단숫자보다 작으면 그냥 넣는다. 현재숫자가 더 크다면 스택에서 pop하고 k를 1감소시킨다. 이 과정을 더이상 스택의 최상단에서 현재숫자보다 큰값이 안나올때가지 반복한다. 숫자를 모두 확인했는데 k가 0이상이면 더 제거해야한다는 뜻이고, 이미 앞쪽에는 최대한 큰 숫자가 앞에 위치하도록 조정해 놓은것이므로 ..

https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제유형 : 그리디 문제풀이 : 여분을 가진 학생도 도난을 당할수 있다 라는 예외처리를 잘 해주어야함 이때 해당학생은 reserve와 lost에서 모두 제거해줘야함 ( 집합의 차집합연산 이용 ) 나를 기준으로 앞에 애한테 줄수있는 상황이면 앞에애한테 먼저 주는식으로 reserve를 반복한다. 내가 만약 앞에 애와 뒤에애한테 모두 줄 수 잇는 상황일때 뒤에애한테 줘..

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제유형 : 그리디, 정렬 문제풀이 회의가 겹치지 않으면서 최대수를 구해야하므로 끝나는시작이 빠를수록, 끝나는 시작이 같다면 시작하는 시간이 빠를수록 해당 회의를 선택하는것이 최대의 회의개수를 만들수 있다. 시작시간으로도 한번더 정렬해줘야 하는 이유는 시작시간과 종료시간이 같은 회의일경우 count를 해줘야하기 때문이다. 현재일의 시작시간이 이전일의 종료시간보다 크면 count를 증가시킨후, 종료시간을 현재일의 종료시간으로 갱신한다. 정답코드 import sys input = sys.stdin.readline n = int(i..