정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
밀렸음,, 우럿서 ㅜㅜ
-
씨발 그놈의 나군 으아아아아아악!!!!!!!!!!!!!!!! 난 가다군 쓸게없어서...
-
수능 선택 물2랑 지2면 고3 되기 전 겨울방학때 뭐 하는거 추천하시나요??...
-
알람이 울리면 '일어나서 세수하고 공부해야지' 라는 의식을 하기도 전에 본능적으로...
-
김현우 미적 0
1,2주차 놓치고 이제 수강신청해서 들으려는데 괜찮나요,,,?? 아님 돈 주고라도 구할정도임???
-
존못에 20살도 아니면서 ot나 새터 가는애들 ㅋㅋㅋ 12
어떻게든 눈치없이 껴서 20살이랑 놀아보겠다고 발악하는거 웃기지않나여 조용히 쥐죽은듯이 살면되지
-
좀 뜬금없긴한데 항상의문이였음 단적인예로 19수능 만유인력 -> 나는 중3때부터...
-
경희대 화학 0
점공 더 해주면 좋겠다 22명 너무 적어ㅠㅠ
-
지금 옯붕이랑 있는데 12
저메추 해주세요
-
과잠보고 오… 했던기억이
-
40명은 돌까...?
-
근데 교육부가..? 사기업도아니고
-
안되는거면 미리알고싶어요…
-
일상에 도파민이 부족함 빠른 조발 부탁
-
작년에는 스나성공 외치시던분들 합격시즌에 다 소멸하샷는데 올해는 제발 다같이...
-
저녁의 질받 2
선넘질이든 뭐든 무물보
-
로스쿨 생각 없으면 문이과 상관없이 닥 학부인가요?
-
6~7칸 한군데만 넣으니까 표본분석이고 점공이고 이런걸 안하게 됨ㅋㅋ
-
보통 이과생들 7
내신사탐 안함요? 여행지리 이런거 말고 등급나오는 9과목... 2, 3학년 때...
-
괜히 문과가지말라는게 아니네 근데 저노력 걍 취업에 투입하면안되나
-
제주항공 참사 피해자 가족, 1년간 대학등록금 지원받는다 9
교육부는 오늘(5일) 제주항공 여객기 사고 피해자의 재정 부담을 낮추고자 피해자...
-
제2 전공이 공공거버넌스와 리더십으로 고정되고 포기신청도 할 수 없음
-
마음은 스테이인데 부화뇌동 엄청 옴 목표는 지거국이든 인서울이든 괜찮으니 계약학과인데
-
다들 원과목 버리고 투투하자
-
?
-
처단 예고함 방역수칙을 어기지않도록 조오심하라구
-
예상 예비번호 1397등인데 이거 합격 가능함? ㅋㅋㅋㅋㅋㅋㅋ
-
만들어봤는데 하나 더 맞추면 2등급이기도 했는데 그땐 가형이고 지금은 확통인데...
-
이때 민지가 착장이 진짜 이뻤지...
-
동기님 다치지 말고 무사전역합시다!!
-
하루에 한시간 반정도 잡고 10문제정도 풀고 + 오답 있으면 보고 + 돌아돌아...
-
한양대 스나 4
한양대 스나해볼려고 봤던 곳들인데 한양대 경영,정책,행정,파경중에 빵 예상되는 곳 있나요?
-
점공에서 점수만 봐도 익숙한 사람들 꽤 보이네요 내적친밀감…ㅎㅎ
-
ㅇ.ㅇ 맥os는 안쓸거임
-
평가원시치가 3
24 확통을 재현할 가능성이 있을까? 있지. 슈붕.
-
입이 근질거리거나 하소연하고 싶을땐 오르비만한게 없음
-
며칠더기다려야 하지않나요 음
-
2026대비 나오기도 전이고 2025는 끝났고 딱 애매한데 뭐 풀지… 드릴 커넥션 이해원 풀어봣어용
-
강민웅 물아일체 +기출 300 + 배기범 플랜비 역학의 기술 병행 어떨까요..!!
-
하.. 갑자기 땡겨요ㅠ
-
행발 테러 0
행발테러당하면 정시나 논술에서 불이익 생김?
-
확통 사실상 처음해봐서 진도 최대한 빼느라 수1 수2 2주넘게 유기했더니 풀었던...
-
문학 독서를 나기출 풀어볼려고 하는데 그전에 올인원을 듣고 풀이법을 정립한 뒤...
-
샘퍼 질문있어요 0
연고대 대형과 추합권인데요. 예상예비번호로 잡나요? 아님 Min.으로 나온...
-
원래 이과고 이번에 사탐런 해 보려고 하는데 생윤 사문 vs 사문 지구 뭐가나을까요...
-
비디디와 페이커 쇼메이커와 쵸비 쇼매는 쵸비랑 20년도 부터 친해지고 싶다고 했었음...
-
가능하죠? 디메리트같은것도 없고요
-
ㅇㅇ 투투 ㄹㅇ 표점 꿀임 가산점도 주지 ㅎㄷㄷ 만표가 73점쯤 된다네!
-
빵 예상하고 0칸스나 질렀는데 되려나이거 ㅋㅋㅋ 빵꾸 예상과 내가 붙는건 그냥 다른 영역인가봄...
-
지역인재 광탈권이 일반전형 뚫을수도 있다는데 팩트체크좀;; 부산의 560대면 부산대...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김