반응형 백준10803 [cs준비] 그리디 알고리즘이란? 그리디 알고리즘이란 여러 경우 중 매 순간 최적이라고 생각되는 선택지를 선택하는 방식으로 진행해서 최종적으로 값을 구하는 방식이다 따라서 특정 문제를 만났을 때 단순히 현재 상황에서 최적이라고 생각하는 답만 골랐을 때에도 문제를 정상적으로 풀 수 있는지를 고려하는 것이 가장 중요하다. 대표적인 예시로는 동전문제, 회의실 문제 등이 있다. 동전 문제는 거스름돈을 거슬러 줄 때 가장 적은 수의 동전을 가지고 거슬러 주는 문제인데 이 때에는 동전들을 내림차순 정렬한 뒤 가장 큰 동전부터 비교해가면서 거슬러 주면 된다. - 현재 기준에서 가장 큰 동전 말고 더 좋은 선택지가 없기 때문에 이런식으로 구하다 보면 거스름돈을 위한 최소한의 동전 개수를 고를 수 있다. - 하지만 배수가 되지않는 금액 [ex)100, .. 2021. 8. 18. 백준 1080. 행렬 🅰 백준 1080. 행렬 ✏️ 문제 풀이 행렬을 변환하는 연산은 3X3 행렬을 뒤집는 것이다. 그러므로 행렬이 3보다 작을 때, 행렬이 3보다 클 때 2가지 경우를 생각하였다. 1. 행렬이 3보다 작을 때 두 행렬이 같으면 0 출력 / drawCnt변수를 이용하여 같으면++ 해주고 drawCnt = N*M이면 같다고 출력 두 행렬이 다르면 -1 출력 2. 행렬이 3보다 클 때 데이터를 입력받을 때 boolean배열을 이용하여 데이터가 두 데이터가 같으면 true, 틀리면 false로 저장을 했다. boolean배열을 탐색하면서 false라면 그 부분부터 시작해서 3*3행렬만큼 true->false, false->true로 변경해주고 cnt를 이용하여 변경한 횟수를 카운트 해주었다. 모든 배열을 변경 완료.. 2021. 8. 18. 백준 1080. 행렬 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0) 이 문제가 그리디 알고리즘인 이유 Q1. 3 * 3행렬로 가장 많이 변경할 수 있는 것이 최적의 해가 아닌가요? 많이 변경함으로써 전체적으로 변경해야할 수가 줄어든 거니깐요. → 뒤집는 연산의 특성상 많이 변경하는 것은 의미가 없습니다. 따라서 최적의 해에 가까워진다고 볼 수 없습니다. Q2. 이게 왜 최적의 해가 되는 건가요? 그냥 순서대로 뒤집어 보다가 단순히 맞추는 것이 아닌가요? 그것이 어떻게 최저횟수가 되는지 모르겠습니다. → 이 문제의.. 2021. 8. 13. 이전 1 다음
