벌써 일주일이 지나갔다.
빠르다면 빠르고 느리다면 느리게 흘러간 일주일이었다.
이번 주는 알고리즘과 CS 공부를 하며 보냈다.
나의 일주일을 소개하겠다.
알고리즘
알고리즘의 시작은 문제에 대한 로직을 파악하는 능력을 키우자는 목표와 함께 시작했다.
이와 함께 알고리즘에 대해 어렵고 재밌었던 이야기를 두 개 해보겠다.
재귀란?
알고리즘을 풀면서 가장 어려웠던 부분은 "재귀" 였다.
사전적인 정의는 이렇다.
"어떤 문제를 해결할 때 자기 자신을 다시 호출하여 더 작은 하위 문제를 해결해 나가는 방식" 이다.
팩토리얼을 예로 들어보자.
n! 이라고 가정하면, 전체 1부터 n을 모두 곱하기 위해서 곱셈을 여러번 해야한다.
이렇게 "전체 곱" 을 구하기 위해 "곱셈" 을 수행한다.
이렇게 큰 문제와 작은 문제로 나누어 볼 수 있다.
나는 이 재귀가 너무 어려웠다.
재귀인 것 같은 문제를 마주쳤을때,
아래 3가지를 생각해보면 좋을 것 같다.
- 종료 조건 즉 재귀를 끝내는 조건은 무엇인가?
- 무엇을 받아오는가?
- 어떤 역할을 수행하고 무엇을 출력하는가?
나는 이렇게 3가지를 생각해보고 수도 코드로 작성한다.
확실히 내가 해본 사고 흐름을 정리해보면 도움이 되는 것 같다.
여러분도 자신만의 사고 흐름을 찾아보길 바란다.
왜 정렬을 직접 구현해봐야 하는가?
정렬 문제를 풀다가 그냥 "sort() 함수 쓰면 되는 거 아닌가?" 라는 의문이 들었다.
하지만 정렬을 실제로 구현해보면 생각이 달라진다.
정렬의 차이가 뭔지 사실 실제 구현하기 전까진 잘 몰랐다.
하지만 구현해보면 확실히 어떤 상황에서 무엇을 사용해야 하는지 알 수 있을 것이다.
정렬이 너무 많아 다 학습하진 못하고 Quick sort와 Merge sort 의 차이에 대해 간단하게 설명해보겠다.
Quick sort 는 피벗(특정한 값)을 기준으로 원래 배열을 왼쪽 오른쪽으로 정렬하는 것이다.
Merge sort는 가운데 인덱스를 기준으로 오른쪽 왼쪽을 나눠서 올라오면서 정렬하는 방식이다.
두 개의 차이를 간단하게 표로 나타내본다면
| 기준 | QuickSort | MergeSort |
|---|---|---|
| 분할 방식 | 피벗 값 기준 | 인덱스 절반 |
| 평균 | O(n log n) | O(n log n) |
| 최악 | O(n²) | O(n log n) |
| 메모리 | O(log n) — in-place | O(n) — 임시 배열 |
위와 같다.
최악의 경우와 메모리에 따라 사용하는 알고리즘이 달라질 수 있다는 것이다.
사실 실제로 구현해보기 전까진 왜 "최악과 메모리" 의 차이가 있는지 몰랐고,
더하여 실제 내장 라이브러리 sort() 역시 어떻게 이루어지는지 몰랐다.
실제 구현 경험이 나에게 확 와 닿았다.
컴퓨터 시스템으로의 여행
Computer Systems A Programmer’s Perspective, CSAPP
저자 : Randal E. Bryant & David R. O'Hallaron
CS APP 이라는 책의 1장을 읽으며 가장 눈에 들어온 문구가 있었다.
"파워 프로그래머"가 되는 길로 향하게 될 것이다.
"이 책을 읽고 파워 프로그래머가 되고 싶다"라는 생각을 떠오르게 했다.
1장에선 앞으로 떠날 여행에 대해 안내를 해주었다.
전처리 부터 컴파일 단계가 어떻게 이루어지는가?
동시성과 병렬성이 무엇인가?
가상주소공간은 어떻게 구성되어 있는가?
프로세스와 스레드에 대해 서술할 수 있는가?
책을 읽기 전 하나도 제대로 대답할 수 없었다.
책의 내용을 자세히 들어가기 전 기본 지식들을 설명해준다.
위 대답을 전부 하기엔 글이 너무 길어지니 인상 깊었던 한 가지를 설명해보도록 하겠다.
Array가 LinkedList 보다 빠른 이유?
지역성이 무엇인지 아는가?
위 설명을 이해하기 위해선 캐시가 데이터를 가져오는 방식을 먼저 이해해야 한다.
CPU가 메모리에 1바이트를 요청하면 캐시라인(평균 64바이트) 단위로 긁어온다.
이 이유가 바로 지역성이다.
지역성은 두 가지를 전제로 둔다.
- 공간 지역성 : 한 번 접근한 데이터 주변은 쓸 확률이 높다
- 시간 지역성 : 한 번 쓴 데이터를 또 쓸 확률이 높다
위와 같은 이유로 배열이 빠른 것이다.
배열은 메모리를 주소값에 순서대로 저장한다.
하지만 연결리스트는 노드로 연결하기 때문에 메모리가 흩어져 있다.
배열의 연결된 데이터를 한번에 캐시로 가져오는 방식 때문에 배열이 연결리스트 보다 빠른 것이다.
캐시 메모리는 알고 있었는데,
가져오는 방식까지 알고 보니 왜 배열이 연결리스트 보다 빠른지 이해할 수 있었다,
정말 이 책을 읽다 보면 나도 파워 프로그래머가 될 수 있지 않을까? 라는 기대를 품어 보았다.
정리
드디어 회고에 들어간다...ㅎ
이것저것 많이 했지만, 배울게 많다는 것을 느낀 한 주 였다.
혼자 공부하는 것이 아니라 같이 공부하는 환경이라 오히려 자극을 받았다.
환경의 중요성을 깨닫는 것 같다.
열심히 했지만 아쉬운 점은
"체계적으로 학습하지 못했다는 점" 인 것 같다.
프로젝트 관리나 공부한 내용 정리, 학습 순서를 좀 더 체계적으로 정해도 괜찮을 것 같다.
확실히 누구에게 설명하거나 글로 작성하는게 생각을 정리하기 좋다고 생각한다.
다음 주가 시작한다면 계획을 세우는 시간을 가져볼 것 이다.
이상 나의 일주일이었다.
많은 관심 부탁드립니다^^
멋있어요