면접을 위한 CS 전공 지식 - 5.1 자료구조 설명

면접을 위한 CS 전공 지식

5. 자료구조

데이터를 표현하거나 저장하는 방법
효과적으로 설계된 자료구조는 프로그램 실행시간을 단축하고 메모리용량을 최소한으로 사용하여 연산을 수행하도록 해준다.
따라서 프로그램을 설계할 때 가장 우선적으로 어떠한 종류의 자료구조를 선택할지 고려해야 한다.
연산 방법과 목적 등에 따라 다양한 자료구조가 있으며, 일반적으로 아래와 같이 분류한다.

5.1 복잡도

자료구조에 대한 글

https://bnzn2426.tistory.com/115
chat GPT
https://noahlogs.tistory.com/27

ch5/1.cpp

#include <bits/stdc++.h> // --- (1)
using namespace std; // --- (2)
string a; // --- (3)
int main()
{
cin >> a; // --- (4)
cout << a << "\n"; // --- (5)
return 0; // --- (6)
}

C++ 언어로 작성되어 있다.

(C++는 C언어 다음에 나온범용 객체 지향 프로그래밍 언어)

(1) 헤더 파일(#include)은 코드 내에서 외부 라이브러리나 기능을 사용하기 위해 필요한 파일을 불러오는 역할.

주어진 코드의 첫 줄(#include <bits/stdc++.h>) 헤더 파일을 포함하고 있다.
이 헤더 파일은 C++ 표준 라이브러리의 일부분으로, 다양한 표준 라이브러리 헤더 파일들을 한번에 포함시켜주는 역할을 한다.
예를 들어, iostream, vector, algorithm, string 등의 표준 라이브러리 헤더들을 모두 포함하고 있어 프로그래밍을 간편하게 할 수 있도록 도와줍니다.

• iostream : 입출력 스트림을 다루는데 사용.
  cin, cout, cerr, clog 등과 같은 표준 입력 및 출력 객체들을 정의하며, 데이터를 표준 입력장치(키보드)로부터 읽거나, 표준 출력장치(콘솔)로 데이터를 출력하는데 사용.
• vector: 동적 배열을 구현하는데 사용. std::vector클래스는 배열과 유사하지만 크기가 동적으로 조정되며, 삽입, 삭제, 검색 등의 다양한 기능을 제공한다.
• algorithm: 다양한 알고리즘을 제공하는 헤더 파일입니다. 정렬(sort() 함수 등), 검색(find() 함수 등), 수치 연산(max(), min() 함수 등) 유용한 알고리즘을 포함하고 있습니다.
• string:문자열을 다루는데 사용. std::string 클래스는 문자열을 저장하고 조작하는데 유용한 다양한 함수들을 제공. 문자열의 연결, 비교, 검색 등을 쉽게 수행할 수 있도록 도와줌.

이러한 표준 라이브러리들을 C++ 프로그래밍에 다양한 기능을 제공하여 프로그래밍을 보다 효율적이고 편리하게 만들어준다. 프로그래머들은 이러한 라이브러리들을 사용하여 작업을 수행하고 코드를 작성할 수 있다.

(2) using namespace std 라는 네임스페이스를 사용한다는 뜻

네임스페이스 :
이는 변수, 함수 및 다른 식별자들의 범위(scope)를 정의하고 구분하는데 사용.
식별자의 충돌을 방지하고 코드를 구조화하는데 도움을 주는 논리적인 “공간” 이라고 생각.
이름 충돌을 방지하고 관련된 요소들을 그룹화하여 코드의 가독성과 유지보수성을 향상시킨다.
C++에서 namespace 키워드를 사용하여 네임스페이스를 정의한다.
예를 들어, 표준 라이브러리의 함수들은 std라는 네임스페이스 안에 정의되어 있다.
이러한 함수들을 사용할 때 std:: 접두사를 사용하여 해당 네임스페이스 안에 있는 것임을 명시한다.

(3)int main(){

// 프로그램 실행코드
return 0;

}

C++프로그램의 실행이 시작되는 부분을 정의하는 함수
모든 C++ 프로그램은 main() 함수에서 시작하며, 프로그램의 실행이 여기서 시작

여기서 int 는 함수가 정수형 값을 반환한다는 의미
보통은 0을 반환하여 프로그램이 정상적으로 종료되었음을 나타냄
이는 운영체제에게 프로그램이 에러 없이 종료되었다는 신호를 보내는 역할.

(4)
cin >> a; : 이 코드는 사용자로부터 입력을 받아서 변수 a에 저장하는 역할
cin은 표준 입력 스트림 객체이며 사용자가 키보드로 무엇인가를 입력하면
그 값이 a에 할당된다.
cout << a << “\n”; : 이 코드는 변수 a에 저장된 값을 화면에 출력하는 역할을 한다. cout은 표준 출력 스트림 객체이며, <<연산자를 사용하여 변수a에 저장된 값을 출력한다. \n`은 줄바꿈을 의미.

따라서 이 두줄의 코드는 사용자로부터 입력을 받고, 그 값을 다시 화면에 출력하는 간단한 작업을 수행한다.
사용자가 입력한 값은 a에 저장되어 cout을 사용하여 화면에 출력

빅오표기법

알고리즘의 효율성을 표기해주는 표기법.
알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미.
빅오 표기법은 보통 알고리즘의 시간복잡도와 공간 복잡도를 나타내는데 사용된다.
(시간 복잡도는 알고리즘의 시간 효율성을 의미, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)
그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서
빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.

빅오O(n²) 빅오제곱
“n” 입력 값의 크기

빅오표기법 특징

1. 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

예를들어
와 같이 상수항은 무시하고 표기한다.

2. 영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

그래프에 나와있는 시간 복잡도의 성능을 비교하면 다음과 같다.
(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

faster - - - - - - - - - - - - - - - - - - - - - - - - slower
		( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )

![업로드중..](blob:https://velog.io/11be56ba-1558-4768-bbae-33595831a005)


#### 빅오 표기법 예제

1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O() : 피보나치 수열