그리디 알고리즘4

• 

  [알고리즘] 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘이란? Greedy를 해석해보면 "탐욕스러운"이다. 이 때문에 그리디 알고리즘을 다른 말로 탐욕 알고리즘이라고도 한다. 이 알고리즘은 선택을 할 때마다 최적의 상황만을 선택해 최종적으로 최적의 결과에 도달하게 된다. 여러 선택이 있을 때, 모든 경우의 수에서 최적의 선택을 했다고 하자. 이때 최적의 선택만을 골랐다 해서 최적의 결과만 나오는 것은 아니다. 최적의 선택이 모여 조금 덜 한 결과가 나오는 경우의 수가 있을 수도 있다. 그리디 알고리즘은 위와 같은 경우가 있어서는 안되며, 항상 최적의 선택만을 하여 최적의 결과가 나와야 하는 알고리즘이다. 정당성 증명 탐욕적 선택 속성(Greedy Choice Property): 현재의 선택이 이후의 선택에 영향을 주지 않으면서, .. Algorithm 2023. 11. 14.

• 

  [백준/BOJ] 1946번: 신입 사원 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 해설 문제에서 핵심 문장은 "어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다."이다. 즉, 두 성적이 모두 다른 지원자보다 떨어진다면, 그 사람은 면접에서 떨어지게 된다. 문제의 예시 중 첫 번째 테스트케이스를 보자. (3, 2), (1, 4), (4, 1), (2, 3), (5, 5).. PS(Problem Solving)/BOJ 2022. 9. 16.

• [백준/BOJ] 12931번: 두 배 더하기 문제 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 해설 배열 A를 B로 만들 수도 있겠지만, 좀 더 쉽게 생각해보면 배열 B를 모두 0의 값을 가지게 만들어도 된다. 문제를 보면, 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 이를 반대로 생각하면 다음과 같다. 배열에 있는 값 하나를 1 감소시킨다. 배열에 있는 모든 값을 2로 나눈다. 여기서, 2번을 실행시키기 위해서는 모든 값이 짝수여야한.. PS(Problem Solving)/BOJ 2022. 7. 20.

• [백준/BOJ] 1202번: 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그.. PS(Problem Solving)/BOJ 2022. 7. 3.