728x90 반응형 백준 알고리즘/그리디3 [백준 12970][파이썬][그리디] AB https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 내 기준 상당히 어려웠던 문제. 내가 생각했던 방식과 개선해나가는 과정을 기록해보려고 한다. (A, B) 쌍의 개수 구하기 우선 특정 문자열에서 (A, B) 쌍의 개수는 어떻게 구할 수 있을까? 예를 들어 ABBAABBB 라는 문자열에서 (A, B) 쌍의 개수를 구해보자. 모든 A에 대해서 각 A 뒤에 있는 B의 개수를 구해서 더하거나 모든 B에 대해서 각 B 앞에 있는 A의 개수를 구해서 더하면 된다. 첫 번째 A에 대해서 .. 2023. 7. 18. [백준 12904][파이썬][그리디] A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 두 가지 연산을 통해 S에서 T로 바꿀 수 있는지 판단하는 문제이다. 처음에는 S에서 T로 바꾸는 방식으로 시도를 했는데 굉장히 까다로웠다. S에서 T로 바꾸는 방식은 하나의 단계마다 여러 가지 경우의 수가 존재하기 때문에 신경써야하는 부분이 많다. 그런데 T에서 S로 바꾸는 방식은 하나의 단계마다 단 하나의 경우의 수만 존재한다. 길이가 4인 문자열의 마지막.. 2023. 7. 16. [백준 11501][파이썬] 주식 (그리디, 재귀) https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 주식으로 벌어들인 이득이 최대가 되도록 하는 알고리즘을 작성하는 문제이다. 이득이 최대가 되려면 다음과 같은 과정을 거친다. 주식 가격이 가장 비싼 날 전까지 모든 주식을 매수해서 가장 비싼 날에 전부 판다. 전부 판 다음 날 부터 다시 가장 비싼 날 전가지 모든 주식을 매수해서 가장 비싼 날에 전부 판다. 위 과정을 마지막 날까지 계속 반복하면 된다. 재귀 난 처음에 재귀로 문제를 .. 2023. 7. 10. 이전 1 다음 728x90 반응형
