DNF LOVE

공간 복잡도는 낮지만 시간 복잡도가 굉장히 높은 경우 어떻게 해야할까? 그럴때에는 보통 공간(메모리)을 사용하여 시간 복잡도를 낮추는 방법이 있다. 시간 복잡도를 안좋게 하는 가장 대표적인 일이 '불필요한 연산'이다. 계산하는 과정에서 발생하는 불필요한 연산/정보는 자료구조 중 가장 많이 쓰이는 배열에서는 어떻게 해결할까? 공간과 배열의 특징, 'Index'를 활용한다. Index를 통한 배열의 검색의 시간 복잡도는 O(1)이다. 아래 영상처리 개념을 예시로 설명해 보도록 하겠다. 원본 영상에서 명암을 15씩 증가하여 밝기를 높이는 영상처리를 만든다고 가정해보자. 영상처리에서 이러한 기법을 LUT(Look-up Table)이라 한다. LUT연산은 산술 연산을 고속으로 수행할 때 사용한다. 이는 LUT로 ..

https://dnf-lover.tistory.com/2 이전에 우리는 '시간복잡도'의 개념에 대해 배웠다.그렇다면 이 시간복잡도 즉, 연산량을 줄이는 방법은 무엇이 있을까? 1. 시간 복잡도의 한계실제 연산량을 계산할 때, 함수의 계수와 낮은 랭크의 항을 무시하게 되기 때문에 실제 연산량과 시간 복잡도를 통해 계산한 연산량의 차이가 클 수 있다. 또, 함수들은 값의 범위에 따라 대소 관계가 다르다는 점때문에 낮은 랭크의 시간 복잡도가 항상 높은 랭크의 시간 복잡도보다 적은 연산량을 보장하지 않는다.위의 그래프를 보면, 길게 보았을 때에는 제곱근들에 비해 Y = X가 더 퍼포먼스가 좋지만, X축이 1이하일 때 퍼포먼스는 y = X 보다 y = X^2 혹은 X^3의 퍼포먼스가 더 좋다는 것을 확인할 수 있..

알고리즘 시험 유형 중 가장 기본 중 기본이 소인수 분해, 약수 구하기가 아닌가 싶다. 당연히 '약수를 구하는 알고리즘을 구현하시오'가 아닌 약수를 이용한 심화된 알고리즘을 풀어야 한다. [약수 구하기] '약수'란, 어떤 수로 정수가 나누어떨어지는것을 대하여 이르는 말이다. 그리고 1과 자기자신으로밖에 나누어 떨어지지 않는 수를 우리는 소수라고 부른다. 그렇다면 약수를 알고리즘 화 시키는 것은 어떻게 해야할까? 약수의 정의를 조금 다르게 해보자. 어떤 자연수 a, b가 있을 때 a를 b로 나누었을 때 나머지가 0이면 b는 a의 약수라 한다. 이렇게 정의를 알고리즘 화시켜보면 if문과 for문을 어떻게 활용해야할지 감이 잡히게 된다, import java.util.*; public class divisor..