알고리즘3 최대 부분합 문제 Maximum Subarray 파헤치기 안녕하세요 블레이즈 테크노트 블레이즈 입니다. 여태까지 삽입 정렬과 합병 정렬에 대해서 살펴봤습니다. 특히 합병 정렬을 다루면서 Divide-Conquer (분할정복)에 대해서 다루었는데요, 이번에는 또 다른 Divide and Conquer (분할정복) 알고리즘인 최대 부분합 문제를 파헤쳐보도록 하겠습니다. 최대 부분합 문제는 주식 판매 수익을 최대화하는 문제로 설명할 수 있습니다. 주어진 기간동안 주식 가격이 있다면 언제 사서 언제 팔아야 할까요?? 당연히 가장 싼 날 주식을 사서 가장 비싼 날 팔아야 겠죠? 이를 최대 부분합 문제, Maximum Subarray Problem이라고 합니다. 위 그림을 보면 2일에 사서 5일에 팔면 될 것 같습니다. 그렇다면 이 문제를 어떻게 알고리즘화할 수 있을지 .. 2023. 10. 9. 알고리즘의 정의와 삽입정렬 InsertionSort 파헤치기 안녕하세요 블레이즈 테크노트 블레이즈 입니다. 이번 포스트에서는 알고리즘에 대해서 공부해보고자 합니다. 알고리즘 Algorithm이란 무엇일까요? 제가 배운 바에 의하면 그 정의는 다음과 같습니다. An Algorithm is a sequence of computational steps that transform the input into the output. 이를 보면 input과 output이 굉장히 중요하다는 것을 알 수 있습니다. 가장 대표적인 알고리즘이 sorting problem입니다. 이 sorting을 효율적으로 할 수 있기 때문에 컴퓨터가 단순히 계산기를 넘어 그 이상의 가치를 발휘하기 시작했다고 볼 수 있습니다. 이번 포스트에서 먼저 살펴볼 것은 삽입정렬 InsertionSort 입니다.. 2023. 9. 22. 이산수학 10. 재귀 알고리즘과 개수 세기(Counting) 안녕하세요 블레이즈입니다. 첫 번째 문제입니다. 이 문제는 비트 문자열을 뒤집는 재귀적 알고리즘을 짜보는 문제입니다. 두 번째 문제입니다. 이 문제는 상당히 어려웠습니다. 파티에 온 사람들 중 지인의 수가 동일한 사람이 최소 두 명 이상 존재하는지 증명하는 문제입니다. 감사합니다. 블레이즈의 테크 노트. 2023. 7. 10. 이전 1 다음
