정렬6

• [백준/BOJ] 2437번: 저울 문제 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 해설 문제의 예시를 봐보자. 3, 1, 6, 2, 7, 30, 1이 있을 때 이를 오름차순으로 정렬해보면 1, 1, 2, 3, 6, 7, 30이 된다. 만약 가장 가벼운 추에 1이 없다면, 우리가 측정 못하는 가장 작은 무게는 1이 된다. 차례대로 봐보면, 첫번째 추로 1을 측정할 수 있다. 두번째 추를 이용해 2도 측정할 수 있다. 세번째 추를 이용하여 3, 4를 측정할 수 있다. 4번째 추를 사용하.. PS(Problem Solving)/BOJ 2022. 11. 1.

• 

  [백준/BOJ] 13904번: 과제 문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 해설 우선순위 큐를 이용한 그리디 알고리즘으로 문제를 풀었다. 문제의 예시를 보자. 다음과 같이 점수가 더 큰 문제부터 차례대로 정렬을 해놓았다. 우선 점수가 가장 큰 60점짜리 문제는 4일이 마감 기간이므로 4일에 문제를 풀도록 하자. 이제 다음으로 점수가 높은 50점짜리 문제를 보자. 이 문제 또한 2일째에 아직 아무 계획이 없으므로 2일째에 끝내도록 하자. 다음으로 40점짜리 문제이다. 이 문제의 마감기한은 4일이지만, 이미 4일.. PS(Problem Solving)/BOJ 2022. 9. 9.

• 

  코틀린(kotlin) - 우선순위큐(PriorityQueue) 정렬 기준 백준 또는 CodeForce 등을 풀다보면 우선순위 큐를 사용할 일이 많다. 이 때 우선 순위 큐에 들어가는 자료형이 Int, Double, String 등 한개로만 이루어져 있다면, 아무 조건없이 넣었을 때 오름차순으로 정렬될테고, reverseOrder() 명령어를 통해 역순으로 정렬할 수도 있다. val pq = PriorityQueue() pq.add(1) pq.add(2) pq.add(3) val rpq = PriorityQueue(reverseOrder()) rpq.add(1) rpq.add(2) rpq.add(3) /* pq -> 1, 2, 3 rpq -> 3, 2, 1 */ 하지만 자료형이 하나가 아닌, Pair 또는 Triple 혹은 데이터 클래스와 같은 것을 PriorityQueue의 .. Programming/Kotlin 2022. 8. 7.

• [백준/BOJ] 5545번: 최고의 피자 https://www.acmicpc.net/problem/5545 5545번: 최고의 피자 첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄 www.acmicpc.net 문제 상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 종류가 있을 수도 있다. 이 피자 가게는 토핑 N개에서 여러 종류를 선택해서 주문할 수.. PS(Problem Solving)/BOJ 2022. 3. 2.

• [백준/BOJ] 18870번: 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 해설 문제가 잘 이해가 안갔으나 .. PS(Problem Solving)/BOJ 2022. 2. 13.

• [백준/BOJ] 11656번: 접미사 배열 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문제 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오. 해설 입력받은 문자열의 길이만큼 .. PS(Problem Solving)/BOJ 2021. 12. 29.