소소한 코딩일지

오늘은 동적 계획법(Dynamic Programming)에 대해 정리하려고 합니다. 그리디 알고리즘(Greedy Algorithm) 코딩 문제를 풀다가 그리디 알고리즘(Greedy Algorithm) 정리가 필요할 거 같아서 정리하던 도중 동적 계획법(Dynamic Programming)에 대해서도 정리하면 좋을 것 같아 정리하려 합니다. 동적 계획법은 '큰 문제를 작은 문제로 나누어 푸는 방법' 입니다. 동적 계획법은 분할 정복(Divide and Conquer)과 문제를 작은 단위로 분해한다는 비슷한 점이 있습니다. (분할 정복은 문제를 나눌 수 없을 때까지 쪼갠 후 하나씩 처리하면서 결과를 합치는 알고리즘입니다.) 하지만 동적 계획법과 분할 정복의 가장 큰 차이점은 같은 연산을 중복하냐 안 하냐의 ..

이번 문제는 수 정렬하기 3입니다. 처음 문제만 딱 보았을 땐 sort()로 간단하게 풀면 되겠다 해서 바로 풀고 제출했지만, 출제의도가 그게 아니었더라고요.... 많은 분들이 계수 정렬(Counting Sort)을 사용해서 푸셨더라고요... 저는 계수 정렬이라는 개념이 전혀 없어서 구글링을 통해 처음 이해하고 풀었습니다... 제가 푼 코드는 계수 정렬과 조금 다른 점이 있긴 하지만 정렬할 배열의 개수를 카운트해서, 카운트 한 값의 인덱스 값을 사용했다는 점은 약간 유사하다고 생각합니다. 아래 링크는 제가 정리한 계수 정렬에 대한 내용입니다! 2020/07/14 - [알고리즘] - [알고리즘] 2. 계수 정렬(카운팅 정렬 / Counting Sort) [알고리즘] 2. 계수 정렬(카운팅 정렬 / Coun..

백준 문제를 풀다가 정말 쉬운 문제인 줄 알고 제 방식대로 풀었다가... 계속 틀려서... https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 다른 분들 질문을 보니 카운팅 정렬, 계수 정렬을 사용해서 풀면 풀린다고 하셔서 인터넷 폭풍 검색으로 풀고 이 부분을 처음 접해서 블로그에 남겨놓으면 혹시 다른 분이나 이후에 도움이 될 것 같아 간략하게 정리하려 합니다. Counting sort라고 불리는 이유가 리스트 내 요소의 개수를 파악하여 정렬하기 때문입니다. 다음과..