나의 지식 보관소

연결 리스트란 여러 노드들이 각각 데이터와 포인터를 가지고 연결되어있는 자료구조이다. 각 노드의 포인터가 다음 노드나 이전 노드를 연결하는 역할을 한다. 노드라는 용어는 영어로 식물의 가지나 잎의 연결부위를 뜻하는 의미가 있는 것으로 보아, 자료구조에서의 노드가 서로 연결되어있어서 그렇게 부르는듯하다. 즉 노드는 데이터를 저장하고, 다른 데이터와 연결 지어 주는 단위 정도로 해석된다. 연결 리스트의 장점 연결 리스트는 데이터를 선형으로 저장하는 데이터 구조로서 각 노드들이 자신의 다음 노드의 주소를 가지고 있어, 배열에 비해 데이터를 추가 하거나, 삽입, 삭제가 자유롭다. 예를 들어 A, B, C라는 노드들이 있다고 가정해보자 A는 B의 주소를 B는 C의 주소를 가지고 있어 셋은 모두 연결되어 있다. 이..

추상 자료형이란 구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 가리키고 간단히 ADT라고도 부른다. 즉 전자레인지의 추상 자료형을 만든다면, 추상 자료형의 정의에는 시간 설정, 강도, 시작, 정지, 해동 등의 기능을 명시하고 내부 동작이 어떠한 방법으로 이루어지는지는 언급하지 않는다. 이러한 특성 때문에 추상 자료형은 구현자와 사용자를 분리해준다. 따라서 추상 자료형의 구현은 외부로부터 숨겨서 정보 은닉이 이루어지고 사용자는 사용방법이 아닌 구현 방법까지 알지 않아도 된다.

빅 오 표기법이란 알고리즘의 효율성을 표기해주는 표기법, 데이터의 수 n에 따른 연산 횟수를 구하는 함수 T(n)에서 가장 영향이 부분을 따지는 것, 데이터의 수 n의 증가에 따른 연산횟수의 증가 형태를 나타내는 표기법이다. 예를 들자면 T(n) = 5n^3+3n+2의 빅오는 n^3이다. 이는 n이 커질수록 n^3가 차지하는 비율이 커지므로 T(n)의 변화 정도가 n^3의 형태를 띠므로 그렇다. 위의 말을 간단히 정리하면, T(n)이 다항식으로 표현 된 경우, 최고차 항의 차수가 빅 오가 된다. 예를 들어 T(n) = 5n^3+3n+2은 O(n^3)이 된다. 위 예시에서 5n^3은 n^3이 됐는데, 최고차항의 계수는 빅오에서 중요치 않다, 왜냐하면 5n^3이나 n^3이나 n이 증가할수록 값이 증가하는 추..

알고리즘의 성능을 평가하기 위해서 시간 복잡도와 공간 복잡도라는 개념이 사용된다. 시간 복잡도는 속도에 관한 것이고, 공간 복잡도는 메모리 사용량에 관한 것이다. 하지만 알고리즘의 속도를 재기란 매우 힘든 일이다. 컴퓨터의 연산 속도에 따라 다르고, 같은 컴퓨터에서 잰다 하더라도 시간은 다르게 나오게 된다. 그래서 알고리즘의 속도를 재기 위해서는 연산 횟수를 세고, 처리할 데이터의 수 n에 대한 연산 횟수를 계산하는 함수 T(n)을 만든다. 함수 T(n)을 만드는 이유는 데이터의 수가 늘어남에 따라 연산 횟수의 변화를 알아내기 위함이다. T(n)을 구성하면 아래와 같이 그래프를 통해 데이터수에 따른 연산 횟수 변화를 한눈에 볼 수 있다. 그렇다면 위와 같이 알고리즘 A와 B가 있다고 가정해보자. 데이터가..

자료구조란 컴퓨터 과학에서 효율적인 데이터의 표현 및 저장방법을 뜻한다, 이러한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 해 준다. 따라서 알고리즘과 자료구조는 밀접한 관계이며, 자료구조에 따라 사용하는 알고리즘이 달라진다.