프로그래밍은 데이터를 처리하는 다양한 방법을 연구하는 분야입니다. 처리하는 데이터는 연산이나 생성하는 과정에서 처리되는 기본 엔티티죠. 데이터는 숫자가 되기도 하고 문자나 문자열이 되기도 합니다. 프로그래밍 언어에 따라 조금씩 다르지만, 각각의 숫자를 대입할 수 있는 자료형이 있고 문자열을 대입할 수 있는 자료형이 있습니다. 이들 자료형에 의해 구별되는 데이터를 조직하고 처리하는 것이 체계화되면 자료구조가 되는 것이죠.
자료구조는 데이터를 효과적으로 처리하게 위해 구조로 만든 코드의 표현 방법입니다. 필요에 따라 서로 다른 자료구조가 주어져 있고 프로그래머는 이 주어진 조건에 맞게 자료구조를 코딩해서 운용합니다. 각기 다른 자료구조는 자료를 저장하는 자료형으로 된 변수를 포함하며 이 자료를 토대로 메모리를 점유하고 규칙적인 엑세스가 가능하게 해줍니다.
제가 참고한 책에서는 아래 도식을 보여줍니다.
알고리즘 + 자료구조 = 프로그램
위에서 나온 것처럼 자료구조는 빌딩 블록으로도 흔히 유비됩니다. 복잡도가 높은 처리 목적을 알고리즘으로 분해해서 정의하고, 자료구조로 조직화해서 처리하는 구조인 것이죠. 자료구조는 얼핏 무질서한 프로그래머가 아무 생각없이 의식 흐름대로 코드를 만들때 방만해지는 결과를 막아주기도 하구요. 특정 코드에서 특정 데이터를 저장하고 꺼내오는 규칙화된 구조를 토대로 효력을 발휘합니다. 한마디로 데이터의 규칙적 접근을 돕고 효율적인 처리에 기준이 되는 것입니다.
위의 도식을 세분화하면 이렇습니다.
자료구조 = 조직화된 데이터 + 처리 작업들
한편 자료구조는 알고리즘과 함께 그 위력을 발휘합니다. 알고리즘이 수학적인 문제 해결을 위한 절차를 정의하는데 쓰인다면 그 실재 데이터 처리의 코드는 자료구조가 일부가 됩니다. 자료구조가 알고리즘이 처리하는 데이터들을 조직하고 접근이 용이하게 한다면 알고리즘은 구체적은 처리 작업을 구현하는 구조입니다. 정규화 작업을 토대로 수학적 알고리즘(느슨한 규칙적인 알고리즘 전단계)이 정규화된 언어로 번안되고, 실재 프로그램 언어가 제공하는 틀 안에서 자료구조가 관여해서 알고리즘이 작동합니다. 보통 자료구조책에서도 알고리즘을 조금 다루고, 알고리즘책에서 자료구조를 다루는 것과 같이 서로 밀접한 연관성이 있는 주제죠.
알고리즘을 분석하는 여러 전제 중에서는 처리 복잡도가 있습니다. 아래 두가지 복잡도가 있습니다..
- 공간 복잡도
- 시간 복잡도
시간 복잡도는 알고리즘 수행시간을 측정해서 알 수 있는 실행 시간을 의미합니다. 알고리즘은 정련하면 할수록 실행 시간을 빠르게 해주며 이 시간적인 측정을 정식화하면 Big-O 표기법이 유의되게 됩니다. 공간 복잡도는 메모리 상의 공간을 얼마나 적게 점유하느냐의 조건인데 요즘은 메모리가 매우 용량이 커서 무시되기도 하지만, 여전히 중요하게 여겨지기도 합니다.
- 공간복잡도 예 – 제한된 자원을 쓰는 웹호스팅에서 얼마나 많은 동접자를 동시에 처리하는 램을 효율적으로 할당할 것인가?
- 인스트럭션 공간 – 실행된 버전의 프로그램을 적재하는 공간
- 데이터 공간 – 상수 (고정된 메모리 공간), 고정된 크기의 변수 (배열), 동적으로 할당된 공간 (연결리스트)
- 스택 공간 – 도중에 서스펜드된 기능을 이어가기 위한 적재 공간
- 시간복잡도
- 최선의 경우, 평균적인 경우, 최악의 경우
시공간 타협안의 개념은 프로그램을 작성할때 가장 적은 공간복잡도에 가장 빠른 시간복잡도를 추구한다는데서 중요합니다. 두가지 조건은 때때로 하나가 달성되면 다른 하나가 타협을 해야 하기도 하고 둘다 비효율적이 되기도 합니다. 이런 복잡도를 낮추는 것은 정련된 알고리즘과 함께, 잘 고안된 자료구조의 구현과 밀접한 연관성이 있습니다. 빅데이터를 처리하면서 연결리스트를 쓴다든지, 그해 입학생들의 수에 맞게 배열 변수를 할당해서 쓰는 것과 같은 기초적인 타협안뿐아니라, 여러 조건을 미리 예상하고 이에 맞추어 효율적인 코드를 작성하는 것이 줒요합니다.
Big-O 표기법은 실행시간을 함수처럼 나타낸 것으로, O(1) 과 같은 상수 시간, Olog(n) 같은 로그 시간, 선형 시간 O(n), 다항 시간, 지수 시간 등으로 나누어지며 이들이 왜 측정되는지, 어떤 기준에 따르는지는 https://www.google.com/search?q=big-o+%ED%91%9C%EA%B8%B0%EB%B2%95&rlz=1C1ASUM_enCA1030CA1030&oq=big-o+%ED%91%9C%EA%B8%B0%EB%B2%95&aqs=chrome..69i57j0i512j0i13i30j0i5i13i30.7523j0j7&sourceid=chrome&ie=UTF-8 를 참고하시길.
Big-O 표기법의 한계는
- 표기법 자체는 프로그램을 어떻게 효율화해야 하는지 말하지 않는다. 그저 복잡도를 보여주기만 한다
- 표기법은 구체적인 증가값이나 하락갑에 따른 속도 측정의 비교가 기준을 엄격하게 모두 다루지 않으면, Big-O 표기법으로 나타낸 두 알고리즘 O(n^2)와 O(n^3) 간의 속도 차이를 다 아우르지 못한다. 예를 들면 초견상 O(n^2)가 빠를 듯해도, n^2가 1000번을 돌면, 2번 돈 n^3가 더 빠르게 된다.
자료구조의 분류
- 기본 자료형 – 기계어 인스트럭션으로 직접 연산 가능한 자료형. 정수형, 소수형, 문자형, 문자열형, 포인터 등이 있다.
- 비기본 자료형 – 같은 자료형으로 구성된 자료구조로 자료를 조직하는 구조를 강조. 배열, 연결리스트, 트리, 그래프 등
int var;
이 구문의 의미는 메모리 상의 랜덤한 위치에 정수형 자료형인 int로 var라는 이름표를 가진 위치를 정해 데이터 저장 공간을 할당하라는 의미다. 이는 기본자료형으로 할당하는 예다
C에서는 struct를 써서 동적인 연결리스트를 구현할 수 있고, 이를 참조하면서 동적으로 비기본 자료형을 구현한다. 코드 구문예는 이후에 예시하겠다.
배열
배열은 같은 자료형을 갖는 변수를 여러개를 한꺼번에 선언하고, 데이터를 대입해서 메모리에 둔다. 효용은 하나의 변수명으로 인덱스만 다르게 붙임으로써 여러개의 데이터를 다룰 수 있다는데 있다. 예를 들면 한반의 성적 처리 프로그램을 제작할때, 학생 이름 그대로 각각 변수를 선언하지 않고, 배열을 쓰면 분류상 이점도 있을뿐아니라, 루프나 이터레이터를 더욱 더 효율적으로 만들 수 있다.
int score[100];
처럼 선언하고 이 배열에 일괄적으로 기본점수 50을 대입한다면
for (int i = 0; i < sizeof(score); i++) score[i] = 50;
처럼 사용한다.
배열은 인덱스를 몇개로 두는지에 따라 일차배열, 이중배열, 삼중배열, … 등등으로 선언할 수 있다. 활용도는 행렬 표현이나 LCD에 표시할 폰트 설정 등이 가능하다.
배열의 문제점은 선언시 한꺼번에 크기를 정하기 때문에 (예: 인덱스를 미리 지정) 인덱스 크기에 비해 적은 량의 데이터가 대입되면 메모리 낭비가 있을 수 있다.
그래서 대안이 된 것이 연결리스트다.
연결리스트
연결리스트는 동적으로 메모리 할당이 가능한 자료구조로 배열에 비해 변수 할당이 필요할때만 그즉시 노드를 추가하는 형태가 되어 메모리를 낭비하지 않을 수 있다. 이 경우에도 필요없어진 노드를 해제할때 메모리도 명시적으로 비워주어야 하는 언어가 존재하지만, 핵심은 할당 당시에 메모리 낭비가 없다는 것에 있다.
연결리스트는 헤드가 존재하고 노드가 추가될수록 각각의 노드가 앞뒤 노드를 이어주는 구조가 된다. C에서는 struct 구조체 안에 데이터를 저장할 변수를 포함시키고 포인터로 전후 노드를 참조할 구문을 두면, 프로그래머는 이 구조체를 참조해서 데이터 저장과 접근을 할 수 있게 된다. 자료구조로는 제일 활용도가 높고 동적 할당이라는 점에 의해 널리 쓰인다.
문자열의 이해
문자열은 특정 글자와 숫자로 이루어진 데이터를 의미한다. 프로그래밍 언어에서는 메모리 상의 랜덤한 영역에 일련의 공간을 할당하고, 특정 바이트에 해당하는 공간부터 일렬로 글자들을 배열하여 표현하는 방식을 취한다. 아래 그림을 보면 메모리 상에 배열된 문자열을 보여주는 추상화된 형태를 알 수 있다.
때로는 문자열의 끝을 표시하는 기호도 포함될 수 있고, 문자열의 시작을 표시하는 기호가 포함될 수도 있다.
서브스트링
서브스트링은 문자열이 주어지면 그 문자열에 포함된 일정 위치부터 다른 일정 위치까지 나열된 문자의 패턴을 의미한다. 예를 들면 superman에서 er이나 rma, man 등은 서브스트링이다. 서브스트링은 의미가 주어지는 패턴이기도 하고 아니기도 하다. 프로그래머는 프로그래밍 언어에서 제공하는 문자열 처리 함수를 조립하여 서브스트링을 추출하고, 자르고, 붙이고, 위치를 바꾸는 등의 처리를 한다. 이역시도 자료구조와 함꼐 이루어지기도 할 것이다.
— 머리가 맹맹해져서 설명 구상이 막히기에 참고한 책의 해설 흐름을 빌려와서 제 표현으로 해설해보았습니다. 참고가 되실 것입니다.