728x90 백준플래/Greedy5 백준 2727, 2,3 거듭제곱의 합 개요 문제 링크 플래 4, Greedy N을 약수/배수의 관계가 아닌 2,3의 거듭제곱의 합으로 표현하기 접근 그리디, 백트래킹을 잘 활용하면 되는 문제, 만약 재귀함수 내에서 for문을 두 개 쓰고 있다면 하나로 줄일 방법을 잘 생각하면 되고 그게 그리디한 요소가 된다. 문제 검색은 최후의 상황이 아니면 잘 안하는데 많이 답답해서 블로그를 참조했다. 들어가자마자 결합법칙이라는 단어를 보고 아 이거였구나 싶었다. 떠올리기 어렵긴 하지만 좀 더 고민해볼 걸 싶었다. 핵심은 이렇다. 문제를 풀다보면, 약수/배수 관계를 만들지 않기 위해 어떤 두 (a,b)쌍에 대해 a1 2023. 3. 18. 백준 2873, 롤러코스터 개요 문제 링크 플래 3, Greedy 경로의 이득의 총합이 최대가 되도록 경로를 구성해 출력하기 접근 이게 왜 그리디일까 싶은 느낌이 드는데 천천히 이해하다보면 충분히 그리디함을 알 수 있다. 우선 모든 점의 값이 양수이니 최대한 많은 점을 훑는게 이득이다. 홀수×홀수나 홀수×짝수 형태의 맵에서는 모든 점을 돌아볼 수 있다. 그래서 여기까지는 쉽다. 만약 가로가 홀수라면 세로로, 세로가 홀수라면 가로로 지그재그로 움직여줘야 모든 점을 돌 수 있다. 이 부분만 재귀적으로 잘 구현해주면 크게 어렵지 않다. 문제는 짝수 × 짝수 인 경우인데, 이때는 최솟값이 있는 점을 거르고 탐색하는 것이 가장 이득이다. 점을 하나만 걸러도 나머지 모든 점을 지날 수 있기 때문인데, 질문게시판의 수많은 질문들에서도 다루듯이.. 2023. 3. 17. 백준 10803, 정사각형 만들기 개요 문제 링크 플래 3, Greedy, DP N×M크기의 직사각형을 최소 개수의 정사각형으로 나누기 접근 내 하루를 앗아간 그리디 & 메모이제이션 DP문제, 사실 접근은 분할정복에 더 가까운 것 같다. 증명 시도했는데 처참히 털렸다. 시간날 때마다 도전해보고 성공하면 수정하려고 한다. 어디가 그리디인가? 싶을 수 있는데 N이 10000이니까 N^2을 돌리지 않게 하기 위해 그리디를 사용한다. 처음에는 N,M루프를 돌면서 왼쪽 위 정사각형을 하나 만들고 남은 L자 모양의 구간을 두 가지 방법으로 잘라서 최솟값을 구하는 방식으로 진행했다. 그런데 이 방법은 최선이 아니다. L자 모양을 두개의 직사각형으로 자르지 않는 것이 최선이 될 수 있는데, 아래 예시를 보자. N=72, M=35이다. 왼쪽 위 15만큼.. 2023. 3. 17. 백준 13146, 같은 수로 만들기 2 개요 문제 링크 플래 5, Greedy, 스택 서로 같은 수를 그룹지어 1씩 추가할 때, 모든 수가 같아지도록 만드는 최소 시행 수 접근 세그트리인가? 하는 생각이 잠깐 지나갔지만, 스택인 걸 보면 크게 어렵지 않게 풀 수 있겠다. 괄호의 균형을 따지는 문제와 비슷한 느낌이라고 보면 될 것 같다. 우선 핵심은 극솟값을 찾는 것이다. 극솟값이 존재할 때까지 시행을 계속 해주면 되는데, 미분이라도 때리면 참 좋겠지만, 리스트니까 이렇게 해야 한다. 극솟값은 지금까지 들어온 값보다 작고, 다음에 들어올 값이 더 큰 지점에 있다. 이때 시행 횟수는 새로 들어올 값과의 차이이다. 그런데 이 차이는 한번만 더해주면 된다. 그리고 새로 들어올 값보다 작은 수는 모두 스택에서 빼버린다. 한 번만 더해주면 나머지는 의미.. 2023. 3. 14. 백준 1071, 소트 개요 문제 링크 플래 5, Greedy a[i+1] != a[i]+1이면서 사전순으로 가장 앞서게 정렬하기 접근 그리디한 인간이 되자. 수를 꺼내서 출력한다고 생각할 때, 가장 작은수부터 꺼내는 것이 가장 유리하다. 이 수를 X라고 해보자. 꺼낼 수 없는 첫 번째 경우. X가 (이전 수)+1인 경우에는 X+1부터 시작되는 최솟값을 다시 구한다. 이게 왜 되느냐? X보다 작은 수는 없다. 그러면 다음 최선 선택지는 항상 X보다 크다. 꺼낼 수 없는 두 번째 경우이자 이 문제의 핵심. X와 X+1만 남은 경우이다. 예를들어 2,2,3,3만 남은 경우 2를 먼저 뽑을 수 없다. 어떻게 뽑아도 2뒤에 3이 오는 경우가 생긴다. 그럼 두 번째 경우를 커버하기 위해 X+1부터 최솟값을 구한다. 그 값을 T라 했을 .. 2023. 3. 10. 다음 728x90
