Chapter1. Algorithm
1.일상 생활과 알고리즘의 관계에 대해 이해한다.
2.알고리즘이 무엇인지 학습하고 이해한다.
3.알고리즘이라 명시되기 위한 조건에 대해 학습하고 이해합니다.
4.알고리즘의 중요성에 대해 학습하고 이해합니다.
Chapter2. 시간 복잡도와 공간 복잡도
Chapter2-1. 시간 복잡도
5.시간 복잡도가 무엇인지 학습하고 이해합니다.
6.Big-O 표기법에 대해 학습하고, 각 종류에 대해 이해합니다.
7.데이터 크기에 따른 시간 복잡도에 대해 학습하고 이해합니다.
Chapter2-2. 공간 복잡도
8.공간 복잡도의 개념에 대해 이해합니다.
9.가변 공간과 고정 공간에 대해 이해합니다.
10.공간 복잡도의 중요성에 대해 이해합니다.
Chapter3. Algorithm의 유형
Chapter3-1. Greedy Algorithm
11.greedy algorithm이 무엇인지 학습하고, 문제 해결 단계를 이해합니다.
12.greedy algorithm의 적용 예시와 문제의 단계적 구분에 대해 학습하고 이해합니다.
13.greedy algorithm의 특징에 대해 학습하고 이해합니다.
Chapter3-2. Algorithm 구현
14.알고리즘 구현에 대해 이해합니다.
15.완전 탐색의 개념과 규칙에 대해 이해하고, Brute Force 예시에 대해 이해합니다.
16.시뮬레이션의 개념과 예시에 대해 이해합니다.
Chapter3-3. Dynamic Programming
17.dynamic programming이 무엇인지 학습하고, 어떤 조건을 만족해야 하는지 이해합니다.
18.dynamic programming의 최적의 해결 방법에 대해 학습하고 이해합니다.
Chapter3-4. Algorithm의 유형 예제
19.greedy algorithm을 이용한 예시를 보고, 동작 방식을 분석해봅니다.
20.알고리즘 구현을 위해 필요한 개념을 적용한 예시 코드를 보고 분석합니다.
21.dynamic programming의 대표적인 문제를 소개한 것을 보고, 분석합니다.
1.일상 생활속에 녹아있는 행동패턴들 또한 알고리즘의 일종이라고 하는 것 같다.
2.알고리즘이란 특정한 입력값이 있을 수 있고 반환값은 반드시 존재해야 하는 함수라고 볼 수 있다.
5.시간복잡도란 특정한 계산을 비교할 때 시간이 얼마나 걸리는지에 대한 대략적인 파악을 위한 일반론 같은 개념이다. 무한을 다룰 때와 비슷하게 상수 또는 숫자의 차이가 중요한 것이 아니라 몇차(n, n^2, n^3 등)인지가 중요한 개념이라고 볼 수 있다.
6.시간 복잡도를 표기하는 방법은 Big-O(빅-오), Big-Ω(빅-오메가),Big-θ(빅-세타)의 최악, 최선, 평균값을 나타내는 방식이 있는데 계산은 항상 최악을 가정하는 편이 리스크를 줄일 수 있기 때문에 빅오 표기법을 제일 많이 사용한다.
7.데이터의 크기와는 관계없이 n으로 표기하며 그 데이터를 즉시 조회할 수 있는 경우에는 상수 1이의 시간복잡도를 가질 수 있다. 또한 for문, while문등 반복적인 행동들을 중첩해서 사용하는 경우에는 곱연산으로 늘어나기 때문에 n^2, n^3등 데이터의 크기와 관계없이 어마어마하게 복잡해질 수 있다. (1만 크기의 n 복잡도는 1만의 복잡도라고 가정하면 100크기의 n^3복잡도는 100만의 복잡도를 가지고 있으며 4크기의 n^10등이 되어버리면 100만이 넘어버릴 수 있다.
8.프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미한다. 일반적으로는 시간적 문제만 있을 뿐 공간적인 문제는 거의 없지만 특정한 경우에는 메모리의 제한을 감안해 프로그래밍 해야 할 수 있기 때문에 시간복잡도와 비슷한 표기법으로 계산한다.
9.고정 공간은 같은 자리를 차지하며 수행하기 때문에 관계없지만 가변 공간은 프로그래밍에 사용되는 변수등을 저장하는 것에 사용되기 때문에 효율적으로 설계하지 않으면 지나치게 많은 가변 공간을 사용할 수 있게 된다. 이를 계산하기 위한 방식이 공간 복잡도이다.
10.위에서 언급했듯이 공간복잡도는 시간복잡도보다 훨씬 덜 중요하지만 동적 계획법 등의 메모리를 많이 요구하는 방식이나 하드웨어 환경이 한정된 경우에는 공간복잡도를 고려해야 하는 일이 생기기 때문에 확인하는 방법을 아는 것도 필요하다.
11.greedy algorithm은 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 아래와 같은 해결 단계가 있다.
선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
12.일반적으로는 잔돈 거슬러 주는 문제, 상위가치부터 하위가치까지 쪼개는 문제 등에 사용된다.
13.앞의 선택이 이후의 선택에 영향을 주지 않으며 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 그렇기 때문에 항상 최적은 아니지만 일반적으로 최적의 근사치 값을 빠르게 구할 수 있다는 장점이 있다.
14.본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고한다.. 그냥 코딩하는 것 아닐까?
15.모든 문제는 완전탐색으로 풀'수는'있다. 하지만 완전히 탐색하는 것은 낭비가 많을 수 있기 때문에 효율적인 탐색이 불가능할 때만 사용하는 것이 좋다. Brute Force는 완전 탐색 방법 중 하나로 무차별 대입이라는 의미를 가지고 있다. 이름처럼 모든 경우의 수를 모든 조건에 넣어서 확인하는 방식이다.
16.시뮬레이션은 조건들이 제시되며 그 결과를 묻는 유형으로 모든 조건을 제대로 구현하는 것이 까다로울 수 있다. 예시로 작성된 부분은 코드스테이츠에서 제공된 해설이기 때문에 언급하기는 어렵지만 시뮬레이션의 까다로움에 대해서 이해할 수 있었다. 마치 처음에 백준 터렛문제를 풀다가 자꾸 실패가 나와서 포기했었던 기억이 난다.
17.dynamic programming이란 동적 프로그래밍으로 모든 경우의 수를 조합해 최적의 해법을 찾으며 해결법을 저장하고 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 피보나치 수열을 예로 들자면 전 단계의 값과 전전단계의 값의 합이 이번 단계의 값인데 그 값들을 계속해서 거꾸로 내려가며 하나씩 더하는게 아닌 한번 더한 값은 저장되어 다시 그 값이 필요할 경우엔 계산된 값을 불러오는 방식을 사용한다.
18.일단 "주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 합니다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있습니다."라고 하는데 이런 말 보다는 느낌으로 파악해야 하는 것 같다.
마치 재귀처럼 공통되는 부분과 규칙을 찾은 후 전단계와의 차이점을 기록하는 방식인 것 같다.
19.거스름돈이라는 문제로 큰 단위 먼저 제거한 후 카운팅을 올리고 다음 단위로 넘어가는 방식이다.
20.Brute-Force 문자열 매칭 문제로 전체를 조회하다가 해당하는 글자로 시작하는 경우 다음 글자들을 체크하는 방식이다.
21.피보나치 수열 문제와 타일링 문제인데 피보나치는 위에서 예시를 들었고 타일링도 피보나치와 유사한데 n번째 타일링의 갯수는 n-1과 n-2의 합과 같기 때문에 dp[n] = dp[n-1] + d[n-2]방식으로 해결한다.
요즘 이상하게 회고 내용이 많아지는데 핵심적인 부분만 있으면 좋겠다.
생각해보면 이걸 다 답변할 의무가 있는 것도 아닌데 내가 무식했던게 아닌가 싶기도 하고
몇개 안남았는데 굳이 방식을 바꿔야 하나 싶기도 하다..