[100일의 IT 초보 탈출] #18 단계 UP! 실생활에서 만나는 중급 알고리즘

 

안녕하세요!

저번 시간에는 알고리즘의 기본 개념을 요리 레시피에 비유해서 알아봤는데요

오늘은 조금 더 난이도 있는 알고리즘에 대해 알아볼게요!

어렵게 느껴지더라도 걱정마세요

최대한 쉽게 설명해드릴게요! 😊

💡 기본 정렬을 넘어선 퀵 정렬 (Quick Sort)

퀵 정렬이란?

퀵 정렬은 '분할 정복' 방식을 사용하는 효율적인 정렬 알고리즘이에요.

이름처럼 상당히 빠른 편이라 실제로 많이 사용돼요!

실생활 예시: 책 정리하기

도서관 사서가 책을 정리하는 방법으로 생각해볼까요?

 

1. 기준점(피벗) 정하기: "ㅎ"으로 시작하는 책을 기준으로 삼아요
2. 분류하기:
   • "ㅎ" 앞 글자로 시작하는 책은 왼쪽에
   • "ㅎ" 뒤 글자로 시작하는 책은 오른쪽에
3. 재귀적 분류: 각 그룹 내에서 다시 기준점을 정해 분류해요
4. 완성: 모든 책이 정렬됐어요!

특징

퀵 정렬의 가장 큰 장점은 평균적으로 매우 빠른 속도를 보인다는 점이에요.

대부분의 상황에서 다른 정렬 알고리즘보다 효율적으로 동작하죠.

하지만 이미 정렬된 데이터나 거의 정렬된 데이터에서는 최악의 경우 느려질 수 있다는 단점이 있어요.

일반적인 경우 시간 복잡도는 O(n log n)으로, 대량의 데이터를 다룰 때도 충분히 빠른 성능을 보여줍니다.

🔍 빠른 검색의 핵심, 이진 탐색 (Binary Search)

이진 탐색이란?

정렬된 데이터에서 원하는 값을 찾는 효율적인 방법이에요.

매번 검색 범위를 절반으로 줄여나가는 방식이죠.

실생활 예시: 사전에서 단어 찾기

두꺼운 국어사전에서 '바나나'라는 단어를 찾는다고 생각해볼게요.

 

1. 사전의 중간 부분을 펼쳐요
2. 펼친 페이지에 '마'로 시작하는 단어가 있어요
3. '바'는 '마' 뒤에 있으니 뒷부분에서 찾아야 해요
4. 뒷부분의 중간을 다시 펼쳐요
5. 이런 식으로 계속해서 범위를 좁혀 '바나나'를 찾아요

특징

이진 탐색은 매우 빠른 검색 속도를 자랑하는 것이 가장 큰 장점입니다.

한 번 비교할 때마다 찾아야 할 범위가 절반으로 줄어들기 때문에 대용량 데이터에서도 효율적으로 작동해요.

다만 데이터가 미리 정렬되어 있어야 한다는 제약이 있어요.

정렬되지 않은 데이터에서는 사용할 수 없죠.

시간 복잡도는 O(log n)으로, 데이터가 10배 늘어나도 비교 횟수는 약 3번 정도만 증가하는 매우 효율적인 알고리즘입니다.

 

🚗 최단 경로 찾기, 다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘이란?

그래프에서 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 알고리즘이에요.

 

실생활 예시: 네비게이션 경로 찾기

집에서 회사까지 가는 최단 경로를 찾는 상황을 생각해볼게요.

1. 출발점(집)을 설정해요
2. 집에서 직접 연결된 모든 교차로까지의 거리를 계산해요
3. 가장 가까운 교차로를 선택해 방문 표시를 해요
4. 그 교차로를 통해 다른 교차로로 가는 경로가 더 짧아지는지 확인해요
5. 3-4단계를 반복해 모든 교차로에 대한 최단 거리를 찾아요
6. 최종적으로 회사까지의 최단 경로가 완성돼요!

 

특징

 

다익스트라 알고리즘의 가장 큰 장점은 두 지점 사이의 최단 경로를 정확하게 찾을 수 있다는 점입니다.

실제 길 찾기 앱이나 네트워크 라우팅에 광범위하게 사용되고 있어요.

단점으로는 모든 간선의 가중치가 반드시 양수여야 한다는 제약이 있어요.

음수 가중치가 있으면 정확한 결과를 보장할 수 없죠.

속도는 일반적으로 O(E log V)로, E는 간선(길)의 수, V는 정점(교차로)의 수를 나타냅니다.

 

💰 문제를 쪼개서 푸는 동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍이란?

큰 문제를 작은 부분 문제로 나누고, 각 부분의 결과를 저장해 재활용하는 방법이에요.

실생활 예시: 최소 동전 개수 문제

670원을 동전으로 거슬러 줄 때, 최소한의 동전 개수를 사용하는 방법을 찾아볼게요.

가능한 동전은 500원, 100원, 50원, 10원이라고 해요.

 

1. 각 금액(1원~670원)에 대한 최소 동전 개수를 저장할 표를 만들어요
2. 10원부터 시작해 각 금액마다 계산해요:
   • 10원: 10원 동전 1개 (최소 1개)
   • 20원: 10원 동전 2개 (최소 2개)
   • 50원: 50원 동전 1개 (최소 1개)
   • 60원: 50원 동전 1개 + 10원 동전 1개 (최소 2개)
   • ...
3. 이런 식으로 670원까지 계산하면:
   • 670원 = 500원 1개 + 100원 1개 + 50원 1개 + 10원 2개 (총 5개)

특징

동적 프로그래밍의 가장 큰 장점은 계산 결과를 저장해두고 재활용함으로써 중복 계산을 피할 수 있다는 점입니다.

피보나치 수열이나 최적 경로 찾기 같은 문제에서 엄청난 효율 향상을 가져올 수 있어요.

단점으로는 모든 부분 문제의 결과를 저장해야 하므로 메모리를 많이 사용할 수 있다는 점이 있습니다.

주로 최적화 문제나 경우의 수를 계산하는 문제에 널리 활용됩니다.

 

🌲 계층 구조 탐색, 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)

BFS와 DFS란?

그래프나 트리 구조에서 모든 노드를 방문하는 두 가지 다른 방법이에요.

실생활 예시: 회사 조직도 탐색

회사의 모든 직원에게 공지사항을 전달하는 방법을 생각해볼게요.

 

BFS (너비 우선 탐색)

1. CEO부터 시작해요
2. CEO의 모든 직속 부하(부사장들)에게 먼저 전달해요
3. 그다음 모든 부사장의 직속 부하(팀장들)에게 전달해요
4. 이런 식으로 같은 계층을 모두 방문한 후 다음 계층으로 넘어가요

DFS (깊이 우선 탐색)

1. CEO부터 시작해요
2. 첫 번째 부사장에게 전달해요
3. 그 부사장의 첫 번째 팀장에게 전달해요
4. 그 팀장의 첫 번째 팀원에게... 이런 식으로 한 경로를 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색해요

특징

BFS는 출발점에서 가까운 노드부터 차례대로 탐색하기 때문에 최단 경로를 찾는 문제에 특히 유용합니다.

모든 경로를 동시에 탐색하는 느낌이죠.

반면 DFS는 한 경로를 끝까지 탐색한 후 다른 경로로 넘어가기 때문에

모든 경로를 완전히 탐색해야 하는 문제나 경로의 특성을 조사하는 문제에 적합합니다.

두 알고리즘 모두 시간 복잡도는 O(V+E)로, V는 정점의 수, E는 간선의 수를 나타냅니다.

 

✍️ 오늘의 IT 초보 탈출 한 줄 정리

"고급 알고리즘도 결국 문제를 효율적으로 해결하기 위한 방법! 실생활 예시로 이해하면 훨씬 쉬워져요!"

 

여러분의 IT 초보 탈출을 응원합니다! 🎉

궁금한 점이 있다면 댓글로 남겨주세요~