[알고리즘]
알고리즘이란?
문제를 해결하는 최선의 선택
문제의 설명, 입출력 예시, 제한사항, 주의사항 잘 파악하기
연습장/화이트보드 -> 수도코드 -> 설명 -> 코드로 옮기기 -> 코드 최적화
쉽게 좌절하지 말자 누구에게나 처음은 존재하니까
[수도코드]
pseudocode 의사코드
장점 : 시간 단축, 디버깅에 용이, 프로그래밍 언어 모르는 사람과 소통 가능
수도코드 작성 후 코드로 풀어나가는 게 가장 효율적
public class PseudoCode {
// 배열의 각 요소들이 그 전의 요소들의 합보다 큰지 여부를 확인하는 함수
public Boolean superIncreasing(int[] arr) {
// 변수 sum을 할당하고 0번쨰 요소를 할당
int sum = arr[0];
// 1번째 요소부터 가장 마지막 요소까지 순회하는 반복문을 만든다
for(int i = 1; i<arr.length; i++) {
// 만약 arr[i]가 sum보다 작거나 같으면
if( arr[i] <= sum) {
// false를 반환
return false;
}
// 그렇지 않으면, 기존 sum에 arr[i] 더한다
else {
sum = sum + arr[i];
}
}
// 반복문이 끝나면 true를 반환
return true;
}
}
[Time Complextiy]
시간 복잡도
연산 횟수에 비해 시간이 얼마나 걸리는 지?
Big - O 표기법 (오. 최악 고려. )
Big - Ω 표기법 (오메가.
Big - θ 표기법 (세타.
Big - O 표기법
빠른 -> 느린 순
O(1) - O(log n) - O(n) - O(n²) - O(Cⁿ) - O(n!)입력값 무관 BST, UpDown 같은 비율 증가 다중배열 종이접기, 피보나치
데이터 값에 따라 시간 복잡도 예측 가능
데이커 값 클수록 시간 복잡도 작음 (빠름)
for (int i = 0; i < n; i++) {
i *= k;
}
// 해당 코드의 시간 복잡도: log n (log 밑은 중요하지 않음. log k n 도 정답)
[Greedy]
탐욕 알고리즘 : 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달
- 적용 순서
-
선택 절차 (현재 상태에서의 최적의 해답 선택)
-
적절성 검사 (선택된 해가 문제의 조건 만족하는지 검사)
-
해답 검사 ( 원래의 문제가 해결되었는지 검사하고, 해걸되지 않았다면 선택 절차로 돌아가 위의 과정 반복)
- 적용 조건
탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향 주지 않아야. 선택의 독립성
최적 부분 구조 : 문제에 대한 최종 해결방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
[Implementation]
구현 - 시뮬레이션
이후 수정 예정
