❓ 자료구조란?

사람들이 일상생활에서 물건을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있는데, 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 자료 구조(data structure)라고 한다.
책을 쌓아 올리는 것처럼 자료들을 쌓아 올리는 구조를 컴퓨터에서는 "스택(Stack)"이라고 하고, 사람들이 줄을 서는 것처럼 데이터를 정리하는 구조를 "큐(Queue)"라고 한다.
"스택"에서는 맨 위에서만 자료를 추가하거나 제거가 가능하고, "큐"에서는 먼저 들어온 자료가 먼저 빠져나간다.

➡️ 자료구조의 특징

효율성

• 자료구조를 사용하는 목적은 효율적인 데이터의 사용 및 관리이다. 적절한 자료구조를 선택하여 이용한다면 데이터 처리의 효율이 올라갈 것이다.

추상화

• 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추려 내는 것이다.
  자료구조를 구현할 때 중요한 것은 알고리즘에 중점을 두지 않고 어느 시점에 데이터를 삽입할 것이며, 어느 시점에 데이터를 추출하고 이러한 데이터를 어떻게 사용할 것인지에 초점을 맞출 수 있기 때문에 구현 외적인 부분에 더 시간을 쏟을 수 있다.
  자료구조 내부의 구현보다 어떻게 사용해야 하는지 추상적인 개념에 대해서 이해해야 한다.

재사용성

• 자료구조를 설계할 때 특정 프로그램에서만 동작하게 설계하지 않는다.
  다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있다.

➡️ 자료구조의 종류와 구분

자료구조는 단순 자료구조 (Primitive Data Structure)와 복합 자료구조(Non-Primitive Data Structure)로 나뉜다. 단순 자료구조는 int를 포함해 프로그래밍 언어에서 통상적으로 제공하는 기본 데이터 형식을 말한다. 그리고 복합 자료구조는 그 안에서 다시 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나뉜다.
선형 자료구조는 데이터 요소를 순차적으로 연결하는 자료구조로, 구현하기 쉽고 사용하기도 쉽다. 배열(Array)과 링크드 리스트(Linked List), 스택(Stack), 큐(Queue)등이 여기에 해당한다.
비선형 자료구조는 선형 자료구조와 달리 데이터 요소를 비순차적으로 연결한다. 한 데이터 요소에서 여러 데이터 요소로 연결되기도 하고, 여러 데이터 요소가 하나의 데이터 요소로 연결되기도 한다. 트리와 그래프가 여기에 해당한다. 비선형 자료구조는 선형 자료구조와 달리 데이터 요소를 비순차적으로 연결한다.

➡️ 자료형(data type)

자료형은 용어 그대로 "데이터의 종류"로서 우리 말로는 "자료형"이라 할 수 있다.

• 자료형은 데이터의 집합 + 연산의 집합으로 볼 수 있다.
  ex) int 자료형 데이터: {-INT_MIN,..., -2, -1, 0, 1, 2, ..., INT_MAX}
  int 자료형 연산: +, -, *, /, %, ==, >, <
• 데이터의 종류가 결정되면 그 데이터와 관련된 연산도 달라지기 때문에, 자료형을 작성할 때는 실행 가능한 연산에 대해서도 신경 써야 한다.
  ex) 나머지를 계산하는 연산자는 정수 데이터에서는 의미가 있지만, 실수 데이터에서는 의미가 없어진다.
• 복잡한 자료형을 구현할 경우에는 연산이 연산자만으로 끝나지 않기 때문에 함수로 작성된다.
  ex) stack에서 새로운 값을 추가하는 연산음 add()함수를 사용한다.

자료형의 3가지 형태

기초 자료형	파생 자료형	사용자 정의 자료형
char(문자형)	Array(배열)	struct(구조체)
int(정수형)	pointer(포인터)	공용체
float(실수형, 소수점 이하 6자리)	-	열거형
double(실수형, 소수점 이하 15자리), long	-	-

• 기초 자료형: 일반적으로 우리가 프로그래밍을 사용할 때 사용되는 자료의 타입.
• 파생 자료형: 기초 자료형을 이용해서 그룹을 이루게 하거나 주소를 가리키는 등의 확장이 된 자료의 타입.
• 사용자 정의 자료형: 기초 자료형 + 파생 자료형 = 사용자 정의 자료형이라 볼 수 있다. 사용자가 자신의 입맛에 맞추어 정의 시킨 자료형이다.

➡️ 추상 자료형 (ADT: abstract data type)

추상 자료형이란 일반적으로 컴퓨터 공학에서 주로 사용되는 용어로, 기능들의 세부적인 구현에 대해서는 이야기 하지 않고 핵심 개념이나 기능을 간추려 낸 자료형으로, 구현 내용은 명시하지 않고 인터페이스만 제공하는 것이다.

추상화(abstraction)

• 소프트웨어 시스템의 복잡성을 관리하기 위한 방법 중 하나로,
  복잡한 시스템 또는 데이터를 간소화하고 중요한 부분에 집중하기 위해 불필요한 세부 사항을 숨기는 프로세스이다. 추상화는 복잡성을 다루고 이해하기 쉽게 만들며, 사용자가 핵심 개념에 집중할 수 있도록 도와준다.

예를 들면, 스마트폰에는 사진촬영, 통화, 게임, 문자 등의 기능들이 있고 이 기능들 외에도 사용자에 따라 많은 기능들을 수행한다. 여기서 중요한 점은 우리는 스마트폰의 이런 기능들에 대해서는 알고 있지만 이 기능들의 구현과정에 대해서는 알지 못한다. 알지 못해도 스마트폰을 이용하는 데는 문제가 없기 때문이다.
이처럼 추상 자료형은 기능의 구체적인 구현은 언급하지 않고, 순수하게 어떤 기능들이 있는지 나열한 것이라고 이해할 수 있다.

어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다.

좋은 추상화란 사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거되는 것이다.
이를 위하여 정보은닉기법(information hiding)이 개발되었고 추상 자료형(ADT)의 개념으로 발전되었다.

정의

• 자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것이라 할 수 있다.
• ADT는 실제적인 구현으로부터 분리되어 정의된 자료형을 말한다. (자료형을 추상적(수학적)으로 정의함을 의미한다.)
• ADT 안에는 객체(objects)와 함수(functions)들이 정의된다.

특징

• 추상화를 통해 정의된다.
• 구현될 때 구현세부사항을 외부에 알리지 않고 외부와의 인터페이스(자료의 특징, 연산)만을 공개하여 이용된다.(세부 내용을 외부로부터 보호할 수 있고, 구현 방법을 언제든 안전하게 변경할 수 있다.(정보은닉의 기본))
  -> 추상화를 통해 캡슐화 기능 가능하고, 캡슐화가 가능하므로 정보 은닉이 가능하다.
• 무엇(What)인지는 정의하지만 어떻게(How) 구현하는지에 대한 정의는 하지 않는다.
  (연산이름, 매개 변수, 반환형은 정의되지만 구체적인 코드는 주어지지 않는다.)
• 프로그래밍 언어에서 말하는 인터페이스는 추상 자료형의 한 종류이다.(구현과의 분리)
• 구현 방법이 변경되어도 인터페이스가 변경되지 않으면 사용자들은 여전히 ADT를 같은 방식으로 사용할 수 있다.
• 세부 구현 과정을 몰라도 이용할 수 있다.
• 사용자는 ADT가 제공하는 연산(인터페이스)만을 사용할 수 있다.
• 사용자는 ADT가 제공하는 연산들을 사용하는 방법을 알아야 한다.

프로그래밍 언어에 따라 ADT는 여러 가지 방법으로 구현 되는데, 객체지향 언어에서는 "클래스"개념을 사용하여 ADT가 구현된다. 객체지향 언어에서는 private,protected,public과 같은 접근 지정자를 통해 캡슐화가 가능하여 내부 자료의 접근을 제한할 수 있다.

❓ 알고리즘이란?

문제를 해결하기 위한 단계적인 절차를 "알고리즘(Algorithm)"이라고 한다. 컴퓨터적인 부분에서 얘기하자면, 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다. 그렇기 때문에 알고리즘은 특정한 일을 수행하는 명령어들의 집합이라고 할 수 있다.

그렇다고 모든 명령어들의 집합이 알고리즘이 되는 것은 아니고 알고리즘이 되기 위한 조건들을 만족해야 알고리즘으로 정의가 된다.

✔️ 알고리즘의 조건

• 입력: 외부에서 제공되는 자료 (입력되어야 하는 값)이 0개 이상 존재해야 한다.
• 출력: 1개 이상의 출력이 존재하여야 하고, 적어도 2개 이상의 서로 다른 결과를 내어야 한다.
• 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
• 유한성(종결성): 한정된 수의 명령어를 수행한 후(유한 시간 내)에 종료한다.
• 효율성(유효성): 모든 과정은 명백하게 실행 가능(검증 가능)한 것(연산)이어야 한다.

✔️ 좋은 알고리즘 분석 기준

요즘의 컴퓨터가 예전의 컴퓨터에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있고 또한 계속해서 발전을 거듭하고 있지만 요즘에도 여전히 프로그램의 효율성은 중요하다.
그 이유는 최근의 상용 프로그램의 규모가 이전에 비해서 엄청나게 커지고 있기 때문이다. 이 말의 뜻은 그만큼 처리해야할 자료의 양이 많아졌기 때문에 알고리즘의 효율성이 더더욱 중요해졌다는 뜻이다.
알고리즘 간의 효율성은 입력 자료의 양이 많지 않으면 눈에 띄지 않지만 자료의 양이 많아지면 차이가 상당해진다.
그렇기 때문에 효율적인 알고리즘이란 알고리즘이 시작하고 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘이다.
이렇게 효율적으로 알고리즘을 사용하고 있는지에 따라 프로그램의 품질이 결정되는데, 좋은 알고리즘의 기준이 뭘까?

• 정확성: 적당한 입력에 대해서 유한 시간 내에 올바른 답을 산출하는지를 판단한다.
• 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정한다.
  해결 하고자 하는 문제의 중요 연산이 여러 개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산한다.
• 기억 장소 사용량: 기억 장소 사용량은 메모리 사용량의 뜻으로, 수행에 필요한 저장공간을 가능한 최소화했는지를 판단한다.
• 최적성: 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘이 없어야 한다.
• 복잡도: 알고리즘은 가능한 알기 쉬워야 한다.
  복잡하고 난해한 알고리즘을 작성하면 나중에는 본인조차 이해하기가 어렵게 되고, 여러 사람들과 협업 시 다른 사람이 곧바로 이해할 수 없게되어 문제가 생길 수 있다.
  또한 이러한 알고리즘은 올바른 결과가 나타나는지도 검증하기 어렵기 때문에 틀린 부분을 찾기도 어렵게 되어 작업 능률이 저하된다.
• 재사용성: 과거에 작성한 것을 그대로 사용하거나 부분적으로 이용할 수 있다면 새로운 프로그램을 만드는 데 필요한 시간을 단축시킬 수 있다.
• 빠른 속도: 속도가 빠르다는 것은 실행을 한 뒤에 그 결과가 나타날 때 까지의 시간이 짧다는 것을 의미한다. 결과의 값이 같다면 짧은 시간안에 올바른 결과를 얻을 수 있는 알고리즘이 더 좋은 알고리즘으로 판단된다.

🤔 알고리즘 복잡도 분석 방법

프로그램의 효율성을 측정하는 방법으로는 알고리즘을 프로그래밍 언어로 작성해서 실제 컴퓨터상에서 실행시킨 다음, 그 수행시간을 측정하는 것이다. 하지만 이 방법은 몇 가지의 문제점이 있다. 알고리즘이 단순한 경우에는 쉽게 구현이 가능하지만, 복잡한 경우에는 구현에 큰 부담이 생긴다. 또한 이 방법을 사용해서 2개의 알고리즘을 비교하려면 반드시 같은 환경 그러니가 똑같은 하드웨어를 사용해 알고리즘들의 수행시간을 측정하여야 한다. 왜냐, 슈퍼컴퓨터의 같은 경우에는 아주 비효율적인 프로그램이라 하더라도 개인 컴퓨터상에서의 가장 효율적인 프로그램보다 더 빠른 시간에 수행될 수 있기 때문이다. 또한, 소프트웨어의 환경에 따라서도 다른데, 예를 들면 프로그래밍 언어에 따라서도 수행 속도가 달라질 수 있다. 일반적으로 C언어의 경우 컴파일 언어이기 때문에 인터프리터 언어를 사용한 경우보다 빠른 수행을 보인다. 이러한 문제점을 해결하기 위해 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법이 개발되었다.

알고리즘의 분석 기법에서는 속도를 다루는 시간 복잡도(time complexity)와 메모리 사용량을 다루는 공간 복잡도(space complexity) 2가지 측면을 고려할 수 있다.

따라서 좋은 알고리즘은 실행 시간이 짧고, 저장 공간도 적게 쓰는 알고리즘이다.

하지만, 2가지 모두를 만족시키기는 어렵다. 시간과 공간은 반비례적인 경향이 있으며, 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선시되기 때문이다. 그렇기 때문에 알고리즘은 시간 복잡도가 중심이 된다.

🔖 시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라, 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시한다. 예를 들면, 연산에는 +,-,* 와 같은 산술연산도 있고 대입 연산, 비교 연산, 이동 연산도 있을 수 있는데 알고리즘의 복잡도를 분석할 때는 이런 연산들의 수행횟수를 사용한다. 그래서 알고리즘이 수행하는 연산의 개수를 계산해서 두개의 알고리즘을 비교할 수 있다.

🔖 시간 복잡도를 표기하는 방법

알고리즘의 효율성은 주어지는 자료집합에 따라 자료집합 중 알고리즘의 수행시간이 가장 오래 걸리는 최악의 경우(worst case), 수행시간이 가장 적은 최선의 경우(best case), 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간을 의미하는 평균적인 경우(average case) 3가지 경우로 나뉜다.

3가지 경우 중에서는 평균적인 수행시간을 산출하는 게 좋을듯 하지만, 광범위한 자료 집합에 대하여 알고리즘을 적용시켜 평균 값을 계산해야 하기 때문에 평균 수행시간은 구하기 힘들 수도 있다. 따라서 "최악의 경우"의 수행시간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다. 이럴 경우 입력 자료 집합을 알고리즘에 최대한 불리하게 만들어 얼만큼의 시간이 소모되는 지를 분석하는 것이다.

➡️ 빅오 표기법(Big-O notation)

빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 많이 기여하지 못하는 항을 생략함으로서 시간 복잡도를 간단하게 표시할 수 있다.
빅오 표기법을 얻는 간단한 방법은 최고차 항만 남기고 다른 항들과 상수를 버리는 것이다. 궁극적으로 최고차 항의 계수도 버리고 최고차 항의 차수만을 사용한다.
이처럼 최고차 항만 남기고 다른 항들과 상수를 버리는 것은 다른 항들과 상수는 시간 복잡도 함수의 증가에 많이 기여하지 못한다는 뜻이다.
입력 값이 작을 때는 영향을 끼칠 수 있겠지만 입력 값이 커질수록 다른 항들이나 상수가 실행 속도에 영향을 미치는 부분은 미비하다.

빅오 표기법은 결국은 입력의 개수에 따른 기본 연산의 수행 횟수를 개략적으로 나타낸 것이므로 이것을 이용하면 알고리즘의 대략적인 수행 시간을 추정해 볼 수 있다.

➡️ 알고리즘 수행시간 비교 그래프

• O(1) 상수형 : 입력 자료의 수에 관계없이 문제 해결시 오직 한 단계만 처리하여 일정한 실행 시간을 갖는 알고리즘 (상수형) ex) 스택에서의 push, pop
  

• O(log n) 로그형 : 입력 데이터의 크기가 커질 수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 입력 자료의 크기가 n일경우 log2n 번만큼의 수행시간을 가진다. ex) 이진탐색(이진 트리), 재귀가 순기능으로 이루어지는 경우도 해당된다.
  

• O(n) 선형 : 입력 데이터의 크기에 비례해서 처리하는 시간이 걸리는 알고리즘. 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다. ex) for문, 최대 값, 최소 값
  

• O(n log n) 선형 로그형 : 데이터가 많아질수록 처리시간이 로그(log) 배 만큼 더 늘어나는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 입력 자료의 크기가 n일경우 n*(log2n) 번만큼의 수행시간을 가진다. ex) 퀵 정렬, 병합 정렬, 힙 정렬
  

• O(n^2) 2차형 : 입력 자료의 크기가 n일경우 n2 번만큼의 수행시간을 가진다. 입력 데이터의 크기에 따라 걸리는 시간은 제곱에 비례한다. 따라서 n값이 커지면 실행 시간이 감당할 수 없을 정도로 늘어난다. ex) 이중 for문, 삽입 정렬, 버블 정렬, 선택 정렬, 루프 구조
  

• O(n^3) 3차형 : 입력 자료의 크기가 n일경우 n3 번만큼의 수행시간을 가진다.
  

• 2차형과 비슷한 모양 2차형보다 더 Time쪽으로 더 곡선이 휘어지는 형태

• O(2^n) 지수형 : 입력 자료의 크기에 따라 걸리는 시간의 2의 n제곱만큼 비례한다. 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다. (지수형) ex) 파보나치 수열, 재귀가 역기능을 할 경우도 해당된다.
  

• O(n!) 팩토리얼형 : 입력 자료의 크기가 N일경우 n(n-1)(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. 가장 느린 알고리즘으로 입력 값이 조금만 커져도 계산이 어려워진다. ex) 외판원 문제(TSP)의 기본적인 해법
  

자료구조와 알고리즘은 밀접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다. 대부분의 프로그램에서 자료(data)를 처리하고 있고 이들 자료는 자료구조(data-structure)를 사용하여 저장된다. 또한 주어진 문제를 처리하는 절차가 필요한데 이는 알고리즘(algorithm)이라고 불린다. 그렇기 때문에 프로그램은 무엇으로 이루어져 있을까? 라고 한다면 흔히 "프로그램 = 자료구조 + 알고리즘"이라고 한다.

출처

• https://velog.io/@alicesykim95/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80
• https://appboong.tistory.com/13
• https://thesauro.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B3%B5%EB%B6%802-%EC%9E%90%EB%A3%8C%ED%98%95-%EC%B6%94%EC%83%81-%EC%9E%90%EB%A3%8C%ED%98%95
• https://velog.io/@charlieppark/%EC%9E%90%EB%A3%8C%ED%98%95%EA%B3%BC-%EC%B6%94%EC%83%81-%EC%9E%90%EB%A3%8C%ED%98%95