정보) 컴퓨터공학과 과목 맛보기 - 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
[서울=뉴시스] 백영미 기자 = 의대 증원 관련 법정 협의체인...
-
국어 X (추석연휴 이틀동안 문학 특강들은게 전부) 수학 내 실력이 너무 ㅈ밥이라...
-
수행 공지를 10개정도 들은거같은데 언제 무슨 수행하는지 제대로 인지하고 있는...
-
prepare는 목적어로 to부정사를 취하는 동사라고 알고있는데 she...
-
속보 꼬얌잉 집 나옴 10
잇올으로 향할거라고 밝혀져..
-
곧 180일되는데 고3 현역 언매 미적 화 지 22115 지1은 이제 시작이라...
-
심심해애ㅐ 9
-
레전드공하싫 13
ㅜㅜ
-
필요없다 그래서 넘겼는데 산술평균 기하평균 많이 쓴다는 말도 있고;;
-
이걸 현장에서 풀라고 낸 게 맞나? 아무리 생각해도 평가원에서 리트 출제용 문제...
-
그냥 속함수가 겉함수 정의역이니 x축으로 보기 편하게 그려놓는거임?
-
2019년도 우주론 지문인듯 ㅋㅋㅋ 이걸 풀라고 수능에 낸건지 참 ㅋㅋ
-
매월승리 0
고2이고 올오카 다 끝났는데 감 잡는 용으로 매월승리랑 피램8개년 기출 병행하려고...
-
나무관세음보살...
-
킬캠 73떳는데 다들 개잘하네 나만 어려웠냐? 14번까지 다맞춰도 20,22 그리고...
-
나도 조심해야지
-
숙취때매 늦게 일어난건 아니고 늦게 자서 늦게 일어났어요 ㅜ 애초에 숙취 있을만큼 안마셨음
-
조은 아침입니다 0
오르비 안들어온지 벌써 이틀이나 지났내.. 오늘은 집에만 있을 예정임니다
-
잠오네 4
자면안듀ㅏ는데
-
수행이고 뭐고 그냥 다 포기하고 싶다 ㅅㅂ
-
윤사 도가 0
노자 장자 구분하는 꿀팁이 혹시 있을까요? 어렵게 나오면 이 둘도 구분할 줄 알아야...
-
재밌네 시간도 빨리가고 근데 패드가 없어서 풀이하는게 좀 불편함
-
한장에 한시간 마이아이즈
-
필수적 부사어도 여전히 부사어라서 부속 성분일 뿐 필수적이라고 해서 주성분이 되는...
-
일단 밤을 새면 제가 자제력이 좀 없어져요... 저번에 술 안마시고 맨정신으로...
-
근데 시냅스 0
확통이 수1 수2 보다 훨씬 쉬운 것 같음 사람들이 왜 거르라고 하는지 잘 모르겠는 수준
-
14 15 21 22 29 30빼고 다 맞추기라도 하면 좋겠음
-
대답이 없네에!
-
물리를 안배워서그런가 계속봐도 ㅁ뭐라는지모르겠음:: 뭘 배워가야하는거지
-
설맞이를 파노
-
평가원 몇정도 뜰까요
-
수잘싶 0
22번 맞춰보고싶다 선택 다 맞아보고싶다
-
설대식 430이정도 받으면 설경까지 되겠죠? 55명중에 이거보다 이상은 별로 없을거같은데
-
바로 수능교재 디자인 전문 D'CORD 이분의 작품으로 현우진 교재 : 뉴런, 드릴...
-
수잘싶 10
아.
-
생각보다 돈 잘벌림 대략 9만원 가까이 벌음 나를 찜한 학생 이거...
-
아닌애들도 있긴한데 경향성이 약간 있는거같아서 신기함 전 여잔데...
-
ㅡ.ㅡ. ㅡㅡ.ㅡ ㅡ.. . … .. .ㅡ. ..ㅡ …
-
그나마 제일 낮은편인 충남약 기준으로 백분위 평균 국수탐 92.67 99.67...
-
뭔가 무기력함
-
콘 증량 후기 0
저번에 27먹고 효과 없는거 같다고 올려줄 수 있냐고 쌤한테 물어봤는데 효과...
-
ㅈㄱㄴ
-
제 커리는 국어 김승리 수학 안가람 경제 우영호 정법 최여름 이건데 님들은 커리 어떻게됨요??
-
공휴일 시즌 시작은 못참겠는데
-
인용되면 아무것도 못얻고 상처만 남은채 돌아가자는 사람 나온다
-
의지라는게 참 무섭다 14
분명 어제저녁에는 내일도 8시부터 공부안하면 사람새기가 아니다 이렇게 다짐하고...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김