정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
"BTS도 군 복무 열심히 하는데…" 병무청장 폭탄 발언 1
이기식 병무청장이 체육·예술요원 병역특례 제도에 대해 "없어질 수도 있다"면서 폐지...
-
고2인데 이제막 정시로 틀었는데 6모에서 11111 일케 못받으면 샘들한테 욕...
-
벌점 생겼어요 ㅜ
-
수잘싶 2
아.
-
대학 상향이다 하향이다 이런 거 담임 선생님이 프로그램 돌려봐서 알 수 있다고...
-
안녕하세요? 전원 서울대 출신 생기부/세특 전문, 올리미 컨설팅입니다. 고등학생...
-
안녕하세요. 이투스 인문논술 5년 연속 1타 강사. 논술을 가르치는 최은식T입니다....
-
ㅈㄱㄴ 재수이상만 푸는 것 같아서 질문드려요
-
[속보] 서울고법, 의대생 자녀 둔 판사 '의대증원 재판' 배제 6
의대 증원 금지 가처분 신청이 1심에서 대부분 각하된 뒤 항고 절차를 밟는 가운데...
-
근데 또 체면이 있는데 무르지는 못하겠고 오또케 오또케 = >그냥 딱 이러는 중임
-
학원에서 줘서 풀어보는데 왤케 별로인 것 같지 지문도문제도맘에안듦 내가 이상한건가요
-
운동 ㅈㄴ 한 글래머가 진리임 반박할수 없다 이건 ㄹㅇ
-
의심하지말자 0
-
19) 5
변하지않는 나날에 울고 있던 나를 너는 상냥하게 끝으로 이끌어 잠기듯이, 녹아가듯이...
-
ㄹㅇ로
-
내가 알기로 정부가 브리핑할때 유급 증원 감축 관련해서는 늘 '유급 시키지 않겠다'...
-
근데 사실 수시러들이 수능 공부할 시간이 없다도르 하는 것도 좀 웃김 6
수능이 공부한다고 오르는 시험인가? 최상위권으로 갈수록 관계가 떨어진다고 본다 현역...
-
저 형광펜 친 부분이 약간 짤린느낌 있으니까 부정합이 맞다는건 알겠음 근데 그러면...
-
.지금 20일짼외우는데 모르는단어가 day당 많아야 3,4개인데... 뒤로가면 좀 어럽나요
-
4시간 30분이나 잤는데도 너무 피곤하네 실모 점수도 이상하고 작년에는 2시간 자고...
-
나는 유명한 사람 다들어보고 하다가 체화 안되서 드랍하고 혼자하는데 궁금함..
-
형은 씹덕 아니라서 살 생각은 없는데 그냥 궁금해졌다
-
수업끝나고 바로 조져야지
-
https://orbi.kr/00067979973/%EC%A7%80%EC%9D%B8%...
-
국어 보면 요즘 맨 앞에 글읽는법 지문 나오던데
-
사탐런 한 사람 0
선택과목 어떻게 하셨습니까
-
그냥 누군가가 탈릅한거라고 믿을게요 ㅠ
-
남자들아
-
영 좋지 않은 일이 일어날수도 있음
-
조그만 실수해도 나락 가는건 두려우니 일반사회로만 선택하자 X 하남자적 사고방식...
-
78명중에서 43등이네 ㅋㅋㅋㅋㅋ 그래도 평균점수보다는 높아서 다행이야
-
교수님이 미국분인데 내가 영어를 영국식으로 알고있어갖고 몇몇 단어를 서로 잘...
-
"심란합니다" 연매출 1243억 성심당이 떨고 있다…왜 1
성심당은 빵집이다. 대전에서 빵을 만들어 대전에서만 빵을 파는 동네 빵집이다. 겨우...
-
1-2등급 감점차이가 수학 4점 한문제보다 차이 안나지 않나요?
-
군수 사탐ㅠㅠ 0
5월입대라 올해는 그냥 쳐보고 내년 수능 진지하게 준비하려하는데 건수...
-
교과서 느낌의 잔잔한 표지보단 색감 강렬한 이런 디자인이 좋은데 + 수특도 이쁘다 생각함
-
ㅈㄱㄴ
-
어케한거지ㄷㄷ
-
뉴런 한완수 3
뉴분감 1회독이 끝나가는데 제가 인강에 집중을 잘 못해서 뉴런 2회독 대신 한완수...
-
블아 빵 2
삼성역 근처에는 다 없네… 도시락 살때 소리 겁나 나서 좀 쪽팔렸음
-
아 ㅈㄴ좋다
-
블아빵 ㅇㅈ 6
솔직히 상품 찍을때 카운터에서 블아 브금 나오는건 아니라고 생각해요
-
뭐가 어려움?
-
진짜 이영상 보고 울었다 망했음에도 어디로 향해야하는가
-
화생 43이지랄로 떠서 사탐run 바로갈겼는데 무슨과목할까 고민하다가 철학 좋아해서...
-
고2 물1 중간고사 어제 봤음 애들 다 첨엔 배기범 듣다가 어렵다고 다른 강사들로...
-
영어글씨 와자자자 써있고 그 글끼가 꼬불꼬불하게 휘어지면서 한 면을 채웠음 색감은 비비드함
-
오늘 학교 다녀오면서 gs 5곳 정도 갈 수 있을듯 7
통학 왕복 4시간이라 의외의 이득?
-
편의점 들어갔는데 계산대에서 누가 계산할때 블아소리 났음 근데 아무리 찾아봐도 포켓몬 빵밖에 없었음
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김