간만에 블로그를 쓴다... 자주 쓰고자 다짐했지만..쩝하지만! 지금부터라도 열심히 쓰면 되지 ㅎㅎ오늘은 그리디 알고리즘(Greedy Algorithm)에 대해서 여러 블로그의 내용을 토대로 공부한 내용을 정리해보고자 한다. 👺그리디 알고리즘에 대해서욕심쟁이 기법이니까 욕심 많을 것 같은 이모티콘으로 선정해보았다 ㅋㅋ- 선택의 순간마다 당장 눈 앞에 보이는 최적의 기법으로 선택하여 최종적인 해답에 도달하는 알고리즘이다.- 그 최종적인 답이 최적의 해라는 보장은 없다. => 순간마다 하는 선택은 지역적으로 최적이지만, 전역적으로 최적이라고 보장 못함- 최적의 값의 근사값을 목표로 함- 그리디 알고리즘이 적용될 수 있는 문제는 지역적, 전역적 모두 최적인 문제이어야 한다. 🤑 그리디 알고리즘 문제 풀이 ..

이번에는 분할 정복에 대해서 알아보려고 한다. 마찬가지로 알고리즘에서 수업했던 교재를 통해 복습했고 그 책 내용을 바탕으로 글을 써보려고 한다. 확실히 블로그에 글을 남기면서 복습이 되고, 나중에 기억이 안날때도 찾아보기가 쉬워서 더욱 자주 글을 쓰도록 해야겠다... 제발.. 분할 정복(Divide and Conquer) 이란, 문제의 입력 사례를 두 개 이상의 작은 입력 사례로 분할하는 것을 뜻한다. 딱 봐도 저번에 학습했던 DP 보단 훨씬 이해하기 쉬워보인다. 분할한 입력 사례의 답을 바로 얻을 수 있으면, 원래 문제의 답은 얻은 답들을 통합하여 구할 수 있다. 반면에, 답을 구하지 못하였다면, 더 작은 입력 사례로 다시 분할하고, 답을 구할 수 있을 만큼 충분히 작아질 때까지 분할을 계속 한다 정렬..

오늘은 알고리즘의 주요 유형 중 하나인 DP에 대해 정리해보려고 한다. 이제 새로운 한해가 되었으니 차곡차곡 블로그를 써보려고 한다!! 1. 개념 DP란 무엇인가.. Dynamic Programming이다. 한국말로 하면 동적 계획법이다. 이게 뭐냐해서 공부를 해봤다. DP는 문제의 입력사례를 분할하여 문제를 푼다는 점에서 분할 정복과 비슷하다. 가장 기본적인 개념은 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 것이다. 그래서 이 동적 계획의 개발 절차를 책으로 찾아보니까... 1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식(recursive property)을 세운다. 2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구한다. - 이렇게 아주 ..