justlog

Algorithm

• Dynamic Programming

  Algorithm 2022. 4. 14. 13:51

  정의 우리말로 동적 계획법이라고 번역되어지는 말입니다. 우선 명칭에 대해서 좀 어색할 수 있다. 이는 해당 어원이 오래되었기 때문입니다. 당시에 programming이란 문제 풀이를 위한 planning(계획) 정도로 생각했습니다. 따라서, Dynamic Programming이 의미하는 바는 다단계 처리에 대한 최적화된 계획법 정도로 해석할 수 있습니다. Dynamic Programming을 사용하기 위해서는 해당 문제가 다음과 같은 조건을 만족할 때입니다. Optimal Substructure Overlapping Subproblem Optimal Substructure란 문제의 최적해가 이것의 하위 문제(subproblem)의 최적해에 의해서 정의되어질 수 있어야 한다는 것입니다. 쉽게 말해서 수열의..

  Read More
• Brute Force

  Algorithm 2022. 4. 4. 10:01

  우리가 알고리즘을 생각할 때, 가장 먼저 떠올릴 수 있는 방법 중에 하나입니다. 가장 기본적인 알고리즘이기 때문에, 굳이 설명을 하지 않아도 자연스럽게 채득하는 경우가 대부분이지만, 사고의 틀을 정하여 더 빠르게 답을 찾을 수 있습니다. Brute Force를 직접적으로 번역하면, 이는 "무차별 대입"정도로 생각할 수 있습니다. 이는 여러 가지의 경우의 수에서 최적의 답이 한 개 이상 존재할 때, 모든 경우의 수를 하나하나 대입해보면서, 정답이 맞는지를 확인하는 방식입니다. 즉, 가능한 모든 경우를 만들고, 그 후에 이것이 정답인지를 계속해서 확인하는 과정이 알고리즘의 핵심입니다. 가장 흔한 예시가 해커들이 특정 유저의 password를 알아내기 위해서 모든 경우의 수를 대입하여 확인하는 것이 있습니다...

  Read More
• Modulo

  Algorithm 2022. 4. 1. 15:28

  해당 Posting에서는 Modulo연산의 정의와 특징을 이해하고, 이를 이용한 알고리즘을 소개합니다. 사칙연산과 같은 연산자입니다. 하지만, modulo 연산은 기존 사칙연산과는 다른 다양한 특징을 가지기 때문에, 이를 정리하고 이해하는 것은 중요합니다. 우선 modulo 연산이란 무엇인지부터 알아야 합니다. $$a = bq + r$$ $$r = a \mod b = a \mod q$$ ex. $100 \mod 3 = 1$ $12 \mod 32 = 12$ $123 \mod 11 = 2$ $1 \mod 1 = 0$ 로 정의할 수 있습니다. 쉽게 말해서, a와 b에 대해서, 나눗셈한 나머지를 반환하는 연산자입니다. 이는 여러 programming language에서는 % 표기로 나타내는 경우가 많습니다. 따..

  Read More