2023.05.17 코드스테이츠 26일차. ( 알고리즘, 의사코드, 시간복잡도, Greedy)

알고리즘

- 문제를 해결하는 최선의 선택

1. 문제를 이해하기 ( 문제의 설명과 입출력 예시, 제한사항, 주의사항을 보고 문제를 파악하기 )

2. 문제를 어떻게 해결해 나갈지 전략 세우기

3. 문제를 코드로 옮기기

 

 

의사코드( pseudocode) 작성법

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

- 의사 코드는 최대한 구체적으로 그리고 순차적으로 작성해야 한다 ( 컴퓨터는 우리가 작성한 코드대로만 작동하는 기계이기 떄문 )

장점

1. 시간이 단축된다

2. 디버깅에 용이하다

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

 

 

시간복잡도(Time Complexity)

- 입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

- 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는것 이다

 

Big-O 표기

- Big-O(빅-오) : 최악의 경우를 고려

- Big-Ω(빅-오메가)  : 최선의 경우를 고려

- Big-θ(빅-세타) : 중간(평균)의 경우를 고려

 

Name	constant	logarithmic	linear	quadratic	exponential
Notation	O(1)	O(log n)	O(n)	O(n²)	O(cⁿ)

 

O(1) ( constant complexity)

- 입력값이 증가 하더라도 시간이 늘어나지 않는다

- 입력값의 크기와 관계없이 즉시 출력값을 얻어낸다

 

O(log n) ( logarithmic )

- BST 자료 구조 탐색처럼 노드를 이동 할떄마다 경우의 수가 절반으로 줄어는 것 

- O(1) 다음으로 빠른 시간 복잡도를 가진다

- up & down 게임처럼 경우의 수를 계속 절반으로 줄여 나가며 답을 찾는다

 

O(n)

- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것

- 입력값이 1일떄 1초의 시간이 걸리면 입력값이 100이면 100초의 시간이 걸리는 것

- 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다

 

O(n²)

- 입력값이 증가할에 따라 시간이 n의 제곱수의 비율로 증가하는 것

- 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 되는 것

 

 

O(cⁿ)

- Big-O 표기법중 가장 느린 시간 복잡도

- 대표적으로 피보나치 수열은 O(2^n)의 시간 복잡도를 갖는다

- 입력값을 늘릴 때마다 걸리는 시간이 n곱 늘어나는 형태

 

Advanced

- 일반적으로 코딩테스트에서는 정확한 값을 제한된 시간내에 반환하는 프로그램을 작성해야 한다

-

데이터의 크기 제한	예상되는 시간 복잡도
n <= 1,000,000	O(log n) or O(n)
n <= 10,000	O(n²)
n <= 500	O(n³)

 

 

탐욕 알고리즘 ( Greedy )

- 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법

1. 선택 절차 ( selection Procedure ) : 현재 상태에서의 최적의 해답을 선택

2. 적절성 검사 ( Feasibility Check ) : 선택된 답이 문제의 조건을 만족하는지 검사

3. 해답 검사 ( Solution Check ) : 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다

 

- 탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간 최적이라 생각되는 해답을 찾으며 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식

탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 한다

1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다

2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대하 최적 문제 해결 방법으로 구성된다

 

 

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

- 알고리즘 문제를 푼다는 것은 내가 생각한 문제해결 과정을 컴퓨팅 사고로 변환하여 코드를 구현한다는 것

= 데이터를 정렬 할 수 있는가?

= 데이터를 효율적으로 탐색할 수 있는가?

= 데이터를 조합 할 수 있는가?

 

- 구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있다

- 완전 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식

- 시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그린다

 

 

 

 

 

## 금일은 알고리즘 파트를 학습하였다

의사코드 작성법을 배운것이 금일 학습 내용중 나에겐 가장 크게 다가왔다

어떠한 문제를 받고 그 문제를 해결하는 코드를 작성 하기 전에 직접 의사코드를 하니씩 단계별로 적어 가면서 이 부분에선 조건문을 어떻게 작성해서 그 결과값이 어떻게 나와야 하고 반복문은 어디를 순회 해야하는지를 명확하게 내가 코드 작성전에 알고 코드를 작성하니 훨씬 코드 작성이 쉽고 빠르게 진행 되었다.

특히 페어 프로그래밍에서 의사코드 작성이 더욱더 빛을 발휘하는거 같다.

페어분과 같이 이 부분은 어떻게 작성하는 것이 좋을까 라고 의견을 나누고 서로의 생각을 알려주고 실행하는게 정말 재밌었고 그 코드가 잘 실현되는것을 보니 정말로 기분이 좋은 하루다.