Part1. 자료구조와 알고리즘은 처음이지?

 

[01. 강의 개요]

① 자료구조란?

    ✔︎ 자료(data)를 효율적으로 이용하기 위한 자료의 저장 방식

          - 자료의 형식, 자료 사이의 관계, 자료를 이용하는 방식(연산, 함수)

          - 효율적: 실행 시간 + 메모리 사용량

          - 주어진 문제에 적합한 자료 구조를 선택함으로써 효율적인 알고리즘을 사용할 수 있음

 

② 알고리즘이란?

    ✔︎ 컴퓨터로 문제를 해결하기 위한 일련의 절차나 방법

          - 입력, 출력 / 명확성, 유한성, 유효성

          - 자연어, 순서도(flowchart), 의사코드(pseydo-code), 프로그래밍 언어 코드 등

자연어, 순서도, 의사코드

          -의사코드와 프로그래밍 언어 코드는 같은 것이 아니다!

 

③ 자료구조와 알고리즘

    ✔︎ 수원에서 대구까지 가장 빠른 경로를 찾으려면?   >   그래프 자료 구조 + 최단 거리 알고리즘

 

④ 강의 커리큘럼

강의 커리큘럼

 

---

[02. C++ 프로그램 개발 환경 설정 ] > SKIP!

---

[03. 코딩 컨벤션]

① 코딩 컨벤션이란?

    ✔︎ 가독성 있는 코드를 작성하기 위한 공통의 코드 작성 가이드라인. 코딩 스타일(coding style)

          - 여러 명의 개발자가 소스 코드를 공유하거나 함께 관리할 때 유용

          - 코딩을 잘하는지 판단하는 척도로도 사용

          - VS CODE에서 맥북의 경우에는 'ctrl + K + F'를 누르면 된다..(자동설정 해놓음)

          - 기타 등등의 코딩 컨벤션은..그냥 pdf 보자..귀찮은 것은 아니고..사실 맞음..써글

 

---

[04. 시간 복잡도]

① 알고리즘 성능 분석

    ✔︎ 주어진 문제를 '잘' 해결하는 '좋은' 알고리즘인지를 판단하려면?

          - ' 잘 ' 해결하는지를 판단하려면?

                ㄴ 정확성 테스트

                ㄴ 수학적 귀납법

                ㄴ 다양한 테스트 케이스 사용

          - ' 좋은 ' 알고리즘인지 판단하려면?

                ㄴ 효율성 테스트

                ㄴ 알고리즘의 자원(resource) 사용량을 분석: 실행 시간, 메모리 사용량, 통신 용량 등

                ㄴ 보통 실행 시간에 대한 분석만 다룸

                ㄴ 대용량 입력 데이터에 대한 처리 능력 판단

 

② 시간복잡도(time complexity)란?

    ✔︎ 입력의 크기가 커짐에 따라 연산 시간(연산 횟수)이 얼마나 증가하는지를 근사적으로 표현
          - 연산의 실행 횟수를 입력 데이터의 크기(n)에 관한 함수 형태로 표현

          - 알고리즘을 직접 구현하지 않고도 위의 함수를 통해  알고리즘의 효율성을 가늠 가능

          - 실행 시간 측정 방법의 한계 : 알고리즘을 구현한 프로그램의 실행 시간은 실행환경(하드웨어,운영체제, 언어, 컴파일러 등)에 따라 달라지므로 절대적인 실행 시간 비교는 성능 파악에 한계가 있음

대표적인 시간복잡도 표기법

빅오 표기법의 예

빅오 표기법의 주요 시간 복잡도 증가율 비교

---

③ 시간 복잡도 예제

▶︎ 예제 1

int middle(int data[], int n)
{
	return data[n / 2];    //n값에 상관없이 1회 연산 실행(O(1))
}

 

▶︎ 예제 2

int summation(int data[], int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum = sum + data[i]; // for 반복문 내부 문장이 n번 실행(O(n))

	return sum;
}

 

▶︎ 예제 3

int variance(int data[], int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum = sum + data[i]; // for 반복문 내부 문장이 n번 실행

	double mean = (double)sum / n;
	double var = 0.0;

	for (int i = 0; i < n; i++)
		var += (data[i] - mean) * (data[i] - mean); // for 반복문 내부 문장이 n번 실행

	// for 반복문 내부 문장이 2n번 실행(O(n))
	// 복잡한 형태의 연산이지만 반복을 얼만큼 하는 것이 중요!
    
	return (var / n);
}

 

▶︎ 예제 4

int find(int data[], int n, int target)
{
	for (int i = 0; i < n; i++)
		if (data[i] == target)
			return i;     // 최선의 경우 for 반복문 안의 비교 연산이 1회, 최악의 경우 n번 실행(O(n))

	return -1;
}

 

▶︎ 예제 5

void bubble_sort(int data[], int n)
{
	for (int i = n - 1; i > 0; i--) // 이중 for 반복문 내부 문장이 1/2*n*(n-1)번 실행(O(n²))
		for (int j = 0; j < i; j++) //(n-1)+(n-2)+∙∙∙
			if (data[j] > data[j + 1])
				swap(data[j], data[j + 1]);
}

 

▶︎ 예제 6

int sum(int n)
{
	if (n == 1)
		return 1;

	return n + sum(n - 1);    //재귀함수가 n번 호출되고, 함수 내부에 단일 연산만 있으므로 O(n)
}

 

▶︎ 예제 7

void func(int n)
{
	if (n == 1)
		return;
	func(n - 1);
	func(n - 1); // func(n)이 1번 호출되면, func(n-1)은 2번 호출되고, func(n-2)는 4번, func(n-3)은 8번 등등으로 호출(O(2ᴺ))
}

---

출처: 어서와! 자료구조와 알고리즘은 처음이지? C++