[인프런 워밍업 클럽 3기 - CS] - 3주차 발자국(자료구조와 알고리즘)

[인프런 워밍업 클럽 3기 - CS] - 3주차 발자국(자료구조와 알고리즘)

강동훈 21일 전

💻 알고리즘

 

📌 삽입 정렬

- 정렬된 영역과 정렬되지 않은 영역을 나누어, 정렬되지 않은 영역의 첫 원소를 정렬된 원소와 비교하여 올바른 위치에 삽입

- 성능이 아쉬움(O(n^2))

📌 병합 정렬

분할 정복(divide and conquer): 해결하기 쉬울 정도로 문제를 쪼갠 후 하나씩 해결

- 재귀를 통해 정렬

- 배열을 더 이상 나눌 수 없을 때까지 쪼개고 병합하면서 정렬

- 시간 복잡도 (O(nlogn))

📌 퀵 정렬

- 분할 정복 알고리즘 중 하나

- 재귀를 사용

- 배열 중 하나를 '피봇(pivot)'으로 설정

- 배열의 시작: left / 끝: right index값 저장

- 값 비교 인덱스: leftStartIndex / rightStartIndex

- leftStartIndex > pivot && rightStartIndex < pivot 일 경우 멈춰서 값 교환

- 인덱스가 만나면 멈추고 피봇을 rightStartIndex랑 변경

- 재귀

- 시간 복잡도 (O(nlogn)) / 최악의 경우 (O(n^2))

- 병합 정렬보다 더 적은 메모리 사용으로 더 좋은 알고리즘이라고 판단

📌 동적 프로그래밍 - 메모이제이션

피보나치 수열- 이전 두 수를 무한하게 더하는 수

재귀 함수를 실행하면서 중복되는 부분이 무수히 발생한다.

- 계산 결과를 저장하고, 중복되는 계산은 저장된 값을 불러온다.

- 속도가 빠른 대신, 메모리 공간 차지가 많아진다.

function fibonacci(n) {
    if (n == 0 || n == 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

function fibonacci2(n, memo) {
    if (n == 0 || n == 1) return n;

    if (memo[n] == null) {
        memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
    }

    return memo[n];
}

console.time("first fibonacci");
console.log(fibonacci(40));
console.timeEnd("first fibonacci");

console.time("second fibonacci");
console.log(fibonacci2(40, {}));
console.timeEnd("second fibonacci");

//102334155
//first fibonacci: 867.412ms
//102334155
//second fibonacci: 0.073ms

 

📌 동적 프로그래밍 - 타뷸레이션

상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장

- 적은 메모리 사용 + 빠른 시간

- 해결하기 힘든 문제를 하향식으로 접근하여 메모리를 이용하여 빠르게 문제 풀이: 메모이제이션

- 직관적이지 못한 재귀, 상향식 접근이 필요: 타뷸레이션

 

📔 회고

🚀 최종 목표 : 로드맵을 마무리하고 알고리즘 문제들을 제대로 이해할 수 있을 정도의 수준이 되기.

🚀 매주 규칙:

  1. 각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분

  2. 강의를 듣고 최대한 이쁘게 (?) 정리해놓기

  3. 매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기

  4. 강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화

     

  5. GPT를 통해 여러 문제를 리스트업하고 최적의 자료구조나 알고리즘을 맞춰보기

     

이번 인프런 워밍업 클럽을 진행하면서 커리큘럼에 맞춰 매일 강의를 듣고 지키려고 하였던 나의 목표 및 규칙이다.

규칙부터 살펴보자면,

  1. 각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분 : 10 / 10

  2. 강의를 듣고 최대한 이쁘게 (?) 정리해놓기 : 8 / 10

  3. 매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기: 6 / 10

  4. 강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화

      : 9 / 10

  5. GPT를 통해 여러 문제를 리스트업하고 최적의 자료구조나 알고리즘을 맞춰보기 : 7 / 10

  • 매 강의를 듣고 섹션별, 유닛별로 모든 내용을 정리하여 저장하였으니 10점을 주었다.

  • 강의를 듣고 최대한 이쁘게 정리를 하려고 노력하였지만 2점이 감점된 이유는 시간이 지날 수록 점점 이모지 사용이 줄고 글간, 행간과 같은 사소한 부분을 신경쓰지 않게 된 것같다,, 그래도 이 노력을 통해서 일관된 템플릿을 형성할 수 있었다는 점, md파일로 매일 정리해보며 파일 정리에 조금 익숙해진 것 같다.

  • 자료구조 강의는 이론적인 부분이 많아, 찾아볼 자료 혹은 더 공부해 볼 부분이 많이 존재하였지만 알고리즘은 이론보다 실전이 더 중요한 부분이라 궁금한 점 보다는 이해가 안가는 부분을 반복해보며 익숙해지려 노력하였다. 결국, 강의를 들으면서 궁금한 점이 많지 않아서 직접 찾아보려고 한 노력들은 적었기에 6점을 주었다. 스스로 피드백을 주자면, 배운 알고리즘이 어느 문제들에서 유용한 지, 혹은 더 개선된 버전의 알고리즘이 있는지 찾아봤으면 더 좋지 않았을까,, 라는 생각이 든다.

  • 강의를 듣고 강의에 관련된 알고리즘 문제를 쉬운 문제라도 최소 하나는 매일 풀어봤던 것 같다. leetcode를 통해서 문제를 찾았고 첫 번째는 효율성을 따지지 않고 스스로 풀어보고, 두 번째는 효율성을 개선할 부분을 찾아 수정하였고 마지막은 더 효율적인 코드가 있는지 다른 코드를 찾아보며 알고리즘 문제에 익숙해지려 하였다. 1점이 감점된 이유는 대부분 하루에 한 문제씩만 풀었다는 아쉬움과 게으름의 후회,,

  • 이 부분이 진행하기 가장 어려웠던 것 같다. 아직 기본적인 수준의 자료구조와 알고리즘만 배운 상태이기 때문에 제대로된 답변을 하지 못하는 경우가 많았고 설명을 들어도 잘 이해가 가지 않는 경우가 많았다. 이게 오히려 투지를 불태우긴 하였지만 아직까지는 아쉬운 부분이 커서 7점을 주었다. 하지만 계속해서 반복하다보면 새로운 개념들에 점차 익숙해질 수 있고 알고리즘 공부와 꾸준히 이어서 하면 큰 시너지를 낼 수 있을 것 같다.

그래서 최종 목표는

로드맵을 마무리하고 알고리즘 문제들을 제대로 이해할 수 있을 정도의 수준이 되기 : 6 / 10

알고리즘 문제를 풀거나, GPT를 통해 여러 문제에 대한 효율적인 자료구조를 대답해봐도 아직 내가 어느정도 성장했다고 느끼지는 못하였다. 자료구조와 알고리즘은 확실히 이론을 공부하는 것보다는 반복적인 연습과 실습이 중요하다라는 것을 다시 한 번 더 깨달은 것 같다. 알고리즘 공부 또한 꾸준히 해나갈 것이고 매일 최소 한 문제씩 풀어가면서 성장을 위해 필요한 최소의 연습양을 채우면서 점차 내가 원하는 수준의 알고리즘 문제 풀이 실력까지 높여가고 싶다.

댓글을 작성해보세요.


채널톡 아이콘