정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://m.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를 선물하세요.
-
초음파, 뇌파, X-ray 사용보다 훨씬 더 파급력이 클 수 있는 한의사의...
-
진단용 의료기기 풀리는건 호재고, 이건 조금 악재일 수 있겠네요. 호재악재 둘다...
-
물론 실제로 폐과하진 않을거 같지만, 정말 초강수를 뒀네요...ㄷㄷ
-
간호법과 의사면허처벌법이 국회 본회의로 직회부됨에 따라 사실상 국회통과로 법안제정이...
-
무조건 의사? 18
Image caption 많은 분들이 참여 해 주셨네요. 이렇듯 질문에 따라서...
-
80년대 어느 학교 어느반 진학 한반에 60명 1등 서울대 물리학과 2등 서을대...
-
메디컬계열의 강세로 앞으로는 메디컬계열학과가 두루 있는 학교가 발전 할거 같은데...
-
믿는 종교가 있으신 분들은 믿는 신께 그리고 각자의 조상님과 부모님께 감사 인사...
-
설치 또는 연치 vs 삼룡의 지거국이 많아서... 잘나가는 치과의사 vs 평범한...
-
집안의 배경이 없어도 내 밥그릇 지켜주는 의협 치협 한의협같은 거대 이권단체가...
-
의사 수입? 9
부모님 도움이 없다면 치과의사와 수련과정이 긴 MD의사중 누가 더 금전적으로 이득일까요?
-
ㅈㄱㄴ
-
침이라는 특화된 술기와 구강질환 및 치아 관련 내외과적인 술기를 갖추고 있는 젊은...
-
한국사0점 12
아니 본인 납치 안당하려구 한국사 다 틀린거만 찍어서 0점임데 9등급 성적표...
-
안녕하세요, 치과의사&치대생만을 위한 1등 모바일 커뮤니티 모어덴입니다....
-
안녕하세요, 치과의사&치대생만을 위한 1등 모바일 커뮤니티 모어덴입니다....
-
안녕하세요, 치과의사&치대생만을 위한 1등 모바일 커뮤니티 모어덴입니다....
-
안녕하세요, 치과의사&치대생만을 위한 1등 모바일 커뮤니티 모어덴입니다....
-
안녕하세요, 치과의사&치대생만을 위한 1등 모바일 커뮤니티 모어덴입니다....
-
2021 정시 때처럼 이대의대, 카관의, 원광치 등등 다 2022 정시에는 확통...
-
의치한 군대 9
현역으로 안가고 공보의로 가는건가요?
-
교환 ㄱㄱ
-
대성인강 추천 해주세요 dnjfzja 저도 해드립니다 1
대성 추천 부탁드립니다#인
-
경희대치대는 광탈이겠죠..? 부산대치대와 경북대치대 같은 경우는 입결점수가 아니라...
-
신기하네요
-
제가 이번에 지방한의대에서 예비를 받았는데 현실적으로 가망이 없는 번호같아서...
-
의치대 고민하면서 치대쪽 알아보니 치대는 옛날보다 많이 떨어졌네요 15
무슨 설 3대치대인 경희치가...가군에 경희치랑 충남의랑 설화학 고민했었는데.....
-
서울대 화학부 vs 경희대 치대 vs 충남대 의대 /// 연세대 치대 vs 한양대 의대 12
모두 붙는다면... 어디를?
-
전국 상위 5%는 상위권 축에도 못낀다고 하는걸 봤는데 기준이 대략 몇%정도인가요?
-
논술 4
안녕하세요 어느덧 입시가 끝난지 1년이 다되가는 사람이네요ㅎㅎ 벌써 시간이 이렇게...
-
워낙 암기하는 걸 잘하고..천문학을 굉장히 좋아하기 때문에 해볼까 하는데...
-
많이 고민했었는데 결국 떙깡부려서 하고싶은거 할래요 ㅎㅎㅎ저는...
-
제목이 질문입니다. 이를통해 다른 발표안난 의치한도 기존의 정확사의 발표신뢰도를...
-
의사면허 있는 치의학 전문의로 불리나요 아니면 그냥 치과의사로 불리나요 논쟁 보다가...
-
2014년 원점수 346에서 2015년 393까지 재수후기 20
저는 수능성적이 100 96 100 50 47 이 나왔습니다. 작년 제 성적이 90...
-
이점수로 한의대 추추추추추추추추추추라도 갈만한데 있을까요? 2
물론 실수가 실력이고, if를 붙인다는건 정말 부질없는 개소리라는건 알지만 수학4점...
-
점공 계산기로는고속성장님 계산기가 짱이었던걸로 기억하는데의치한 수험생들의 노고를 상당히 덜어주었던
-
안녕하세요 지금 수시접수때문에 골머리를 썩고있어서 질문드립니다ㅠㅠ저는...
-
ㅈㄱㄴ
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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김