정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘

오늘은 '알고리즘' 과목입니다.

컴퓨터과학을 배운다면 빠질 수 없는 바로 그 과목이죠.

백준, 코드포스와 같은 Problem Solving을 하기 위한 기본 지식을 배울 수 있는 과목입니다.

요즘 취직에 필수적인 코딩 테스트를 준비하기 위해서는 이 과목은 열심히 들어야겠죠. 

필자가 이 과목을 수강했던 학기는 2020년(2학년) 2학기, 평점은 A+였습니다.

---------------------------------------------------------

알고리즘이란 과연 무엇인가?에 대해서 교수님이 수업 첫날에 보여주신 영상입니다.

알고리즘은 '어떤 문제를 해결하기 위한 절차'를 말합니다.

알고리즘을 많이 알고 있으면 

어떤 상황에서 어떤 알고리즘이 좋을지 판단할 수 있고,

더 효율적인 프로그램을 작성할 수 있을 것입니다.

소프트웨어 엔지니어라면 필수적으로 알고 있어야 한다는 뜻이겠죠.

알고리즘은 얼마나 '효율적'인가를 판단하게 되는데요.

이때의 효율이란 Input으로 들어오는 양에 대해 얼마나 빠른 속도로 처리되는 지를 말합니다.

흔히 Big-O라고 하죠. 

예를 들어 O(n)인 알고리즘은 Input Size가 2배가 되면 처리 시간도 2배가 되는거고요,

O(n^2)의 알고리즘은 Input Size가 2배가 되면 처리 시간은 2^2=4배가 되는겁니다.

과제로는 위처럼 어떤 알고리즘의 시간 복잡도를 직접 계산해보는걸 했었네요.

그 다음으로는 본격적인 알고리즘에 대해 배우는데요.

정렬에 대한 내용을 배웁니다.

정렬이란 건 말 그대로 여러 데이터들이 모여있을 때, 이를 순서대로 줄 세우는 작업을 말합니다.

Sorting은 알고리즘 수업에서 뗄레야 뗄 수 없는 내용인데요.

워낙 종류가 많기도 하고 시간 복잡도도 전부 달라서 

알고리즘에 대해 설명하기 좋은 예시가 되기 때문입니다.

Insertion Sort, Merge Sort, Quick Sort, Count Sort, Radix Sort 등

많은 정렬 알고리즘의 시간 복잡도, 특징, 구현 방법 등에 대해 배웁니다.

이렇게 한 줄로 정리했지만 실제 배우는 내용은 무지 많습니다.

다음으로는 Problem Solving을 공부할 때 빠지지 않는 Dynamic Programming입니다.

이건 어떤 알고리즘 문제를 풀 때의 방법론?이라고 할 수 있는데요.

점화식을 세운다고 생각하시면 됩니다.

슬라이드에 나와있는 예시처럼 피보나치 숫자를 구하기 위해서 

이전 단계에서 계산한 결과를 저장해놓은 다음, 그 다음에 나올 숫자를 구하는 거죠.

이를 위해서는 Memoization(이전 단계의 결과를 저장해놓는 것)이 필요합니다.

이 다음은 Dynamic Programming으로 해결 가능한 대표적인 문제에 대해 배웁니다.

LCS, Knapsack 등에 대해 배웠습니다.

그 다음에 나오는 건 Greedy(탐욕) 알고리즘입니다.

이건 각각의 단계에서 가장 좋아보이는 선택만을 하는 알고리즘입니다.

적절한 예는 아니지만 물건을 훔치는(?) 상황인데 가방은 한 개 뿐입니다. 

이럴 때 도둑은 비싼 것부터 가방에 차곡차곡 담겠죠.

탐욕 알고리즘은 이와 같이 문제를 해결하는 방식을 말합니다.

하지만 가장 큰 문제점은 바로 항상 최적의 해를 보장해주지는 않는다는 것입니다.

이 이후에는 Greedy 알고리즘으로 해결 가능한 문제들에 대해서도 배웁니다.

혹시 기출 지문 중에 '허프만 부호화' 기억나시나요?

이 허프만 부호화도 탐욕 알고리즘으로 구할 수 있습니다.

Huffman Code 외에도 Fractional Knapsack, 

Minimum Spanning Tree를 구하는 Prim's Algorithm, Kruskal's Algorithm 등

여러 Greedy Algorithm에 대해 배웁니다.

이 다음은 그래프에 대해 배웁니다.

그래프는 이산수학 과목을 들으면 배울 수 있는데요.

알고리즘에서 빠질 수가 없는 녀석입니다.

그래프를 돌아보는데(Searching) 쓰이는 알고리즘이 그 유명한 BFS, DFS입니다.

BFS는 처음 시작한 노드에서 같은 거리에 있는 노드를 먼저 탐색한 후, 거리를 점점 늘려가면서 탐색합니다.

DFS는 처음 시작한 노드에서 최대한 많이 들어간 후, 더 들어갈 곳이 없을 때 이전 노드로 돌아와 다시 탐색합니다.

컴퓨터과학을 전공하는 고학년이라면 BFS와 DFS 정도는 안 보고 코딩할 줄 알아야.. 근데 전 까먹음

이렇게 탐색 알고리즘에 대해 배운 이후에는 최단 경로를 구하는 알고리즘을 배웁니다.

최단 경로를 구하는 알고리즘에는 Bellman-Ford, Dijkstra 알고리즘이 있습니다.

마지막으로는 그 유명하고 유명한 P-NP 문제에 대해 배웁니다.

물론 이건 아직까지 해결되지 않은 문제이므로 그냥 어떤 것인지에 대해서만 배웁니다.

유명한 문제이니 상식 좀 쌓는다고 생각하시고 한번씩 들어보셨으면 좋겠습니다. 

이 문제를 풀면 $1,000,000 + 엄청난 명예 + 기타 등등을 모두 얻을 수 있습니다

부와 명예를 위해선 컴퓨터공학과에 진학해야

한 학기 동안 이렇게 많은 내용에 대해 배우게 됩니다.

근데 이 과목 특성 상 계속 기억해야 하는 내용이 많아서

주기적인 복습이 필요한 과목입니다.

알고리즘 한번 제대로 공부해놓으면 도움 많이 될 겁니다.

다음에 시간 날 때 또 적어보겠습니다.

제가 적은 글 (클릭하면 연결)

1. 컴퓨터공학과는 뭐하는 곳인가?

2. 컴퓨터공학과 과목 맛보기 - 1. 자료구조

3. 컴퓨터공학과 과목 맛보기 - 2. 시스템프로그래밍(1)

4. 컴퓨터공학과 과목 맛보기 - 2. 시스템프로그래밍(2)

5. 컴퓨터공학과 과목 맛보기 - 3. 인공지능(1)

6. 컴퓨터공학과 과목 맛보기 - 3. 인공지능(2)

(현재 글) 7. 컴퓨터공학과 과목 맛보기 - 4. 알고리즘