정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://iu.orbi.kr/00066884548
오늘은 '알고리즘' 과목입니다.
컴퓨터과학을 배운다면 빠질 수 없는 바로 그 과목이죠.
백준, 코드포스와 같은 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를 선물하세요.
-
의대는 군의관 끌려가니까 떡락이고 대통령 밑에서 형님형님 하는 정치외교학과가 Top티어 찍나
-
병력동원소집대상 3
1. 예비역 2. 군사교육소집을 마친 보충역3. 병역법 제66조 규정에 의하여 보충역에 편입된 사람
-
응시되던 도중에 시험지 내용도 다 아는데 어캄?
-
북한 도발씨키고 대학 모집정지시켜서 만회하려고 하나?
-
님들의 솔직한 답변을 들어보고싶음 참고로 adhd도 있긴함
-
ㅇㅈ..?)확실히 수험생활하면서 조져지긴 하네요 피부가 11
방금 찍은거고이게 작년여름 수능 끝나면 관리해야지..
-
혼자 있는 친구한테라도 가서 살갑게 같이 추억이라도 하나 만들어 줘라. 학창시절...
-
ㄹㅇㄹㅇㄹㅇ
-
그런 듯
-
한석원 차영진 10
고2 노베인데 이제 정승제F[(즁등수학,도형), 수꼭필] 끝내고 노베한테 괜찮다는...
-
어렸을때 걱정 안했는데 지금 생각하면 ㅈㄴ 무식하네 걍 죽는거 사실상 확정인데
-
별 생각없이 시험기간에는 공부하고 시험이 끝나면 놀고 비록 내신이 안나오고...
-
군필이랑 미필이랑 전쟁이나 군을 바라보는 태도가 너무 다름. 자원입대니 전쟁이니...
-
왜 200년 만에 이산화탄소 수치가 급격하게 올라간지... 4
알 것만 같음...
-
전쟁 찬반 12
투표
-
스물세살이오 ― 三월이오 ― 咯血이다. 여섯달 잘 기른 수염을 하루 면도칼로 다듬어...
-
택배비내고 일괄 구매하겠다고 했고 결제방법 안전결제인가 그거말고 없는거같아서 구매랑...
-
초딩입맛임 표지도 예뻐야함
-
어라라
-
https://akorn.bab2min.pe.kr/input/...
-
혼틈 ㅇㅈ 2
하지만 돌아온건 여드름 폭탄 혐짤이죠? ㅋㅌㅋ
-
난 미필이어서 0
자진입대하면 폐급이겠지만 가능만하다면 자진입대 할거임 애국이라기보다 북한을 워낙...
-
챗지피티랑 나무위키면 무서울 게 없다
-
주체성은 한편으로 진실됨을 의미하기도 한다. 어두운 쪽으로 치우치기도 했다가,...
-
솽화뎜雙花店에 솽화雙花 사라 가고신 휘휘回回 아비 내 손모글 주여이다 이 말미...
-
예전에 되게 재밌게 보다 말았는데 완결났네 수능끝나고 정주행해야지
-
조회수 왜이렇게 빨리올라가나요
-
딱 1강만 더 듣고 수면
-
키 1
30cm 상납하면 뭐랑 교환 ㄱㄴ?
-
나는 이게 편하니까 갠찬나…
-
예:) 수능날 가방 싸는 생각을 함 -> 우연히 휴대폰이 가방안에 들어있는 상상을...
-
우리말의 주격조사 '가'는 일본어 차용일 가능성이 농후하다.
-
qwerty님 13
너무 귀여워요 타자 치실 수 있나요
-
수능 평백 83 10모는 살자방지 모고가 아닐수도 있지만.. 그렇다고 수능이...
-
저번에는 6시 얼버기 실패했으나 오늘은 기필코
-
2 싸움, 간통, 살인, 도둑, 구걸, 징역, 이 세상의 모든 비극과 활극의...
-
미적기준 1컷 몇으로 잡으면 괜찮을까요?
-
수열 0
15번 문제에서 매번 시간 오래써서 맞추거나 틀리는데뇨ㅜㅜ 수열을 확실히 잡고...
-
뭐어케해야되는거임…,
-
편하게 보세요 그렇다고 아침에 엄마가 안깨워줘서 8시에일어나서엄마한테화내고...
-
커뮤질과 내 경험에만 의거하여 작성한 글이니 잘못 알고 있다든지의 것들은 댓글로...
-
안녕하십니까, 국어 연구소 Team. KUKLL 입니다. 10평이 코앞으로...
-
디플러스 고맙다 1
내 남은 수험생활을 위해 녹아웃을 자진해서 안 가다니.. 씨발놈들아
-
7년 전 3만원을 현재 물가로 치면 몇 만원 하려나? 대충 예상도 ㄱㅊ하니 댓 좀 부탁해요~
-
ㅋㅋㅋ
-
사탐 과탐 하나씩하는데 사탐은 50나올 자신있는데 과탐얘가...
-
ㄷㄷ 까먹고있었다
-
주무셔요 1
특수어휘 안 나오려나
-
ㄹㅇ로
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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김