본문 바로가기

알고리즘 & 코딩테스트/알고리즘 공부

 (3)
진법 변환 (Base Conversion) 진법이란 무엇일까요? 진법이란 수를 표기하는 기수법의 하나로 몇 개의 기본 숫자를 이용하여 수를 표시하는 방법이다. 자리값이 올라감에 따라 수가 일정하게 커지는 규칙을 이용하고 수를 표시한다. 아라비아 숫자에 해당하는 1~9까지의 숫자를 사용하여 수를 나타내는 방식을 10진법이라고 하고 프로그래밍 영역에서는 2진법, 8진법, 16진법이 존재한다. 모든 진법은 숫자의 위치에 따라 가중치가 달라진다. 아래 그림을 보자. 예를들어 `12345 = (1 \times 10^4)+(2 \times 10^3)+(3 \times 10^2)+(4 \times 10^1)+(5 \times 10^0)`와 같은것이다. 주의깊게 봐야하는 부분은 각 진법간의 변환인데, 차례대로 알아보자. 10진수를 `N`진수로 변환하는 방식을 ..
약수의 개수와 최대공약수, 최소공배수 (Count of Divisor & GCD, LCM) 수론에서 약수(=divisor) 혹은 인수(=factor)는 어떤 수를 나누어떨어지게 하는 수를 말한다. 두 정수 `a,\;b`에 대하여 `b=ac`를 만족하는 정수 `c`가 존재한다면 `a`를 `b`의 약수라고 말하고 `a|b`로 표기한다. 모든 정수는 1과 -1을 약수로 가진다. 또한 모든 정수는 자기자신과 그 반수(더했을 때 0이 되는 수)를 약수로 가진다. 예시를 들면 이렇다. 12의 모든 양의 약수는 1,2,3,4,6,12이다. 약수는 음수일 수 있으며, 12의 모든 음의 약수는 -1, -2, -3, -4, -6, -12이다. 이제는 성질을 알아보자. 약수를 논할때 빠질 수 없는것이 바로 배수와의 관계이고, 가장 빈번하게 등장하는 개념이 최대공약수와 최소공배수일 것이다. 요거까지 정리해보자. 우..
소수와 소인수 분해 (Prime Number, Prime Factorization) 소수 (Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 의미한다. 예를 들어, 5는 1x5 혹은 5x1로, 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 소수에 해당한다. 반대개념으로 합성수(Composite Number)가 있는데 여기서는 소수에 집중해보자. 정수론의 기본 정리에 의해, 모든 자연수는 꼭 한가지 방법으로 "소수의 곱"으로 표현할 수 있고 이를 소인수 분해의 일의성이라고 한다. 즉, 곱셉의 관점에서 소수는 자연수를 이루는 성분이라 할 수 있다. 아래 예시를 보자. $$23244 = 2^2 \times 3 \times 13 \times 149$$ `23244`는 약수의 순서를 무시하면 단 1개의 방법으로 소인수 분해가 된다. 현재..

티스토리툴바