자료구조 & 알고리즘

[백준] 회의실 배정 - 1931 Python 파이썬 풀이

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘 문제입니다. 😀 한 유튜버분이 그리디, 탐색, 동적 프로그래밍 각 50문제씩 풀어보는 것을 추천해 주셔서 그리디만 엄청 풀고 있습니다.😪 📝 접근 방식 & 문제 풀이 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회..

[백준] ATM - 11399 Python 파이썬 풀이

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 실버4 그리디 알고리즘 문제입니다. 😀 📝 접근 방식 & 문제 풀이 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = ..

[백준] 설탕 배달 - 2839 Python 파이썬 풀이

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 실버4 그리디 알고리즘 문제입니다. 😀 📝 접근 방식 & 문제 풀이 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램..

[백준] 거스름돈 - 5585 자바 & 파이썬 풀이

https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 그리디 알고리즘 문제입니다. 📝 접근 방식 & 문제 풀이 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성..

[백준] 전자레인지 - 10162 자바 & 파이썬 풀이

https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 그리디 알고리즘으로 쉽게 풀 수 있는 문제입니다. 잔돈 계산 문제와 레퍼토리가 비슷하고, 대신 전자레인지라는 익숙한 도메인 지식 덕분에 문제를 이해하는 시간이 거의 없었습니다. 😀 📝 접근방식 & 문제풀이 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에..

[백준] 세탁소 사장 동혁 - 2720 자바 & 파이썬 풀이

https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 저번 글에서 그리디 알고리즘에 대해서 학습했습니다. 따라서, 그리디 알고리즘의 대표적인 문제인 잔돈 계산을 풀어봤습니다.😀 접근 방식 & 문제 풀이 미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다. 동혁이는 리암에게 실망했다. 리암은 거스름돈을 주는 것을 자꾸 실수한다. 심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다! 어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성..

[알고리즘] 그리디 알고리즘이란?

그리디(greddy) 알고리즘이란 말 그대로 탐욕 알고리즘입니다. 미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택을 하는 탐욕적인 알고리즘이기 때문입니다. 코딩 테스트에서 많이 출시되는 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법입니다. 😀 하지만, 당연히도 그리디 알고리즘은 항상 '최적의 해'를 보장하지 못합니다. 현재의 최적 해가 전체의 최적 해가 되리라는 보장이 없기 때문입니다. 따라서 다음과 같은 조건을 생각해서 문제 풀이를 위한 아이디어를 떠올리고 정당한지 검토할 수 있어야 제대로 된 해답을 도출할 수 있습니다. 👍 📝 그리디 알고리즘의 조건 ⦁ 조건 1 ✔ 현재의 선택이 미래에 영향을 주지 않는다. 서울에서 대전까지 가는 거리를 고려했을 때, 대전에서 부산까지의 거리에 영향을 ..