💪 Today I Learned

• 알고리즘 1, 2주차 강의 수강

Algorithm

알고리즘 개선

단순히 기능을 구현했다고 끝내지 말고 더 나은 알고리즘으로 개선할 수 없는지 생각해보기

예를 들어, 특정 숫자보다 작은 소수를 모두 나열하는 경우 소수의 필요충분조건을 통해 알고리즘을 개선할 수 있다.

[소수 나열하기]
1. 소수는 자기 자신과 1 외에는 아무것도 나눌 수 없다.
2. 주어진 자연수 N이 소수이기 위한 필요충분조건은 'N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다'이다.

배열 vs 링크드 리스트

배열(Array)

• 배열은 각 원소에 즉시 접근 가능 -> O(1) 내에 접근할 수 있음
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다. 최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가진다.
• 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조이다.

링크드 리스트(linked list)

• 리스트 크기가 정해지지 않은 데이터의 공간 -> 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있음
• 리스트는 특정 원소에 접근하려면 포인터를 따라 탐색해야 한다. 최악의 경우에는 모든 노드를 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.
• 리스트는 원소를 중간에 삽입/삭제하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 원소 삽입/삭제를 O(1)의 시간복잡도 안에 할 수 있다.

재귀 함수

• 재귀 함수를 사용하기 위해서는 항상 탈출 조건이 있어야 한다.
• 재귀 함수는 자기 자신을 호출함으로써 코드를 간결하고 명확하게 만들 수 있다.
• 재귀 함수로 풀기 위해서는 문제가 축소되는 특징을 보여야만 함 -> 특정 구조가 반복되는 양상을 보이면 재귀 함수로 문제를 축소시키면서 풀어볼까?라고 생각해보기

Python

for-else문

오늘 알고리즘을 공부하다가 Python에는 for-else문이 있다는 것을 알게 되었다.
for문 안에서 break가 발생하지 않았을 때의 동작을 else문에 작성하면 될 것 같다.

        for i in prime_list:
            if num % i == 0 and i * i <= num:
                break
        else:
            prime_list.append(num)

📢 한마디

오늘 <TIL의 중요성과 작성법> 특강을 듣고 간단하더라도 꾸준히 TIL을 작성해야겠다고 생각이 들었다. 새로운 것을 알게 되더라도 기록을 하지 않으니까 쉽게 잊어버리게 된다. 이제부터는 잘 기록해야겠다!