정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
한지 실모는 0
하루에 몇개씩 치는게 정상인가요 그냥 1일1실모하면서 이만복 슥슥 돌려보려고 하는데...
-
수학 푼거 정리 2
2023 뉴런 5회독은 한듯 기출어시스트 수분감 배성민 드리블 수1, 수2, 미적...
-
초창기 물바의 향이 난다
-
이재명 조국 대통령 당해봐야 정신차리지
-
시즌2보다 맛있나요
-
뻘글만 쓸거야
-
"숭배해라"
-
인강패스랑 여러과목쌤들 교재랑 모의고사랑 이런거 전부 다 해서요 평균치가 어느정도일지 궁금합니다
-
롤계정 잠가놨더니 부계로 솔랭 돌리는 삼수생을 뭐라고부름? 4
시발 하..
-
수학황들 이거좀 3
이거 치환이랑 그래프 그려서 말고 대수적으로는 못푸나
-
혼자 다니니까 외로워요..
-
막 3등급이런데서 정체되는 경우도 있나 막 2년씩?
-
19년 살면서 뭐 하나 이룬 게 없네 내 인생 이대로 괜찮은가...
-
좀만 공부하면 오후 6시 이럼… 마법같음
-
국어 2중 ~ 3초중 수학 높2 ~ 3극초 영어 1 탐구 1 1 성공하면 서성한...
-
국어 어이없는 실수 줄이는데에 실모 풀고 오답노트 적는게 도움이 될까요?
-
생2 킬러는 0
특히 복추, 코돈은 예전만큼 어렵게 나오진 않겠죠? 수완에는 복추하고 제효 복잡한거...
-
사진은 강대 k 본 성적이고, 올해 6,9 평가원은 둘다 3등급, 이감 2~3초...
-
9,10,19 42점. 문제진짜 잘냈네 작수끝나고 공부 거의안한거 치곤...
-
최고난도 과학 지문, Crash course로 대비하기 0
안녕하세요 독서칼럼에 진심인 타르코프스키입니다. 혹시 Crashcourse를...
-
나만 안 외우나ㅜㅜ
-
무서움 3
모의고사 운영 연습을 그렇게 많이 했음에도 불구하고 내 실력은 분명 이것이 아님에도...
-
Fx가 0이랑 2에서 0이 되는데 불연속인거 아닌가요? 잘 이해가 안되서요..
-
명곡 중의 명곡
-
한번 망생 테크 타니까 이것도 벗어나기가 쉽지 않네여
-
이감 국어 오프 모의고사 6-4 답 번호 알려주세요.. 답지 잃어버렸습니다ㅠ 이모...
-
어떰?
-
진지함
-
인스타 릴스 뜨면 죽여버리고싶음 ㄹㅇ 지만 시험전날 영어 수특 n회독했냐 지만 수능...
-
출출~허이
-
막 ‘ㅎㅂ여중딩 가슴‘ ’ㅎㅂ여중딩 레전드‘ 이런 제목.. 커뮤에 다른 글들은 다...
-
님들은 몆번해봄
-
내년에 입학할때 현역들이랑 있을때 늙어보이면 안돼니까
-
고2 9모 성적 4
목표 (서성한 공대+@)인데 정시ㄱ? 내신 합산 3.9x~4.0x
-
질문 해드림. 12
대신 천 덕씩 내야함.
-
토요일은 현강 두개 들으러 가다 보니 뭐 측정할 공부 시간이 안나와서... 토요일은...
-
Making cookie dough with shit 6
nice ingredient for dark chocolate chip cookie
-
노베 기적일지 D-47 “기회는 일어나는 것이 아니라 만들어내는 것이다.” -크리스...
-
안테르그라테의 기계가 통계와 확률로 예언한 3차대전을 일으킬 전범을 낳을 남자가...
-
생각해보고 정리해봤는데 ㄱ 가정하는거 말고 정상적으로 푸는게 가능한가요…? 약간...
-
수2를 젤 잘하긴하는데 마무리용으로 하나 하고싶네여
-
…….그래서……..내가…문학을…….못해요…..
-
뭐가 있을까 님들은 그때그때의 욕망에 충실하지 않고 열심히 사는 이유? 동기?가 뭐임
-
내가 가진것을 모두 내려놓았는데 수능 성적 하나는 나에게 줄 만도 하다
-
혹시 일요일 같을 때 평소보다 약간 늦게 일어나시나요? 아니면 수면패턴 항상...
-
요즘 공부를 한다기 보다는 실모를 쳐내는 노동을 하는 느낌인데 2
국어 영어 격일로 하루 한 회 수학 물리 지구 하루 한 회 이정도면 딱 적당한...
-
눈만 감으면 그동안의 내 수험생활이 파노라마처럼 스쳐지나가면서…. 참 고생도...
-
난 솔직히 그중에 절반이 허수일거라고 생각함. 하루에 10~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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김