그리디3 [BOJ] 12904. A와 B(Python) / Greedy 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램 작성하는 문제 사용 알고리즘 : Greedy(탐욕 알고리즘) 처음에 백트래킹 완전탐색으로 구현했는데 제출하자마자 시간초과 났다. 알고리즘 구분을 보니 Greedy 알고리즘이더라. 다른 사람의 풀이를 보고 무릎을 탁! 쳤다. 생각을 바꿔서 T에서 S로 만드는 것이다. 조건을 반대로 생각해 T의 마지막 문자가 "A"이면 pop, "B"이면 pop 하고 문자.. 2021. 4. 8. [BOJ] 13305. 주유소(Python) / Greedy www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 이해하는 건 금방이었다. 그리디(Greedy) 알고리즘으로 접근했다. 그리디하게 for문으로 1번 인덱스부터 현재 위치에서의 주유비와 이전의 주유비와 비교, 최솟값으로 갱신한다. 최소 주유비로 거리를 곱한 값을 전체 가격 total 변수에 더해준다. 늘 느끼듯 Greedy나 DP는 발상이 힘들지, 코드는 짧다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin... 2021. 3. 12. [Programmers] 큰 수 만들기(Python) / Greedy programmers.co.kr/learn/courses/30/lessons/42883?language=python3 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 난 개인적으로 어려웠던 문제다. Greedy 알고리즘은 뭔가.. 쉽고도 어려운 알고리즘이다. stack 으로 구현한 Greedy한 풀이.. 어려워서 다른 사람 풀이를 참고했다. stack에 값이 있고, k가 남아있다면 stack의 마지막 값과 현재 value를 비교해 value가 크다면 k를 사용하며 stack의 마지막 값을 빼준다. 앞에서부터 탐색하며 비교해주기 때문에 k를 다 써버린다면 뒷 부분은 사실 그리디하게 풀 수 없기 때문에 최적해가 아닌 경우가 발생할 수 있겠다. 그리디의 약점이 무조건 최적해를 보장하지는 않는.. 2021. 2. 26. 이전 1 다음
