Algorithm/Greedy
-
백준 1052 - 물병Algorithm/Greedy 2024. 1. 16. 09:29
1052번: 물병 (acmicpc.net) 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 요즘 근래 너무 골드3 문제에 치여서 좀 쉬운 문제를 풀면서 다시 코테 흥미를 높여볼까 생각하면서 실버1 문제를 건드려보았다. 근데 이게 뭔가 싶은데... 누가봐도 그리디 문제인데, 뭐 도통 이해가 안되는 문제를 만나서 한참을 헤메게 되었다. 이 문제를 스터디원들과 꼭 공유해보고자 블로그를 작성한다. ※ 문제의 규칙성 이 문제는 규칙을 발견하면 사실상 문제가 끝난다고 보면된다. 코드도 정말 간단하기 때문에... 충격적이었다...
-
그리디(유형정리) - 백준 20300Algorithm/Greedy 2023. 6. 28. 11:23
20300번: 서강근육맨 (acmicpc.net) 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 문제 로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다. 헬스장에 있는 �$N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지..
-
그리디(유형정리) - 백준 13305Algorithm/Greedy 2023. 6. 28. 10:31
13305번: 주유소 (acmicpc.net) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마..
-
프로그래머스 고득점 kit(유형정리) - 체육복Algorithm/Greedy 2023. 2. 12. 19:19
※ Greedy란? 다른 알고리즘들과는 다르게 Greedy 알고리즘은 처음보는 알고리즘이다 보니 먼저 소개를 하고 지나가려고 한다. Greedy는 탐욕법 알고리즘이라는 말 처럼 순간 순간의 경우마다 가장 최적의 방법이라고 생각하는 경우를 택해서 결국 최적의 경우의 수를 찾아내는 방식이다. 최적의 경우의 수를 보장할 수는 없지만, 대게 근사적으로 최적의 방법을 찾아낼 수 있다. 또한, 코딩테스트에서 그리디 방식을 원하는 문제의 경우 이론적으로 최적의 경우를 택했을 때 거의 가장 최적의 방법이 되며 문제가 해결된다. 코딩테스트 연습 - 체육복 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하..