22.08.10_TIL

📌 이제 커리큘럼 중 학습을 하는 시간에서 남은 것은 알고리즘 밖에 남지 않았다. 다양한 내용을 학습하고 배우면서 나의 실력에 대해서 깨달았던 시간이었고 많은 것을 배움으로 나의 역량을 성장시킬 수 있는 계기가 되었다. 남은 알고리즘 학습까지 끝마치고 프로젝트에 들어갈 때 팀원들과 원활한 협업을 통해 좋은 결과를 낳을 수 있도록 해보자!!

📗 오늘 학습한 내용

알고리즘

• 문제를 해결하는 최선의 선택
• 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법을 의미한다.

알고리즘의 명시 조건

• 입력: 출력에 필요한 자료를 입력받을 수 있어야한다. 꼭 입력을 받지 않아도 되는 알고리즘도 있다.
• 출력: 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야한다.
• 유한성: 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 한다.
• 명확성: 각 단계는 단순하고 명확해야 하며, 모호해서는 안된다.
• 효율성: 가능한 한 효율적이어야 한다. 모든 과정이 명백하게 실행 가능해야 하며, 실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘이라 볼 수 있다.

시간 복잡도 

입력값의 변화에 따라 연산을 수행할 때 , 연산 회수에 비해 걸리는 시간

• 시간 복잡도 표기 방법
  • Big-O(빅-오)
    • 가장 자주 사용되는 표기법
    • 최악의 경우를 고려하여 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.
  • Big-Ω(빅-오메가)
  • Big-θ(빅-세타)

빅오 표기법 시간복잡도 (feat.codestates)

Big-O 표기법의 종류

• O(1): Constant complexity
  • 입력값이 증가하더라도 시간이 늘어나지 않는다.
  • 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다.
• O(n): linear complexity
  • 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다. (1중 for문)
• O(log n): logarithmic complexity
  • O(1) 다음으로 빠른 시간 복잡도이다.
  • Binary Search Tree와 같은 이동할 때마다 경우의 수가 절반으로 줄어드는 구조의 알고리즘이다.
• O(n2): quadratic complexity
  • 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다. (2중 for문이상)
• O(2^n): exponential complexity
  • Big-O 표기법 중 가장 느린 시간 복잡도 이다.
  • 매번 접근을 할 때마다 시간이 2배로 늘어나는 알고리즘이다. (대표: 피보나치 수열)

공간 복잡도

• 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미한다.
• 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미한다.

Greedy Algorithm (탐욕 알고리즘)

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 찾아 최종적인 해답에 도달하는 방법이다.
• 특징
  • 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
• 대표문제: 거스름돈 문제

Greedy Algorithm 문제 해결 단계

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

Algorithm 구현의 기초

• 알고리즘을 푼다? 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것이다.
• 알고리즘을 해결하기 위해서는 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두어 연습해야한다.

완전 탐색

• 모든 문제는 완전 탐색으로 풀 수 있다.
• 굉장히 단순하고 무식하지만 답이 무조건 있는 강력한 장점을 가지고 있다.
• 첫 번째 규칙은 만족시킬 수 있지만 두 번째 규칙은 만족할 수 없는 경우가 있다.

완전 탐색을 하는 방법

• Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등

Brute Force (무차별 대입 방법)

• 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법이다.(완전탐색)
• 공간, 시간 복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 정답을 찾으려는 방법이다.

Brute Force가 사용되는 경우

• 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

Brute Force의 한계

• 문제가 복잡해질수록 기하급수적으로 많은 자원(시간, 컴퓨팅)을 필요로 하는 알고리즘이 될 수 있다.

Brute Force를 사용하는 문제

• 순차 검색 알고리즘 (Sequential Search)
  • 배열안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색한다.
• 문자열 매칭 알고리즘 (Brute Force String Matching)
  • 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색한다.
• 선택 정렬 알고리즘 (Selection Sort)
  • 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 떄까지 현재 요소보다 더 작거나 큰 요소(오름차순, 내림차순)를 교환하는 정렬 알고리즘이다.
• 버블 정렬 알고리즘 (Bubble Sort)
• BFS, DFS
• DP

Dynamic Programming (DP, 동적 계획법)

• 하나의 문제는 단 한 번만 풀도록하는 알고리즘이다.
• 탐욕 알고리즘과 함께 언급되는 알고리즘이며, 탐욕 알고리즘과 같이 작은 문제에서 출발한다.
• 모든 경우의 수를 조합해 최적의 해법을 찾는 알고리즘이다.
• 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다.
• 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.

Dynamic Programming을 사용할 수 있는 조건

• Overlapping Sub-problems: 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
• Optimal Substructure: 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수있다.

📘 추가로 공부할 내용

[udemy] React 완벽 가이드 강의 보기 (매일 조금씩 이라도 꾸준히 듣기) (완주)

Study원과 함께 진행중인 프로젝트 구현

pre-Project 사이트 찾기

📝 중요한 내용

• 알고리즘이란?
• 시간 복잡도
• Big-O 표기법
• 공간 복잡도
• 그리디 알고리즘
• 브루트포스 알고리즘