개요
8주차 스터디는 그리디 관련 4문제였다.
A번
문제 요약
주가가 변동하는데, 매일 주식을 하나씩 살 수 있고 원하는 만큼 팔 수 있다.
주가를 다 미리 알고 있을 때 최대 이익을 내는 문제
설명
각 주식마다 그 이후에 나오는 최대까지 들고 있다가 팔면 끝이라서 각 지점에서의 최댓값을 구해놓으면 된다.
prefix sum처럼, 뒤에서 보는 max를 구하면 된다. (postfix max라고 하면 되는거 같다.)
그럼 그냥 O(N)으로 훑으면서 마주치는 주식마다 그 이후 최댓값에 바로 팔면 끝
B번
문제 요약
N자리 수에서 K개를 지워서 얻을 수 있는 가장 큰 수 구하기
설명
스택을 통해서 A[i]보다 A[i+1]가 큰 경우를 앞에서부터 반복적으로 지워준다.
(스택을 쓰는 이유는 A[i]를 지웠더니 A[i-1]과 A[i+1]의 값도 지워야 하게 될 수 있기 때문이다.)
그 후, 남은 K는 남은 수들 중 가장 작은 것들을 없애면 된다.
어쩌다 풀긴 했는데 왜 맞는지는 잘 모르겠다.
Proof by AC
C번
문제 요약
문자열 S, T가 있다.
S에 2가지 연산을 마음대로 적용시켜서 T를 만들 수 있는지 구하기
- S 뒤에 A를 붙이는 연산
- S를 뒤집고 뒤에 B를 붙이는 연산
설명
T를 보면서, 그냥 끝이 A면 A를 빼고 끝이 B면 B를 빼고 뒤집어주는 식으로 반복해서 S가 나오는지 보면 끝이다.
D번
문제 요약
두 수를 더했을 때 최대가 되도록 알파벳에 숫자를 배정하는 문제
설명
자릿수를 보고, 저 A가 100의 자리라면 100A라고 생각하면 된다.
그런식으로 알파벳마다 실제 값은 몇 배인지 확인해주자. 그 후 정렬해서 가장 큰 값부터 9부터 차례대로 배정해주면 된다.
그리고 한가지 더 생각해줘야 하는 부분이, 0이 앞에 오는 경우는 없다는 것이다.
그래서 0이 될 수 없는 수들은 따로 체크를 해 주고, 0이 될 수 있는 수 중 가장 작은 수를 대신 0으로 정해주면 된다.
후기
이번 주는 뭔가 의욕이 없었는데 그리디라서 재밌게 풀 수 있었다.