🤖 1. 자료구조와 알고리즘

자료구조와 알고리즘

자료구조(자료를 처리하고 저장) + 알고리즘(처리 절차) = 프로그램

✅ 알고리즘 조건

① 입력 : 0개 이상의 입력이 존재해야함
    🚨 입력이 0개인 경우 : 키보드/마우스로 데이터를 받지 않음 ex) for문을 이용해 1~100 더하는 프로그래밍

② 출력 : 1개 이상의 출력이 존재해야함
    🚨 출력이 0개면 안되는 이유 : 프로그램의 목적 = 결과 얻기 -> 결과가 없으면 헛수고!

③ 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야함

④ 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함
    ✔️ real-time system : 정해진 시간 내에 결과가 나와야 함

⑤ 유효성 : 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 함

✅ 알고리즘 기술 방식

① 한글이나 영어 같은 자연어 : 약간의 모호성 -> 명백하게 정의해야함
② 흐름도(flowchart) : 도형 사용 -> 알고리즘 복잡해질수록 힘듦
③ 의사 코드(pseudo-code) : 자연어보다 체계적이고 프로그래밍 언어보다 덜 엄격함
④ 프로그래밍 언어 : 예약어들이 모두 명백한 의미를 가짐

추상 자료형

자료형(data type) : 데이터의 종류

추상자료형(ADT, abstract data type) : 실제적인 구현으로부터 분리되어 정의된 자료형 = 추상적, 수학적으로 자료형을 정의한 것 = 프로그래밍 언어로 구현한 것
✔️ 객체(objects)와 함수(functions)들이 정의됨

알고리즘의 성능 분석

시간 복잡도 함수 T(n) = n²+n+1 의 값에서 n²은 99.9% 차지, n+1은 0.1% 차지
=> 차수가 가장 큰 항이 전체의 값 주도

✨ 빅오 표기법(=상한) : 시간 복잡도 함수에서 불필요한 정보를 제거해 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n₀에 대하여 f(n)≤cg(n)을 만족하는 2개의 상수 c와 n₀가 존재하면 f(n)=O(g(n))이다.

f(n)=5이면 n₀=1, c=10일 때, n>1에 대하여 5≤10∙1이 되기 때문에 O(1)이다.
f(n)=2n+1이면 n₀=2, c=3일 때, n>2에 대하여 2n+1≤3n이 되기 때문에 O(n)이다.
f(n)=3n²+100이면 n₀=100, c=5일 때, n>100에 대하여 3n²+100≤5n²이 되기 때문에 O(n²)이다.
f(n)=5∙2^n+10n²+100이면 n₀=1000, c=10일 때, n>1000에 대하여 5∙2^n+10n²+100≤10∙2^n이 되기 때문에 O(2^n)이다.

많이 쓰이는 빅오 표기법 : O(1) > O(logn) > O(n) > O(nlogn) > O(n²) > O(n³) > O(2^n) > O(n!)

수행시간 : O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!)

빅오메가(=하한) 표기법

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n₀에 대하여 f(n)≥cg(n)을 만족하는 2개의 상수 c와 n₀가 존재하면 f(n)=Ω(g(n))이다.

빅세타(=상한+하한) 표기법

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n₀에 대하여 c₁g(n)≤f(n)≤c₂g(n)을 만족하는 3개의 상수 c₁, c₂와 n₀가 존재하면 f(n)=𝜣(g(n))이다.

• 최선의 경우 : O(1) -> 의미 없음
• 최악의 경우 : O(n) -> 널리 사용됨, 계산하기 쉬움
• 평균의 경우 : O(n) -> 계산 어려움
  
  

✏️ 빅오표기법 예시

int test1 (int n) {  // O(n)
	sum = 1;
    for (i=1; i<=n; i+=2)
    	sum++;
    return sum;
}

void test2 (int n) {  // O(n²) = O(n) x O(n)
	for (i=0; i<n; ++i)
    	for (j=0; j<n; j++)
        	k++;
}

void test3 (int n) {  // O(n³) = O(n) x O(n²)
	for (i=0; sum=1; i<n; i++)
    	for (j=0; j<n*n; j++)
        	sum++;
}

void test4 (int n) {  // O(nlogn) = O(n) x O(logn)
	int i, j, sum = 0;
    for (i=0; i<n; j++)
    	for (j=n; j>0; j/=2)
        	sum+=i;
}

void test5 (int n) {  // O(n) = O(n) + O(logn) (둘 중 차수 높은 것)
	int i, j, sum=0;
    for (i=0; i<n; i++)
    	sum+=i;
    for (j=n; j>0; j/=2)
    	sum+=j;
}