정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://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를 선물하세요.
-
바퀴벌레 나오면 당근에 벌레 잡아주세요 사례금 5만원 ㄴ이딴걸로 돈 다 쓸게 뻔함
-
소형고닉종철 2
음음 오르비를 살리자
-
잘생긴 남자는 부러울 뿐이고 이쁜 여자는 내 곁에 있을리 없는데
-
정용화 형님 사랑합니다ㅏ
-
열어봤는데 너무 어려워 보이던데
-
앞으로 11월까지 안잴 예정ㅋㅋ 난 키크니까 ㄱㅊ아 (라고 자기위로) 지금은 걍...
-
저두요 ㅠㅠ 다들 힘내세요
-
예전에 ㅎㅅ 그분이 재밌긴 했었는데 그래도
-
현역인데 2
경찰대 원서 쓰니까 이제 진짜 고삼이 됐다는 게 실감남... 더해서 뭐 아직 아무...
-
지금 딱 봐도 오르비 상태가 다 남자밖에 없음
-
김상훈 갑자기 치고 올라오고 신용선 저 아래로 가버림 양승진은 3타가 돼버렸노 ㄷㄷ
-
강윤구T 4공법 0
재종에서 강윤구t 4공법 수업을 듣는데 이게 수업 시간 제한이 있어서 인강보단...
-
자습서에 나와있음. 님들 자습서 읽으세요. 평가원의 출제의도/풀이 가 보이기 시작함.
-
오늘하루도고생하셧스빈다
-
ㅜㅜㅜㅜ +) 미적/기하 검토진 선발 결과는 내일 공지드리겠습니다!
-
수학을 못한다고 3
죽어야됨 알겠냐 특별히 수학 못하는 대가리만 큰
-
on 3
대충 밤 샌다
-
진짜 나는 내가 쓸 수 있는 최대한으로 글을 쓰는데 소용이 없네 대형고닉이 와서 살려줘야 한다고 봐
-
진짜 모솔,키작남이라 기만남이 될 수가 없다 ㅅㅂ
-
힘들게 사는구나 싶더라 ㅋㅋ
-
배성민의 드리블 어케막냐고 배성민이 제 수학학습에 가장 최적화된 강사가 아닐까 싶은 밤이에요
-
요즘 인스타 문화 이해 안된다
-
거우루 2
거울 중세국어에선 거우루였음 거우루 탕후루
-
쪽지 좀..
-
국어 학원 다닐 시간이 없어 혼자 국어 풀려고합니다 이번에 자이스토리...
-
난 거울 종종 봄 27
그나마 거울에서 좀 정상적으로 보이거든.... 사진 찍으면 개씹좆망해서
-
그걸로 여러명 꼬셧는데
-
공부는 루틴대로 하는거고........음 하루를돌아보며 의식흐름대로 기록 1.공부는...
-
뭐 부터 들어야해요? 독서만 들을거에요. 핑프 맞아요. 주변에 공부하는 사람이...
-
거울도 어딘가엔 눈이있을텐데 미안해서 못보겠음..
-
쌍사인데 탐구 할 시간이 너무 없는데 일주일에 몇 시간정도 해야할까요...???
-
. 1
-
수학 0
죽어버려 죽어버려 죽어버려 죽어버려 죽어버려 죽어버려 죽어버려 죽 죽 죽어버려 죽...
-
이상한거죠?? 학원에서 남자가 여자 잠시 계속 쳐다보고 여자도 마주보면서 약간...
-
차라리 짐승이면 이해를 하지.. 사람인데
-
보닌 수1 수2 과외하게 돼서 과외비 각각 다른날짜에 주시는데 수2는 주셨는데...
-
연대가 가고싶었는데 영어 반영비를 본후 나는 원래 고대가 가고싶었다고 세뇌하는중
-
아 훈수두고싶다 0
근데 오르비에서 훈수는 오지랖이라 야러번 생각하게되네
-
설치 설치 설치류 찍찍
-
많이 비싸려나 아님 허수여서 못 들어가려나
-
오르비언들 겁나 착한듯 15
표독한 사람들만 있는줄 알았는데 이제보니 너그럽고 포용심 넘치는 분들이 많이 보임...
-
4덮 국수 원점수 76, 69 이렇게 나왔는데 센터 문과 50명 중 4위였음 보고...
-
시대 강사컨이랑 N제 풀기 급급해서 올해는 강사컨에 껴있는 기출 말고는 거의...
-
우리집근처 7
10분거리 지하철역 다섯개 기차역 한개 12456호선 공항철도 경의중앙 있음 근데...
-
댓글점!!
-
경험치가 빨리 오르네
-
언미생지 94 84 1 38 45 늘엇다
-
지금 왜 같이 노상까고있는거지;;
-
제 3장 어느 해여름 금강변을 소요하다나는 하늘을 봤다.빛나는 눈동자.너의 눈은밤...
-
시골 탈출하고 싶다 13
여기는 이감 연계 학원 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김