그리디 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.

어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

나중에 미칠 영향을 고려하기 보단 매 순간 가장 좋아 보이는 방법을 선택한다.

앞으로 공부할 여러 알고리즘과 달리, 사전에 외우지 않고 풀 수 있을 가능성이 높은 문제 유형이라는 점이 특징이다.

좋게 생각하면, 각 알고리즘에서 요구하는 어느 정도의 사전 지식과, 암기?를 필요로 하지는 않지만, 반대로 그 만큼 그리디 알고리즘 문제 유형 자체의 폭이 넓고, 단순 암기를 통해 모든 문제를 대처하기 어렵다는 점이 있다.

 

이는 그리디 알고리즘이 문제를 풀기 위한 최소한의 아이디어를 요구하는 능력을 필요로 하기 때문에, 문제를 잘 대처하기 위해서는 많은 유형들을 접해보고 문제를 풀어보는 훈련이 필요하다.

그리디 알고리즘 문제들을 계속 풀다보면, 특정 문제를 만나더라도 주어진 조건속에서 가장 단순히 가장 좋은 routine으로 문제를 풀어 나갈 수 있을 것이다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로, '가장 큰 순서', '가장 작은 순서'라는 조건이 알게 모르게 제시한다. 이러한 점 때문에, 그리디 알고리즘 문제를 풀 때, 정렬 알고리즘을 사용하게 된다면, 문제를 좀더 쉽고 효율적으로 접근할 수 있을 것이다.

 

거스름돈

문제 : 교재 87p 참고

 

나의 풀이

책의 해설과 거의 동일해서, 해설 코드는 추가로 올리지 않겠다.

문제 난이도가 그리 어려운 편이 아니여서, 쉽게 풀었다. 하지만, 해설을 살펴보면서 느낀 것이 있다.

이와 같은 방식은 큰 단위가 항상 작은 단위의 배수인 경우만 가능하다는 점은 생각하지 않았다. (5번째 줄의 주석) 

본인은 문제를 접한 뒤, 크게 생각하지 않고, 위와 같은 방식을 사용했지만, 생각해보니 배수의 관계가 아닌 경우에는 성립이 안된다는 것이다.

만약, 저 동전들 사이에 배수 관계가 아닌 400원과 같은 화폐가 있었더라면, 문제 접근을 다르게 해야할 뿐더러, 위와 같은 방식으로 풀었을 때는 오답이 나왔을 것이다. (이는 그리디 알고리즘 유형의 문제가 아니다.)

이러한 점들도 고려하지 않고, 무작정 풀었다는거에 조금 반성할 필요가 있다는 생각이 들었다.

문제들마다 다양한 접근 방식들이 존재하는데, 이렇게 난이도가 비교적 쉬운 문제들을 접근할 때도 사소한 예외? 오류들이 존재할 수 있기 때문에, 조금 더 꼼꼼해질 필요가 있다는 것을 느꼈다. 

 

책의 저자도 본인과 같은 경우가 많다는 생각을 했는지, 이러한 점을 언급하였다.

위 문제 뿐만 아니라 다른 그리디 문제들도 문제 풀이를 통해 최소한의 아이디어를 떠올리고, 이에 정당성을 부여할 수 있어야 한다는 것이다.

 

추가로, 위 문제는 화폐의 종류 개수만큼 반복을 수행하기 때문에, 시간 복잡도는 O(K)라고 할 수 있다.

 

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형이 떠오르지 않느다면, 그리디 알고리즘을 의심해보고, 고민해야 한다.

그럼에도 그리디 알고리즘으로 해결책을 못찾았다면, 앞으로 배울 다른 알고리즘들을 통해 해결책을 찾아봐야 할 것이다.

 

 

 

큰 수의 법칙

문제 : 교재 92p 참고

 

나의 풀이

입력값들을 받고, 배열의 값들 중에서 1, 2번째로 큰 수들을 각각 a, b 변수에 저장하였다. (변수명 정하는 연습 필요...)

가장 큰 값을 만들어야하기 때문에, a값을 최대한 더해야 한다. 

그래서, while문 내에서 a값을 k번 더하기 시작하는 것은 물론이고, 덧셈 횟수를 최대한 a값 덧셈에 많이 써야하기 때문에, b는 1번만 더하고 넘어가준다.

그래서 11~14번째에는 a값을 k번 더하고, 덧셈을 할때마다 (for문을 돌때마다), m값을 1씩 빼주고, k번 덧셈이 이뤄지면, b값을 1번 더해주고, m값도 1만 빼준다. a, b를 더하는 과정에서 m값이 0이 되었는지 확인해주고 0이 됐을 때, 즉시 while문을 빠져나와서 덧셈의 결과 result을 출력해준다.

 

 

해당 문제 또한 난이도가 쉬운 편이다. 해설 코드를 참고하고 난 뒤의 코드를 확인해보면

난이도가 있는 문제가 아니기 때문에, 코드 길이에서 차이가 막 나지는 않지만 조금 더 간결하게 보인다.

가시적인 부분 뿐만 아니라 반복문을 사용하지 않고, 한번에 값을 도출한 것을 보면, 만약 k가 큰값이 입력됐더라면, 본인의 이전 코드에서는 그만큼 while문에서 계속 그만큼 반복 연산이 일어났을 것이다. 즉 비효율적인 코드인 것이다.

이 문제 또한 풀긴 했지만, 그리디 알고리즘 유형에서 요구되는 방식은 아니였던 것이다....;;

 

 

 

숫자 카드 게임

문제 : 교재 96p 참고

 

나의 풀이

행렬값들을 입력받고, 각 행에서 최솟값과 해당 최솟값들 중에서 최댓값을 구하기 위해, for문으로 각 행의 값들을 오름차순으로 정렬하여, 각 행렬의 첫번째 값들을 최솟값들로 들었고, 다음 for문으로 각 행의 첫 번째 값들을 max method를 통해서 쉽게 최댓값을 도출하였다.

 

 

2가지 방식의 해설코드

본인은 나름 깔끔하게 풀었다고 생각했지만, 오산이었다.

해설코드에는 배열을 만들고 굳이 저장해서 활용하지 않았다.

본인은 for문으로 배열을 입력받고, for문으로 각 행의 값들을 정렬하고, 또 for문으로 최댓값을 각 행마다 비교하였다.

쓸데없이 for문을 3번이나 쓴것이다.

해설 코드는 단순히 입력받았을 당시부터 비교를 시작하여 최솟값만 다른 변수에 옮겨두고 끝난다. 

n값에 엄청 큰 수가 입력됐더라면, for문으로 그만큼 의미없는 연산을 엄청 했을 것이다. ;;;

 

 

 

1이 될 때까지

문제 : 교재 99p 참고

 

나의 풀이

해설 코드 2가지가 있었지만, 필자의 의도대로 한 코드와 비슷하기 때문에 해설 코드는 생략한다.

일단 본인의 코드를 설명하자면, 아무래도 n값을 1로 만드는 과정에서, n 값에 대하여 뺄셈을 할 때마다 연산 횟수를 증가시키는 것보다 나눗셈을 통해 한꺼번에 n값을 줄여나가며 연산 횟수를 증가시키는 것이 확실히 연산횟수를 최소화하는 방법이다.

그렇기 때문에 최대한 나눗셈을 많이 해야 하는데, 나눗셈을 하기 위한 조건은 나머지가 0이어야 한다.

그렇기 때문에, 어쩔 수 없이 n값이 k로 나누어 떨어질 수 있는 값이 되기 위해서, n값에 k로 나눠서 만들어지는 나머지 값 x만큼 n에서 빼고, x만큼 뺏기 때문에 그만큼 연산 횟수를 증가시켜준다. 

n값이 이제 k로 나눠떨어지기 때문에, 나눗셈을 하고 연산 횟수를 1 증가시켜준다. 

이와 같은 과정을 반복하고, 이제 n이 k보다 작다면 반복문에서 벗어나고, 이제 n을 k로 나눌 수 없기 때문에, n에서 1이 되기 위해 빼야하는 만큼 연산횟수를 더해준다.

 

1번째 해설코드는 이전에 본인이 했던 실수와 비슷한 유형으로, 본인의 코드처럼 뺄셈 연산이 얼마나 나올 것인지를 계산 후 그 만큼 연산 횟수를 더한 것과는 다르게 반복문을 통해서 뺄셈을 할때마다 연산 횟수를 1씩 증가시키는 방식이었다. 

그래도 필자의 의도대로 풀었다는 것에 기분이 좋았다. 물론 쉬운 문제이긴 하지만......

 

 

 

느낀점

처음 코딩테스트 공부를 해보고 블로그에 글을 올려본다. 그리디 part의 문제들을 풀어봤는데, 문제의 난이도는 아직까진 비교적 평이해서 문제 자체를 못 풀겠다는 아니었지만, 접근 방식에서 뭔가 뒷통수 맞은 느낌?이 들었던거 같다.

풀긴했지만 효율적인 방법이 아니었고, 만약 코드의 실행시간 제한을 넘어, 오답인 코드라고 하여도 할 말이 없을 것 같다.

문제가 풀만 하더라도, 이게 과연 좋은 방식으로 풀었나에 대해 계속 생각해보게 되는 것 같다.

아 그리고, 계속 블로그 글을 작성하면서 변수명 좀 잘 지어야겠다는 생각이 계속 든다....;;;

 

기말고사가 끝나고, "이것이 취업을 위한 코딩테스트다. with 파이썬" 교재를 구매 후, 코딩 테스트 공부를 시작했지만, 당장 내일부터 계절학기 시작이라, 앞으로 진도가 얼만큼 나갈지는 미지수이다..... 

 

 

 

만약 이 글을 읽고 있는 사람이 존재한다면, 어떠한 피드백 환영입니다.

블로그 작성코드 부분이든, 글의 내용이든, 블로그 관련된 것이든 부족하고나 수정이 필요한 부분이 눈에 보인다면, 피드백 부탁드립니다.