[Section2] 06. 자료구조와 알고리즘 3 / 20230517

🧑🏻‍💻 TIL(Today I Learned)

---

✔️ 의사코드, 시간 복잡도(Time Complexity), 탐욕 알고리즘(Greedy), 구현(implementation)-시뮬레이션(simulation)

 

1. 의사코드(pseudocode) 작성법

의사코드란? 
: 프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것

➡️ 컴퓨터에게는 빈틈없이 의사코드를 작성하고 코드를 작성해야 문제없이 작동될 수 있음

 

🔎 장점

1. 시간이 단축된다.

2. 디버깅에 용이하다.

3. 프로그래밍 언어를 모르는 사람과 소통할 수 있다.

 

🔎 의사코드 양식 

➡️ 다른 사람도 이해할 수 있는 자연어(영어나 한국어처럼 일상에서 사용되는 언어)만 사용한다.

➡️ 자연어와 프로그램 언어의 조합을 사용한다.

1. 마스크를 꺼낸다.
2. 마스크 날개를 펼치고 날개 끝을 잡아 오므린다.
3. 고정심 부분을 위로 잡고 턱에서 시작하여 코와 입을 완전히 가린다.
4. 만약 귀걸이 마스크라면 왼쪽 귀와 오른쪽 귀에 걸어준다.
   만약 귀걸이 마스크가 아니라면 마스크를 머리 뒤쪽으로 걸어준다.
5. 고정심을 코에 밀착되도록 누른다.
6. 양 손으로 마스크 전체를 누르며 공기 누설이 있는지 체크한다.
7. 만약 공기 누설이 있다면, 5번으로 돌아간다.
8. 공기 누설이 없다면 마스크 착용 완료.

-------------------------------------------------------
public void wearMask() {

// 마스크를 꺼낸다.

// 마스크 날개를 펼치고 날개 끝을 잡아 오므린다.

// 고정심 부분을 위로 잡고 턱에서 시작하여 코와 입을 완전히 가린다.

// if (귀걸이 마스크라면) 왼쪽귀와 오른쪽귀에 걸어준다.

// else 마스크를 머리 뒷쪽으로 걸어준다.

// while(공기누설이 있다면)

  // 고정심을 코에 밀착되도록 누른다.

  // 양 손으로 마스크 전체를 누른다.

  //if(공기누설이 없다면) return;

}

 

2. 시간 복잡도(Time Complexity)

➡️   시간 복잡도를 고려한다는 것은  "입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?"

➡️ 즉 입력값이 커짐에 따라 증간하는 시간의 비율을 최소화한 알고리즘을 구성했다는 것 

 

🔎 Big-O 표기법

➡️ 시간 복잡도를 표기하는 방법 세 가지 

• Big-O(빅-오) → 가장 자주 사용됨(프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

➡️ 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선 중간(평균)의 경우에 대하여 나타내는 방법 

 

✍🏻 Big-O 표기법의 종류

• O(1)
  : constant complexity, 입력값이 증가하더라도 시간이 늘어나지 않음
     즉 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다는 의미 

public int O_1_algorithm(int[] arr, int index) {
  return arr[index];
}

int[] arr = new int[]{1,2,3,4,5};
int index = 1;
int results = O_1_algorithm(arr, index);
System.out.println(results); // 2

// 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있음 
// arr 길이가 100만이라도 즉시 해당 index 접근해 값 반환할 수 있음

 

• O(n)
  : linear complexity, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것 

입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면 
→ O(n)의 시간 복잡도를 가진다고 말할 수 있음

 

public void O_n_algorithm(int n) {
	for(int i = 0; i < n; i++) {
	// do something for 1 second --> O(n)
	}
}

public void another_O_n_algorithm(int n) {
	for(int i = 0; i < n * 2; i++) {
	// do something for 1 second
	}
}

 

• O(log n)
  : logarithmic complexity, O(1) 다음으로 빠른 시간 복잡도 가짐
    BST의 경우 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듦
    → O(log n)의 시간 복잡도를 가진 알고리즘(탐색 기법)

 

• O(n^2)
  :  quadratic complextity, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것

입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면 
→시간 복잡도는 O(n^2)

public void O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			// do something for 1 second
		}
	}
}

public void another_O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
				// do something for 1 second
			}
		for(int k = 0; k < n; k++) {
				// do something for 1 second
			}
		for(int l = 0; l < n; l++) {
				// do something for 1 second
			}
		}
	}
}

// 2n, 5n을 모두 O(n)이라고 표현하는 것처럼, 3n^2, 5n^2도 n^2으로 표현
// n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에

 

• O(2^n)
  :  exponential complexity, Big-O 표기법 중 가장 느린 시간 복잡도를 가짐
     구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋음

public int fibonacci(int n) {
	if(n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci (n - 2);
}

// 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘

 

3. 탐욕 알고리즘(Greedy)

➡️  선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적이 해답에 도달하는 것 

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사(Feasibility Check) :  선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check) :  원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정 반복

➡️ 하지만 이 알고리즘은 두 가지의 조건을 만족하는 "특정한 상황" 이 아니라면 최적의 해를 보장하지 못함

• 탐욕적 선택 속성(Greedy Choice Property) :  앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

 

4. 구현(implementation) - 시뮬레이션(simulation)

➡️ 구현 문제, 구현 유형 
: 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것 

➡️ 시뮬레이션

: 모든 과정과 조건이 제시되어 그 과정을 거친 결과가 무엇인지 확인하는 유형 

 

---

알고리즘 어렵다. 언제쯤 친해질 수 있을까......?