DNF LOVE

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

프로그래밍을 하다보면 각 특징에 맞게 효율적으로 데이터를 담는 자료구조가 존재한다.이 포스팅은 다양한 자료구조의 종류와 각 특징의 간단 정리를 하는 글이다.- 자료구조의 분류자료구조는 크게 두 분류로 나뉘어진다. 바로 선형구조와 비선형 구조이다. ■ 선형구조 : 선형 리스트(배열), 연결 리스트, 스택, 큐, 데크 ■ 비선형구조 : 트리, 그래프선형구조란? 자료를 구성하는 원소들은 순차적으로 나열시킨 형태를 의미한다. 어떤 연산들을 수행할 수 있느냐에 따라 세부적으로 나뉠 수 있다.비선형구조란? 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태를 의미한다.그림으로 보면 더 이해하기가 쉬울 것이다.선형구조는 아래와 같이 1부터 4까지 순차적으로 원소를 나열시키는 형태이며,비선형구조는 아래와 같이 하나..

* 자료구조의 가장 간단한 부분인 리스트이다. 저번 학기에 도전했던 몇몇 회사 필테에 링크드리스트 구현 코드가 나왔었다. 기초가 부족했던 나는 폭망했다 ㅎ... 그래서 종강하면 바로 링크드리스트부터 공부해야겠구나 마음을 먹었다. 강하고 보름 내내 놀다가 이틀정도 공부했다. ㅎ 그래서 조금 허접하다. 암튼, 각색하고 리스트를 알기 전에 우선 가장 기본적인 배열을 알아보도록 하자. 배열의 가장 큰 특징은 인덱스를 가지고 있고, 초기에 배열의 크기가 정해진다. 그러고 인덱스 0부터 주어진 배열의 크기 -1 까지 데이터가 해당 인덱스에 따라 데이터를 여러개 가질 수 있는 자료구조이다. 그렇다면 리스트는 무엇인가? 리스트에는 크게 두 가지 종류가 있다. 바로 순차리스트와 연결 리스트다. 1. 순차 리스트 : 배열..