2022-[05.31~06.03](Section2_Algorithm_코딩실습)

0. 시작하게 된 계기 및 다짐 😮

• 이번 코드스테이츠의 백엔드 엔지니어링 개발자 부트캠프에 참여하게 되면서 현직개발자 분들의 빠른 성장을 위한 조언 중 자신만의 블로그를 이용하여 배운 것 들을 정리하는게 많은 도움이 된다 하여 시작하게 되었다.

  • 그 날 배웠던 것을 길지 않아도 좋으니 정리하며 복습하는 습관 기르기
  • 주말에 다음주에 배울 내용들을 예습
  • 코딩 문제와 java코드들은 꾸준히 학습
  • 자료구조를 이용한 알고리즘 문제 해결 학습

1. 학습 목표 😮

목표	결과
다양한 알고리즘 해결 방식에 대한 이해 및 학습	O
Greedy를 이용한 탐욕알고리즘 해결	O
DP(Dynamic Programming) vs BruteForce	O
BST(Binary Search tree) Tree를 이용한 문제해결	O
그외 Math관련 알고리즘	O

2. 정리

Coding전 문제해결 시 고려사항(Time Complexity등)

Algorithm 코딩 전.

 1. 문제 이해
 - 주의사항,제한사항 등 조건 인지

2. 문제를 해결해 나갈 전략 세우기
 - 전체적인 흐름 사고 및 수도코드 작성

3. 문제를 코드로 옮기기

extra) - 구현한 코드의 최적화



# 의사코드(pseudocode) 
 - 일상 언어로 프로그램 작동 논리 작성
 - 디버깅과 소통에 용이

# 시간복잡도
 - 알고리즘 수행시, 입력값의 변화에 따른 시간의 비율을 최소화한 알고리즘
 - Big-O 표기법 주로 사용
  (1) Big-O 표기법
     - 최악의 경우를 고려하여 만든 알고리즘
     - 계수, 상수값을 제외한 입력값을 고려한 계산 알고리즘
     - 그외, 빅-오메가,빅세타 존재
 
# 참조
   BST : O(log n) - 경우의 수가 절반으로 줄기 떄문
   fibonachi(재귀) : O(2^n) - 최악의 케이스 시간이 가장 오래 걸림

1. Greedy(탐욕 알고리즘)

1. 선택절차 - 현재 상태에서 최적의 해답을 선택
2. 적절성 검사 - 선택된 해의 조건 검사
3. 해답 검사 - 원래의 문제가 해결되었는지 확인하고, 해결되지 않았다면 전단계에서 다시반복

 - 가장 큰 가치의 아이템을 먼저 선택하는 방법
 - 매 순간 최적의 해답을 찾으면 답을 채워나가는 상황
 - 어느정도 최적에 근사하여, 근사 알고리즘으로 사용할 수 있음

★최적해 보장 상황
 1. 탐욕적 선택 : 앞의 선택이 이후의 선택에 영향을 주지 않음
 2. 최적 부분 구조 : 문제에 대한 최종 해결법은 부분 문제에 최적 문제로 구성됨

2. 완전탐색(brute force)

 - 모든 경우의 수를 확인하여 문제 해결
 - 최악의 시나리오 더라도, 솔루션을 찾는 방법
 - 비 효율적인 알고리즘

 (1) 프로세스 속도를 높이는 다른 알고리즘이 없을 때
 (2) 문제를 해결하는 여러 솔루션이 있고, 각 솔루션을 확인해야 할 때


ex)
    - 순차 탐색 알고리즘 : 차례 대로 확인하는 경우
    - 문열 매칭 알고리즘 : 전체 문자열에서 특정 문자열을 포함하고 있는지 검색하는 경우
    - 선택 정렬 알고리즘 : 전체 배열 에서 가장 큰/작은 요소를 하나씩 검색하여 정렬하는 경우
    - 버블 정렬
    - DFS,BFS 
    - DP (동적 프로그래밍) 

advance)
  Brute Force vs Dynamic Programing
  Closet-Pair Problems by Brute Force
  Convex-Hull Problems by Brute Force

3. 이진 탐색 알고리즘

 - 정렬된 데이터를 절반씩 범위를 나눠 분할 정복 기법으로 특정 값을 찾아내는 알고리즘
 - 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용
 - 데이터의 양이 많을수록 효율이 높아서 데이터 양이 많을 떄 사용
 - 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. Algorithm With Math

 - 컴퓨팅 사고
 - 알고리즘 해결 수학 주요 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. 멱집합 
 - 부분집합의 부분집합을 이용한 문제 해결 방식사용
      

3. 피드백 😮

• 다양한 알고리즘 문제를 해결하는데 사용되는 방식들을 학습하였는데, 이전에 배웠던 Tree, Graph, Queue, Stack등 자료구조 형태를 실제로 사용하여 문제를 해결하니 굉장히 어렵긴 하지만 그 과정을 이해해 나가는 부분이 많이 뿌듯하였다.
• 이는 지속적으로 문제를 해결하지 않으면 금방 까먹고 하므로, 타 알고리즘 문제들을 해결해나가면서 꾸준히 연습해야 될 것 같다.

• '정규 표현식'에 대하여 추가적으로 학습하면 문제해결에 많이 유용할 것 같다.

4. 앞으로 해야 될 것 😮

• 매일 꾸준히 할 것
  • 꾸준히 velog 작성
  • Java 언어 및 Algorithm 공부(Coding-Test)
  • 틈틈히 운동 하기

---

• 내일 해야 할 것
  • 네트워크의 작동원리와 HTTP 프로토콜에 대한 이해
  • 이를 이용한 간단한 실습과 브라우저의 동작원리, 클라이언트-서버[DB] 이해