정보) 컴퓨터공학과 과목 맛보기 - 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 + 엄청난 명예 + 기타 등등을 모두 얻을 수 있습니다
부와 명예를 위해선 컴퓨터공학과에 진학해야
한 학기 동안 이렇게 많은 내용에 대해 배우게 됩니다.
근데 이 과목 특성 상 계속 기억해야 하는 내용이 많아서
주기적인 복습이 필요한 과목입니다.
알고리즘 한번 제대로 공부해놓으면 도움 많이 될 겁니다.
다음에 시간 날 때 또 적어보겠습니다.
제가 적은 글 (클릭하면 연결)
3. 컴퓨터공학과 과목 맛보기 - 2. 시스템프로그래밍(1)
4. 컴퓨터공학과 과목 맛보기 - 2. 시스템프로그래밍(2)
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
안자는사람 1
너무놀아서 생활패턴 망했다.. 그냥 ㅈ같다ㅏ
-
Ky 정시 농어촌으로 간 사람이 일반전형으로 쓰면 어디대학가나여?
-
이제서야 언매고정적으로 다 맞기시작..! 과연 이게 이득일까
-
아 너무 속상하다
-
불키고 과제한다 시부레
-
이거 어케빼지?......... 슬슬 평균 넘을거같은데 야식을 줄일까요 아니면 수능...
-
고2 수학 1
김기현 파데킥오프 하고 아이디어 듣고 있는데 제가 고2 9모 수학 6등급인 너무...
-
얘만 돈받으려고 않았을거 같긴 한데 솔직히 두창이도 정부 당 동원해서 여론선동...
-
오르비잘자 5
-
머가 좋을까요 시간상 하나만 할 수 있을듯해서
-
최애 정진솔이던 극성 닰붕이었는데 파생그룹인 아르테미스나 루셈블은 뭔가 그때 그...
-
기하 선택 작수 92 / 9평 96
-
질문 잠깐 받아봄요 20
고졸 무직 아이돌 짬밥 8년차 아이오아이 위키미키 // 아이즈원 이후 아이브,...
-
너무 힘들다 사실 그냥 다 지치고 버거운 느낌 새벽이니까 가짜 힘듬이겠지
-
도박묵시록 카이지 슈타인즈게이트 데스노트 이런거 되게 재밌게 봤고 아인...
-
문학계속 기출위주로 공부하는데 계속 시간이 빨리거나 선지가 깔끔히 안맞아 떨어져...
-
원래 온라인에서 무료로 다운받을 수 있었는데 갑자기 바껴서 교사만 다운로드 할 수...
-
원정에서 토트넘 현실이 이랬는데 그 분 사라지니 ㄷㄷㄷㄷㄷㄷ 대승 손흥민 있었으면...
-
고2 아수라 0
정파인데 들을까요?
-
교과서는 에너지띠 이론 그냥 파울리의 배타원리로 퉁치고 조국광복회도 북한이...
-
미대 입시생이라 이쪽밖에 모름 이대 미대로는 상위권인디.. 서울대 디자인과 넣는...
-
텐하흐 나가 ㅗㅗ
-
알바하면서 내 또래 서양인지 유렵인지 모르겠는데 백인 여자들 손님으로 오면 너무...
-
지금 반토막임 코묻은돈 용케 모아서 셀트리온에 50넣었는데 잠깐 40%찍고 이후로...
-
진짜 농어촌.. ㅂㄷㅂㄷ...
-
드릴 2024 1
드릴 2024 수2 어렵나요?
-
난 유명한 장기투자자임 34
고3때 코스모신소재 400넣고 재수하고 대학교 다니다가 4천 찍혀서 팔았음 2주...
-
뱀의 꼬리가 되자
-
안녕하세요 저는 지금 고1이고 메가패스 끊었는데 겨울방학때 관리형 도서실에서...
-
이대를 저평가하는것은 곧 모든 여성에 대한 모욕이다 3
쎈을 고평가하지 않는것은 곧 호훈에 대한 능멸이다. 생각 플로우가 이런 사람들을 멀리해야됨
-
스트레스 받아서 그렁가 6월-현재까지 약 5키로는 빠진듯여;; 저체중됨 ㅜ
-
おやすみ 10
-
진짜 보법이다르네
-
사실 저도 이대 2
가본적은 없는데 관련해서 썰 풀자면 작년 4월즘인가 신검을 받으러 갔어요 1층에서...
-
공부하다 과로사 1
지금부터 수능까지 하루 2시간 자고 매일 20시간 공부하면 과로사 할수도 있나요/
-
오랜만이에요 4
-
분명 기가책에선 옷색깔 바뀌는 컴퓨터옷이 생긴다고 했는데
-
메이플이 갑자기 재밌어졌네~
-
연상 누나랑 대화를 나누고 싶구나…. 대학 잘 가자 ㅈㅂ
-
와야만 한다.
-
이번 9모 바쟁 오프라인 간쓸개 연계임 이감 전 지문 독서 적중한거
-
논란 종결.
-
이대목동병원에서 태어남
-
공무도하 공경도하 타하이사 당내공하
-
아쉽네 다전제에서 만나면 좋겠다
-
내일의 할일을 4
오늘로 미루지 말 것
-
논란 잠재우기 3
잘자
-
9월-11월 사이 지치고 .. 해이해지고 ..
-
건대성적으로 로스쿨갈거면 서성한급 대우 ㅋㅋ
-
경한을 붙은 나를 상상하고있음
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
빨리 n log n 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김