- 시작하게 된 계기 및 다짐 😮
이번 코드스테이츠의 백엔드 엔지니어링 개발자 부트캠프
에 참여하게 되면서 현직개발자 분들의 빠른 성장을 위한 조언 중 자신만의 블로그를 이용하여 배운 것 들을 정리하는게 많은 도움이 된다 하여 시작하게 되었다.
- 학습 목표 😮
목표 | 결과 |
---|---|
다양한 알고리즘 해결 방식에 대한 이해 및 학습 | O |
Greedy를 이용한 탐욕알고리즘 해결 | O |
DP(Dynamic Programming) vs BruteForce | O |
BST(Binary Search tree) Tree를 이용한 문제해결 | O |
그외 Math관련 알고리즘 | O |
- 정리
Algorithm 코딩 전.
1. 문제 이해
- 주의사항,제한사항 등 조건 인지
2. 문제를 해결해 나갈 전략 세우기
- 전체적인 흐름 사고 및 수도코드 작성
3. 문제를 코드로 옮기기
extra) - 구현한 코드의 최적화
# 의사코드(pseudocode)
- 일상 언어로 프로그램 작동 논리 작성
- 디버깅과 소통에 용이
# 시간복잡도
- 알고리즘 수행시, 입력값의 변화에 따른 시간의 비율을 최소화한 알고리즘
- Big-O 표기법 주로 사용
(1) Big-O 표기법
- 최악의 경우를 고려하여 만든 알고리즘
- 계수, 상수값을 제외한 입력값을 고려한 계산 알고리즘
- 그외, 빅-오메가,빅세타 존재
# 참조
BST : O(log n) - 경우의 수가 절반으로 줄기 떄문
fibonachi(재귀) : O(2^n) - 최악의 케이스 시간이 가장 오래 걸림
1. 선택절차 - 현재 상태에서 최적의 해답을 선택
2. 적절성 검사 - 선택된 해의 조건 검사
3. 해답 검사 - 원래의 문제가 해결되었는지 확인하고, 해결되지 않았다면 전단계에서 다시반복
- 가장 큰 가치의 아이템을 먼저 선택하는 방법
- 매 순간 최적의 해답을 찾으면 답을 채워나가는 상황
- 어느정도 최적에 근사하여, 근사 알고리즘으로 사용할 수 있음
★최적해 보장 상황
1. 탐욕적 선택 : 앞의 선택이 이후의 선택에 영향을 주지 않음
2. 최적 부분 구조 : 문제에 대한 최종 해결법은 부분 문제에 최적 문제로 구성됨
- 모든 경우의 수를 확인하여 문제 해결
- 최악의 시나리오 더라도, 솔루션을 찾는 방법
- 비 효율적인 알고리즘
(1) 프로세스 속도를 높이는 다른 알고리즘이 없을 때
(2) 문제를 해결하는 여러 솔루션이 있고, 각 솔루션을 확인해야 할 때
ex)
- 순차 탐색 알고리즘 : 차례 대로 확인하는 경우
- 문열 매칭 알고리즘 : 전체 문자열에서 특정 문자열을 포함하고 있는지 검색하는 경우
- 선택 정렬 알고리즘 : 전체 배열 에서 가장 큰/작은 요소를 하나씩 검색하여 정렬하는 경우
- 버블 정렬
- DFS,BFS
- DP (동적 프로그래밍)
advance)
Brute Force vs Dynamic Programing
Closet-Pair Problems by Brute Force
Convex-Hull Problems by Brute Force
- 정렬된 데이터를 절반씩 범위를 나눠 분할 정복 기법으로 특정 값을 찾아내는 알고리즘
- 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용
- 데이터의 양이 많을수록 효율이 높아서 데이터 양이 많을 떄 사용
- O(log n)으로, 빠른 편이지만 항상 효율이 좋진 않음 , 찾고자 하는 데이터가 끝에 있을 때
- 배열에만 구현 가능, 정렬 필요
1. 정렬된 배열의 중간 인덱스 지정
2. 해당 인덱스 보다 작으면 왼쪽 크면 오른쪽을 해당 인덱스를 기준으로 분할
3. 위의 부분을 반복
# 탐색 알고리즘
(1) 선형 탐색 알고리즘
(2) 이진 탐색 알고리즘
(3) 해시 탐색 알고리즘
advance)
Linear Search Algorithm
Hash Search Algorithm
Divide-and-conquer algorithm
Binary Tree vs Binary Search Tree
Binary Search Algorithm vs Binary Search Tree
- 컴퓨팅 사고
- 알고리즘 해결 수학 주요 3가지 개념
1. GCD/LCM(최대공약수, 최소공배수)
★ 최대 공약수(유클리드 호제법: Euclidean algorithm)
public int gcd(int m, int n) {
if (m % n == 0) return n;
return gcd(n, m % n);
}
2. 순열/조합
- 순열 : nPm = n! / (n-m)! --> 순서가 상관 있을 때
ex) (i = 0, j = 0, k = 0)
- 조합 : nCm = n! / (n-m)!*m! --> 순서가 상관 없을 때
ex) (i = 0, j = i + 1, k = j + 1)
3. 멱집합
- 부분집합의 부분집합을 이용한 문제 해결 방식사용
- 피드백 😮
- 앞으로 해야 될 것 😮