Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- database
- Algorithm
- SQL
- namenode
- 프로그래머스
- wrapper class
- BIT연산
- 백준
- procedure
- BFS
- bigdata
- spark
- 시뮬레이션
- greedy
- MVC
- priorityqueue
- hdfs
- boto3
- Parquet
- JPA
- MySQL
- datanode
- ES6
- EventScheduler
- 구현
- 우선순위큐
- ACID
- S3
- Spring
- Transaction
Archives
- Today
- Total
목록greedy (1)
IT 개발일지
[백준] 15903 - 카드 합체 놀이(JAVA)
문제 접근 N개의 카드에서 M번 카드 합체를 한 후 카드에 적혀있는 총 합의 최솟값을 구하는 문제 그리디를 활용할 수 있다. 탐욕 선택 속성(만족) 1번 카드 합체를 할 때마다 구하는 최솟값을 모두 더하면 ⇒ 전체의 최솟값을 구한다는 것이 보장된다. 최적 부분 구조(만족) 전체 문제 : M번 카드 합체 후의 총 합의 최솟값 부분 문제 : M번을 진행하면서 각 단계에서 2개의 카드를 뽑아서 최솟값 구함 즉, 각각의 부분 문제에서 최적의 해를 구한 후, 조합하여 전체 문제의 최적해 구할 수 있음 적용 알고리즘 그리디 알고리즘 우선순위 큐 매 부분 문제를 해결하기 위해 최솟값을 추출하기 위해서 우선순위 큐를 활용할 수 있음 시간복잡도 각 단계마다 가장 작은 2개의 값을 뽑아서 문제의 조건을 고러해서 제한시간(..
카테고리 없음
2024. 4. 3. 10:52