정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
브레이크타임3시 0
부터인데 벌써 1시반임 나갈까말까
-
6평 80 9평 93 상상은 보통 80초반~ 잘치면 중후반 나옴 고3 되고부터 시간...
-
D-100
-
다들 커리 만족도 어때요? 저는 독서 분량 너무 적은것 빼고는 완전 만족인데...
-
학원갈 돈은 없고 현장감은 느껴보고 싶고 그러네요
-
얼버기 0
-
50일남았는디 0
수학 3➡️1 가능하다 보시는지,, 백분위 86에서 96 국어는 91에서 100,, 받구싶ㅍ다
-
이것은 수류탄이여 죽지 않으려면 까불지들 말더라고 !
-
오늘 밤 이 세계에서 사랑이 사라진다 해도 본 사람 6
영화 재밌니?
-
머리가 지끈지끈
-
오랜만에 들으니 좋
-
늘어날까요? 줄어들지는 않을 것 같고
-
설레네요
-
보통 몇부터에요?
-
아수라 총정리 day 4 상위선 지문 푸신 분 있나요 6번에 4번 선지 판단 논리...
-
변비해결법 18
똥쌀때 단어와우기 본인 일주일전부터 똥쌀때 단어 외우기 시작했는데 몸이 공부하기...
-
나결심했어 3
일료일만 오르비한다 그러니까 오늘은 편하게하겟다는거지
-
에이징커브 이슈 체력 개박살
-
ㄹㅇ 문과가서 로스쿨 간다고 준비했으면 ㅈ댔을거같음.... 진짜 글은 안어려운데 문제에 ?뜸
-
시발점이랑 쎈 b만 풀고 수2 자이 푸는데 1등급 8개 중에 2개 간신히 풀고...
-
겉보기 등급과 실제 실력이 차이가 너무 심한거 같은데 8
수학도 지금 실제 실력은 잘쳐줘야 한 2중반 정도지 않을까 싶은
-
걍 돈 알아서 모아다가 직접 전국 표본 선정해서 공직적격성평가, 법학적성시험,...
-
수학은 어찌저찌하면 걍 되길래 과외 계속 하는중인데 뭔가 과학 가르쳐주는게 더힘든듯...
-
특목고 자사고 갔으면서 일반고 꿀빤다고 생각하는 건 좀 그런듯 수시가 적폐인 이유는...
-
커넥션 수2 0
김기현 선생님 커넥션 수2 미분법쪽 어려운건가요 제가 병신인건가요? 중반부 부터...
-
하
-
애들 공부도 직접 봐주면서 느긋하게 슬로우라이프 즐기고 싶구나
-
이거 풀어주실분 0
전 -34나오는데 답지가 없어서 답을 ㅁㄹ
-
국어 시간관리 3
제가 화작러인데 시간분배가 독서론 3-4분 화작 15분 문학35-40분 독서...
-
관독 인강재수로 백분위 85올렸다고 고3,재수기간동안 학원은 한번도 간적이없음 지방은 인강이없냐
-
주식 뭐사지 19
미장에 더 넣을까 아니면 국장 바이오 존나 맛있어보임...
-
오늘 도파 이팅 2
-
5줄 이상으로 겨우 답 내는 현실
-
공부에 동기부여가 없다 10
귀여운 여자아이가 공부 열심히 하는 남자가 멋있다고 얘기해주면 의욕이 나려나
-
어제꿈에김슨리가 0
백분위100받거싶은 91인데,, 아니 어젯밤에 꿈에서 김승리가 나온거 근데 되게...
-
어떤 주제든 의견 공유하실분 댓글로 주제 ㄱㄱ 댓글 달아주시면 제가 주제 던져드리기도 하겠음
-
ㅈㅁㅌ
-
수능공부 제대로 시작한지 6개월차인디 수학공부가 7할인데 수학만 안올라료ㅠㅜ...
-
문실정 답지 0
교재 샀는데 답지가 어디 있는 거죠..?
-
“핑클 2집“
-
데이트 못해서 울었어 12
네.
-
나머지는 다 맞히는데 리트지문만 계속 틀림 심지어 다 틀릴 때도 있는데 나만 이런 거임?? ㅠ
-
버스 타는 동안 한 분이라도 도와드리려구 15분정도 잠깐만! 수학 관련 질문받습니다
-
질문받는다 34
곧 수험 프렌드와 밥 약속 있다. 공부 얘기 아니여도 됨
-
띵학이나 조정식 실모 괜찮나여
-
수시(논술X) 1등 2등 ... 100등 여기서 상위 10% 즉 10명의 우수 학생...
-
요즘 드는 생각
-
담배피면서 ㅅX, x 등등 욕설 섞어서 말하는데 알고보니 서바얘기, 독서 가나지문,...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김