Algorithm(알고리즘)131 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. 백준 2941번 파이썬 풀이 | 크로아티아 알파벳 https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 문제 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= www.acmicpc.net 이 문제의 핵심은 replace이다. replace는 특정 문자열을 특정 문자 혹은 제거할 수 있는 기능이다. 이 문제에서는 Croatia에 저장된 문자열이 있으면 *로 바꾸어 주어 길이를 1로 계산하게끔 하였다. 2020. 6. 24. 백준 5622번 파이썬 풀이 | 다이얼 https://www.acmicpc.net/problem/5622 5622번: 다이얼 문제 상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다. 전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. � www.acmicpc.net dial이라는 list에 다이얼 별로 문자를 저장시킨다. 그리고 입력받은 단어의 첫 문자와 dial을 비교하여서 포함되어 있는 j를 찾은 뒤 index(j) +3 만큼 더해주면 된다. 2020. 6. 23. 이전 1 ··· 27 28 29 30 31 32 33 다음
