정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
되게 참 어른인 것 같음
-
강x 어케 삶? 0
자꾸 뭐 강좌랑 동시결제 안된다고 뜨는디...
-
가 눈에 들어오네요 죄송합니다 그래도 열심히 했잖아 수민눈나… 아직은 눈나가 좋지만...
-
두각 수업료 0
두각 수학 단과 수강료가 어떻게되는지 아시는분
-
착한 오르비언들 사이에 싸가지 없는 새끼가 자꾸 보이네
-
미래 성공확률 높고 지적미때문에 수요많을 것 같은데
-
달고싶어져서 미친듯이했는데 달았으니 다시 접어야지
-
유리함수에 치역의 조건 줘서 바로 점근선이 y=2구나! 했는데...
-
갑자기100톤짜리고민거리등장.
-
국어:김승리 수학:정병훈 영어:션티 kiss start 나머지 듣고 기파급 할 예정...
-
어제 한완수 추천해주신 분들이 많긴 했는데 검색 ㄷㄷㄷㄷ 돌려보니 너무 쉽고...
-
푼거 하사십 시즌1(풀다 문제퀄 떨어지는거같아서 드랍) 드릴4, 5, 워크북...
-
안녕하세요.국어 강사 배인호입니다.수업 기획하고 준비하다 보니 오르비에 자주 못...
-
종강하고 걍 재미로 풀어본 이과인데 풀이 어떰? 20번 ㄹ은 시간 없어서 ㄱㄴㄷ만 판단한거
-
중학교 수행평가 지필평가 진짜 의미 1도 없는데 뭐가 그리 힘들다고... 고닥교...
-
어머니보고 내신 챙기기 싫다고 맨날 징징대면 항상 하시는 말씀이 고생해둔건 어디...
-
누를 시간에 공부해야할듯
-
포인트는 머야? 오르비북스 사는 돈같은건가?? 레벨은 16인데 등급은 뭐야?? 글고...
-
고민되네 집독재 이제 한계에 도달했어
-
이상하구나 나는 평생 아기할래
-
사실 한다고 오르기는 할지도 모르깃음 근데차피 방학때 별거안하니깐?...
-
국어 수완 실모 난이도 원래 많이 쉬운 편인가요???? 3
궁금해서 시간 재고 1회차 풀어봤는데 80점 중후반이 떴어요 근데 제가 6모...
-
키 클 것 같고 그럼 경험적으로도 문과반에 인싸가 많았던거 같은..
-
저는 베트남에서 온 배리응우옌이라고 해요. 저는 kpop을 좋아해서 한국에 왔어요....
-
라면 먹고싶은데 2
먹고싶은 라면이 집에 없음 ㅠㅡㅠ
-
님들은 어케 생각하심?
-
1.전적대 자퇴했어도 장학 되겠죠?(의대 자퇴) 2.일과 시간표 맞춰서 출석+강의는...
-
수학 빨더텅(평가원,교육청 포함) vs씨뮬(최근 평가원만) 1
기출을 실모처럼 풀면서 복습할 예정인데 빨더텅이랑 씨뮬중에 뭐 사는게 좋을까요?
-
ㅇㅈ 5
용돈 받았는데 이거 얼마임?..
-
환율 금리 말고 또 있나요??
-
저 잘 때도 이거 포근해서 안고 그 위에 이불 덮고 잠 이러니까 부엉이에서 쓸 담요가 없긴 함
-
1:18초부터 나오긴하는데 1:32초쯤부터 하,,,
-
27도는 춥고 28도는 더워 담요에 두꺼운 이불 두겹으로 덮고 잠
-
부활하라 1
제발
-
수학 백분위에 버리고 싶다
-
2025 EBS 연계 교재 수능특강 수능완성 독서 주제 정리 9평 대비
-
예전에 맛있게 먹었는데 다시 안나오나 ㅜㅜ
-
이거 어케푸노….? 비주얼 ㅅㅂㅋㅋ
-
그런거 없당ㅋ
-
멀쩡한 줄 알았던 사람이 정신나간사람인걸 진심 수십번은 더 본 것 같은데 볼때마다...
-
핑프같긴 하지만 찾아봐도 잘 모르겠어서 질문남깁니다.. 지금도 박종민 미적정규...
-
벌거벗은세계사 일본버블 90분 영상봤는데 이것도 순공 ㅇㅈ? 0
경제니까 25수능에선 독서에서 경제가 나올 수도있으니까 배경지식 쌓은셈쳤음 히히
-
아 제발
-
잇올 빌보드 4
6모 가지고도 하나?? 빌보드 20 안에 들만한데…
-
바이든 말 더듬는 거 너무 심하던데… 아무래도 트럼프가 당선될듯… 님들 생각은 어떰?
-
-보다 크다 좀 안틀리고 싶다... 3x1=9 5-3=3 이 지랄만 안하면 좋겠다...
-
어떻게 했음? 나는 원래 수학만 못하는 사람이었음. 작년에도 6월 9월 다 3떴음....
-
17이전껀 안 푸려고 했는데 더 전년도 것도 푸는게 유의미할까요? 그리고 흔히...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김