[자료구조] 1강 - 자료구조란 무엇인가?

✅ 1. 자료와 정보

(1) 자료의 가공 및 결과

• P (process: 프로세스)
• D (data: 자료, 데이터)
• I (information: 정보)
• 프로세스에 자료를 넣으면 정보를 얻게 된다.
• 컴퓨터의 근본적인 목적은 자료를 처리하여 최종적으로 정보를 제공해주는 것이다.

(2) 자료의 정의

• 현실 세계에서 관찰이나 측정을 통해서 수집된 값이나 사실
• 우리의 생활에서 실제로 만질 수 있거나 볼 수 있는 것(길이, 무게, 부피 등을 측정할 수 있는 대상)에 대해서 물리적인 단위로 표현하여 얻어낼 수 있는 내용
• 쉽게말해, 자료는 더 이상 쪼개지지 않는 원시 데이터이다.

(3) 정보의 정의

• 자료가 가공이 되어서 유의미한 형태로 변환이 되어 제공이 되는 것을 정보라고 한다.
• 쉽게말해, 자료가 2개 이상 서로 상호작용을 통해 얻게 되는 유의미한 데이터이다.
• 즉, 정보를 쪼개서 자료를 얻을 수 있다면 그것은 정보가 되는 것이다.

---

✅ 2. 추상화의 개념

• 추상화는 객체의 공통적인 특징 부분을 가지고 사용자가 보기 편하게 표현한것을 의미한다.
• 쉽게말해, 지하철 노선도 같은 경우에는 실제 지도의 위치와 다르지만 한 눈에 들어오기 때문에 보기 좋음.
• 추상화의 근본적인 목적으로 추상화를 통해 의사소통을 원만하게 하기 위해서라고 보는 경우도 있다.

(1) 자료의 추상화

• 물리적이며 전기적인 동작과는 무관하게 자료를 생각하고 바라보는 사람의 상상
• 쉽게말해, 메모리 트랜지스터에 의해 자료가 저장이 될텐데 이때 트랜지스터는 0과 1 이진코드로 표현이 된다.
• 이때 트랜지스터 상태는 그냥 원시적 데이터 저장소일 뿐, "스택", "트리" 같은 개념은 전혀 없는 상태이다.
• 즉, 물리적으로는 그저 주소가 붙은 비트의 집합이 존재할 뿐이다.
• 다양한 대상을 컴퓨터에서 저장하고 처리하기 위해 그 대상들의 의미와 구조에 대해서 공통의 특징만을 뽑아 정의한 것
• 컴퓨터 내부의 이진수의 표현 방법, 저장 위치 등은 포함되지 않고 단순하게 개발자의 머릿속에 그림을 그리는 것처럼 개념화하여 개발자들 사이의 의사를 쉽게 전달하기 위해 사용되는 방법

(2) 정리

• 자료가 자료의 추상화를 거치게 되면 자료구조가 된다.
• 예시: 학점 - 이름, 학번 등 이러한 구조 또한 자료구조로 볼 수 있다.
• 자료의 추상화는 결국은 자료의 공통적인 특징을 뽑아서 추상화를 한 것
• 이러한 구조를 알고리즘에서 사용을 하는 것이다.
• 또한 자료의 추상화는 개념적 추상화와 구현적 추상화로 볼 수도 있을 것 같음
• 개념적 추상화는 현실 세계의 복잡한 객체를 단순화해서 데이터로 표현하는 것이고 구현적 추상화는 해당 개념적 추상화를 실제 메모리의 단순한 셀구조에 논리적 구조인 자료구조를 덧씌운 것 이라고 할 수 있음.

---

✅ 3. 자료구조와 알고리즘

(1) 자료구조

• 추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것
• 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있음.
• 결론은 따지고보면 객체, 변수도 자료구조로 볼 수 있다.
• 알고리즘은 자료를 처리하고 문제를 해결하는 절차 또는 방법을 의미하며, 데이터 조작과 연산을 의미한다.
• 자료구조는 자료를 효율적으로 저장하고 조직화하는 구조를 의미하며 데이터 보관과 관계가 있다.
• 정리하면 자료구조는 데이터의 형태와 저장 방식, 알고리즘은 데이터의 처리 절차를 의미한다.

(2) 알고리즘

• 컴퓨터에게 일을 시키기 위한 (추상화된) 명령어의 연속된 덩어리 ( 명령의 추상화로 보면 된다. )
• 정리하면, 자료구조와 관련해서 설명하면 자료구조 위에서 데이터를 처리하고 문제를 해결하는 방법으로도 볼 수 있다.
• 자료구조를 사용하는 주체가 알고리즘이라고 보면 된다.

(3) 자료구조와 알고리즘의 추상화/구체화

• 입력값을 머릿속에 추상화된 형태(자료구조)로 구조화하고, 수행되어야 할 명령어를 머릿속에서 추상화된 형태(알고리즘)으로 체계화됨
• 프로그래밍 언어: 자료구조와 알고리즘을 구체화하는 방법

(4) 추상 자료형

• 자료구조와 알고리즘의 중간쯤에 있는 자료의 복잡한 논리적 성격을 정의하는 형식
• 자료값의 집합과 연산 집합에 대한 정의로 구성되며, 자료구조를 표현하는 가장 대표적인 방법이다.
• 쉽게말해, 전산학에서 사용되는 자료구조를 표현하는(공통의 의미를 추출하여 전달하는)방법이다.
• 정리하면 자료의 추상화를 수학적으로 표현하는 것이 추상 자료형이라고 볼 수 있다.
• 이 추상자료형은 프로그래밍 언어의 컴파일러 의해서 프로그래밍 코드로 변형이 됨.
• 이 추상자료형 자체는 자료구조의 개념적 설계라서 CPU가 이해하지 못하므로, 컴파일러가 프로그래밍 언어로 작성된 구현체(Java-ArrayList 등)를 기계가 이해할 수 있는 코드로 바꿔서 실행 가능하게 만들어 준다.

(5) 정리

ArrayList<Integer> list = new ArrayList<>(); // 자료구조
list.add(5) // 알고리즘
list.remove(0) // 알고리즘

• 자바 코드를 예시로 들면, ArrayList 자체는 자료구조이고 내부에서 add, remove 같은 자료구조를 조작하는 것은 알고리즘임.
• 추상 자료형은 개념적 설계이고, 자료구조는 이 추상 자료형이 실제로 구현된 것을 의미함. ( ex: ArrayList... )

---

✅ 4. 알고리즘의 개념과 조건

(1) 알고리즘과 프로그램

• 컴퓨터에게 일을 시키기 위한 (추상화된) 명령어의 연속된 덩어리 ( 명령의 추상화로 보면 된다. )
• 사람(개발자)이 컴퓨터에게 일을 시키기 위한 사람의 의도와 명령을 전달해 줄 수 있는 방법(언어/글)
• 컴퓨터가 수행할 명령어의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것
• 컴퓨터에게 시킬 일(프로그램)을 머릿속에서 추상화시켜서 대략적으로 상상해 놓은 것
• 정리하면, 자료구조와 관련해서 설명하면 자료구조 위에서 데이터를 처리하고 문제를 해결하는 방법으로도 볼 수 있다.
• 자료구조를 사용하는 주체가 알고리즘이라고 보면 된다.

(2) 알고리즘의 조건

• 출력: 알고리즘을 수행하고 나면 적어도 한 가지 결과를 생성해야 함
• 유효성: 반드시 실행 가능해야 해야함
• 입력: 외부/내부 입력값은 유한해야 하며, 반드시 입력 형태가 정의될 수 있어야함
• 명확성: 각 명령들은 명확하고 애매모호하지 않아야 함
• 유한성: 반드시 종료가 명확하게 정의되어 있어야 함

---

✅ 5. 알고리즘의 성능

(1) 알고리즘의 실행시간 분석

• 알고리즘을 실행하는데 필요한 예측 실행시간을 추정하여 알고리즘의 성능을 분석

[ 실행 시간의 예측 ]

• 알고리즘의 실행 횟수를 O(n)이라고 표현 ( big o(n) )
• 같은 O(n)을 가진다고 해서 같은 실행 시간을 갖는 것이 아니라 실행 시간의 유사한 증가 경향에 대한 표현 방법

(2) 알고리즘의 실행메모리 분석

• 알고리즘을 실행하는데 필요한 공간(메모리)을 추정하여 알고리즘의 성능을 분석함 ( 근데 요즘 메모리 가격 하락 잘 안씀 )

[ 실행 메모리의 예측 ]

• 알고리즘의 공간 복잡도(space complexity)는 프로그램을 실행시켜서 완료하는 데 필요한 총 메모리 공간
• 고정 공간: 프로그램의 크기나 입출력의 횟수에 관계없이 컴파일 시에 결정되어 프로그램의 실행이 끝날 때까지 고정적으로 필요한 메모리 공간을 의미한다.
• 가변 공간: 프로그램의 실행 과정에서 동적으로 할당되어야 하는 자료 구조와 변수들을 위해 필요한 메인메미로 공간
• Sp = Sc + Se ( 공간복잡도 = 고정공간 + 가변공간 ) -> 공간복잡도 = 총 메모리 공간

(3) 알고리즘의 성능 측정

• 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간을 측정하여 알고리즘의 성능을 측정

[ 실행 시간의 측정 ]

• 실제로 실행 시간을 시계로 잰다는 것을 의미
• 실제로 실행될 수 있는 프로그램(실행 파일)이 있어야 하는 조건이 있음.
• 시스템 시계를 이용을 함.
• 같은 프로그램이지만 알고리즘이 다른 A와 B 구현 된 프로그램을 실제로 기간을 들여 돌려보면서 측정을 하는 방식
• 문제는 여러 알고리즘으로 만들어 두어야 한다는 매우 비용이 많이 드는 작업임. ( 말이 안되는 작업 )
• 그래서 성능 측정 보다는 분석을 하는 방식을 채택함. 즉, O(n) - 수학적 모델을 사용 ( 대략 어느정도 증가하겠다 이런 느낌 )