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

💻 알고리즘

📌 재귀

✅ 재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것

✅ 콜스택 : 함수가 호출되면서 올라가는 메모리 영역 (메모리 스택 영역) - FILO(First In Last Out)

함수를 호출하면 콜스택에 올라가고 종료되면 콜스택에서 종료된다.

1. 다른 함수 2개를 호출하는 상황

1. A가 실행되고 콜스택에 올라간다

2. A가 종료되고 콜스택에서 제거된다

3. B가 실행되고 콜스택에 올라간다

4. B가 종료되고 콜스택에서 제거된다

2. 하나의 함수에서 다른 함수를 호출하는 상황

1. A가 실행되고 콜스택에 올라간다.

2. A 실행 중, B를 실행하고 콜스택에 올라간다.

3. B가 종료되고 콜스택에서 제거된다.

4. A가 종료되고 콜스택에서 제거된다.

3. 재귀함수

1. A-1이 실행되고 콜스택에 올라간다.

2. 내부에서 기저 조건을 확인하고 거짓이라면 다음 문장을 실행시킨다.

3. 재귀에 의해 A-2가 실행하고 콜스택에 올라간다.

4. ...

5. 기저 조건에 의해 함수가 종료된다.

6. 가장 상위 함수부터 콜스택에서 제거된다.

7. 만약 기저조건이 없었다면 무한으로 콜스택에 올라가 메모리 부족 현상 발생

📌 재귀적으로 생각하기

1. 반복문을 재귀함수로 대체하는 것은 더 나쁜 효율성을 갖는다. (콜스택 메모리 차지)

2. 하위 문제를 기반으로 현재 문제를 계산한다.

3. 하향식 계산은 재귀함수만 할 수 있다.

📌 버블 정렬

- 앞에 있는 데이터와 옆 데이터를 비교하여 자리를 바꾸고 정렬하는 방식

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

📌 선택 정렬

- 정렬되지 않은 영역의 첫 원소를 마지막 원소까지 비교하여 정렬하는 방식

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

📌 더 찾아본 점

❓ 하노이 탑

✅ 재귀적으로 생각해봐야할 부분

1. 마지막 원판(count) 위의 모든 원판은 temp로 가야한다. (to -> temp)

2. 마지막 원판은 to 로 간다

3. temp에 있는 모든 원판은 to로 가야한다.(from -> temp, temp -> from)

❓ 하노이 탑 (count: 4) 진행과정

{
    4 A C B
    {
        3 A B C
        {
            2 A C B
            {
                1 A B C
                console.log(1 block from A to B)
            }
            console.log(2 block from A to C)
            {
                1  B C A
                console.log(1 block from B to C)
            }
        }
        console.log(3 block from A to B)
        {
            2 C B A
            {
                1 C A B
                console.log(1 block from C to A)
            }
            console.log(2 block from C to B)
            {
                1 A B C
                console.log(1 block from A to B)
            }
        }
    }
    console.log(4 block from A to C)
    {
        3 B C A
        {
            2 B A C
            {
                1 B C A
                console.log(1 block from B to C)
            }
            console.log(2 block from B to A)
            {
                1 C A B
                console.log(1 block from C to A)
            }
        }
        console.log(3 block from B to C)
        {
            2 A C B
            {
                1 A B C
                console.log(1 block from A to B)
            }
            console.log(2 block from A to C)
            {
                1 B C A
                console.log(1 block from B to C)
            }
        }
    }
}

📔 회고

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

🚀 매주 규칙:

각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분
강의를 듣고 최대한 이쁘게 (?) 정리해놓기
매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기
강의에 관련된 알고리즘 최소 1문제씩 풀어 습관화

이번 주차에는 알고리즘에 대한 이론과 정의보다는 실제 코드를 작성해보면서 동작 원리를 익히는 게 주된 주차였다. 그에 맞춰서 알고리즘에 대한 이론보다 동작되는 과정을 익히고 코드로 어떻게 풀어나가는 지 이해하기 위해 직접 코드를 작성해보고 어떻게 진행되는 지 생각해보고 직접 작성해보았다.

재귀함수의 대표적인 문제인 하노이 탑의 경우, 강의를 직접 듣고 원리와 코드를 한 번에 이해하기가 힘들어서 검색해보고 애니메이션도 확인하면서 이해하려 노력하였다. 여러 방식을 익혀봤지만 역시 동작되는 과정을 직접 타이핑해보는 것이 가장 이해가 빨랐던 것 같다.(하노이 탑 진행과정 코드) 이 뿐만 아니라 하노이 탑 시뮬레이터(라고 말하고 게임)도 있길래, 미리 동작 과정을 예상해서 코드로 타이핑을 하고 시뮬레이터에 그 코드 과정을 그대로 따라가면서 학습했던 것 같다.

이번 주 목표 중 하나였던 알고리즘 최소 1문제 습관화 또한 달성하였다. 기존에는 백준이나 프로그래머스를 통해 문제를 풀어봤었는데 이번에는 영어 공부도 할 겸 leet 코드를 통해서 매일 알고리즘 문제를 풀어보았다. 매일 강의를 듣고 그 강의에서 배웠던 알고리즘 방식과 관련된 문제들을 찾아보고 최소 1문제씩 풀었다. 문제를 풀면서 AI 혹은 discussions에 나와있는 해설들을 절대 보지 않으려고 노력하였고 뭐가되든 첫 문제 풀이는 내 스스로 하는 것에 최대한 집중하였다. 그렇게 문제를 풀고 틀리게 되면 한 번 더 고민해보고 주변 도움을 구하였고, 만약 맞췄다면 그 이후 성능을 더 빠르게 문제를 풀 수 있는 방법이 있는지 찾아보기도 하였다.

알고리즘 문제를 풀면서 다음 주에 해보고 싶은 규칙이 하나 생겼다. 현재는 내가 알고 있는 방식으로만 문제를 해결하고 있지만 직접 문제를 해결하지 않더라도 문제에 대해 알맞는 자료구조를 선택할 수 있는 능력을 기르는 것은 어떨까? 그래서 이 또한 GPT를 이용해서 여러 문제들에 대해 나열을 시키고, 그 문제를 해결할 수 있는 최적의 자료구조와 알고리즘을 답변하여 점점 더 개념을 탄탄히 하고 최적의 문제해결능력을 사고하는 능력을 길러보고 싶다.

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