분류 전체보기225 백준 11399번 파이썬 풀이 | ATM | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net Sort를 한 후에 [0:i+1]까지를 계속 더해가는것이 핵심이다. 이전까지 걸린 시간을 계속해서 더하는 것이므로 1 , 1+2 , 1+2+3, 1+2+3+3, 1+2+3+3+4 를 하면 된다. 2020. 6. 28. 백준 5585번 파이썬 풀이 | 거스름돈 | 그리디(Greedy) 알고리즘 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건� www.acmicpc.net 그리디(Greedy) 알고리즘은 그 순간 최적의 선택을 하는 알고리즘이다. 그 중 가장 기본적인 예시로 동전 거스름돈이 많이 사용된다. 여기서 주의할 점은 파이썬에서는 / 는 소수점까지 나타내므로 // 를 해서 소숫점을 제거해야 한다. 2020. 6. 28. 01. 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘은 탐욕적인 문제 해결 방법으로 '문제를 해결하려는 상황에서 그 순간순간마다 최적의 상황을 쫓는 알고리즘'입니다. Greedy 방법은 최적의 해 근사값을 빠르게 찾아 줍니다. (단, 항상 최적의 결과를 도출하지는 않습니다.) 탐욕적이라고 불리는 이유는 미래를 생각하지 않고 지금 당장 보이는 것에서 최선의 방법을 선택하기 때문입니다. 그리디 알고리즘의 대표적인 예시는 거스름 돈 문제, 시간이 주어졌을때 한 사람이 최대한 많이 할 수 있는 수(활동 선택 문제), 배낭 문제에서 사용됩니다. 동전의 예시를 들자면, 740원을 거슬러 주어야 할때 500원 짜리 1개 , 100원짜리 2개 , 10원짜리 4개로 거슬러 주는 과정에서 "큰 화폐부터 거슬러 준다" 라는 알고리즘을 통해 최적의.. 2020. 6. 28. 백준 1316번 파이썬 풀이 | 그룹 단어 체커 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때� www.acmicpc.net 본 문제의 핵심은 find 를 사용하는 것이다. find는 해당하는 단어를 찾아서 index를 알려주는데 따로 값을 지정해주지 않으면 첫번째 위치를 알려준다. 따라서 만약 앞에 있는 단어의 find index가 뒤에있는 단어의 find index보다 크다면 이건 그룹 단어가 아닌것이다. 예를 들어 aba가 있을때, b는 index 1 / a는 index 0 인데 .. 2020. 6. 25. 이전 1 ··· 39 40 41 42 43 44 45 ··· 57 다음
