[알고리즘 성능 상향] 배열 사용 시 성능을 향상시킬 수 있는 방법(LUT)

공간 복잡도는 낮지만 시간 복잡도가 굉장히 높은 경우 어떻게 해야할까?

그럴때에는 보통 공간(메모리)을 사용하여 시간 복잡도를 낮추는 방법이 있다.

시간 복잡도를 안좋게 하는 가장 대표적인 일이 '불필요한 연산'이다. 

계산하는 과정에서 발생하는 불필요한 연산/정보는 자료구조 중 가장 많이 쓰이는 배열에서는 어떻게 해결할까? 공간과 배열의 특징, 'Index'를 활용한다. Index를 통한 배열의 검색의 시간 복잡도는 O(1)이다.

아래 영상처리 개념을 예시로 설명해 보도록 하겠다.

---

원본 영상에서 명암을 15씩 증가하여 밝기를 높이는 영상처리를 만든다고 가정해보자.

영상처리에서 이러한 기법을 LUT(Look-up Table)이라 한다. LUT연산은 산술 연산을 고속으로 수행할 때 사용한다.

이는 LUT로 사용할 배열의 인덱스를, 원본 화소값으로 하고, LUT로 사용할 배열의 원소값을 산술 연산 후 새로운 화소값이 된다.

말로 설명하면 잘 이해하기 어려우니 그림과 함꼐 설명하도록 하겠다.

이 LUT기법을 사용하면 불필요한 계산을 방지하여 포인트 처리의 효율성을 증대한다. 즉, 시간 효율 상 좋기 때문에 시간 복잡도를 낮출 수 있다.

후 PPT장인이 되어가는 것 같다.

원본 영상의 변수 명을 img라 하고, LUT는 lut, 계산 후 영상의 변수 명을 out이라 하자.

원본 영상 img[3][0]의 원본 데이터 값은 '3'이다. lut는 이 값을 인덱스로 삼는 다는 것이다.

즉, img[3][0]은 lut[img[3][0]]을 가리키게 된다는 것이다. 이것을 원본에서 15 증가 되는 것을 연산해보자

lut[img[3][0]] = img[3][0] + 15; 이렇게 될 것이다.

그렇다면 out은 이를 어떻게 데이터를 참조할까?

out[3][0] = lut[img[3][0]] 이렇게 사용할 수 있다.

코드를 보도록 하자.

for(int i = 0; i < 7; i++){
    lut[i] = i + 15;
}

for(int i = 0; i < 4; i++){
    for(int j = 0; j < 4; j++){
        out[i][j] = lut[img[i][j]];
    }
}

위의 코드는 LUT기법을 사용했을 때다. 

for(int i = 0; i < 4; i++){
    for(int j = 0; j < 4; j++){
        out[i][j] = img[i][j] + 15;
    }
}

그 다음 코드는 LUT를 사용하지 않을 때의 코드이다.

반복 횟수가 적은 지금은 별 차이가 없어 보이지만 횟수가 커지면 커질 수록 for문을 돌때마다 계산량이 증가되기 때문에 시간이 좀 더 오래걸리게 된다.

---

알고리즘에서 이 기법을 사용하는 경우는 조금 다르지만, 쓰임새는 어쨌든 이렇게 사용한다.

알고리즘 문제를 풀다보면 개별데이터의 횟수를 구하기 위해 매번 전체 데이터를 조회하는 경우(2중, 3중 for문 사용)가 많을 것이다.

반대로 전체 데이터를 한 번 조회하는 과정에서 각 개별 데이터의 등장 횟수를 구하는 방법이 바로 위와 같은 기법이다. 

이를 사용할 땐 어떤 공간에 어떤 기준으로 저장할 것인지를 잘 알고 구현하는 것이 중요하다.