정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
못배운 놈이지
-
입결, 거리, 등록금, 취업 다 따져서 어디가 젤 좋나요?
-
드디어 오르비가 정상화 되어가고 있다
-
41번에 보면 답이 4번인데 해설 보니까 고지 의무 위반에 해당되는 사항이 보험...
-
어떤 못배운새끼 대가리에서 나온 정책인지 진짜 ㅋㅋ
-
학교마다 기준도 다 다르고 편차도 크고 선생 역량도 다른데 이걸 공정하게 평가하는...
-
하니 2
-
알려
-
걍 난 수시정시 관련해서 이정도만 손봐줬으면 좋겠음 2
수시정시 비율 정상화 교과 학종 졸업후 1년이하만 넣을수있게 제한 20년전...
-
기출 풀었는데 농담 아니고 반타작함 ㅋㅋㅋ 그리고 과거 기출 보니까 비율? 직접...
-
주변 결혼하신 형 누님들보면 학창시절때부터 연애해서 결혼한 케이스보다 거의 나이먹고...
-
카르마 그런 게 아니라. (물론 정의를 지키면 좋지) 안걸리게 대처를 하냐 이거임...
-
시대라이브를 들어갈지 구해서 그냥 풀기만 할지 고민인데
-
f(x)를 매개변수 t로 나타내었을 때 x=2t^{2}/3t^{2}+1...
-
얼마나 대단한거냐 나는 아직도 내신영어가 혐오스러워 죽겠음 그리고 현실을 보니까...
-
나 그메타 싫은데..
-
내신시험하고 수능시험은 요구 능력치가 다르잖음.전자는 물론 능지도 중요하지만...
-
제니, '실내 흡연' 사과 "문화적·시대적 문제, 맞설 수 없다" 0
최근 실내 흡연으로 논란을 일으켜 사과한 그룹 블랙핑크(BLACKPINK) 멤버...
-
저 때는 그냥 기출만 무한반복하면서 자신만의 풀이 찾아서 정립하거나 하면 어느정도...
-
고대처럼 최저 높이기 ㅇㅇ 3합7 병신최저가지고있는 그 대학이랑은 대비되긴함 ㅋㅋ
-
결국 메인 올랐었구나 ㅋㅋㅋㅋㅋ
-
대인라 정석준t 0
지금 합류해도 될까요?
-
노래부르는 사원들 모두가 작당해서 e:지각한 사람을 야유하는 듯한 기분이 들었다....
-
g(x)가 연속이고 항상 0보다 크거나 같을 때 g(x)를 작은 수에서 큰 수로...
-
내가 그래요..
-
GOAT
-
메인글 수시 6
아 내가 그 사람 이미 차단했었구나 ㅋㅋㅋ
-
..
-
출제위원이 운영햐는 수능 학습컨텐츠개발하는데가 잇다는데 어딘가요...궁금궁금
-
이감또좃박앗서 2
71점이라 우럿서
-
“정치, 도덕성 없이는 미래 없다”… ‘영원한 재야’ 장기표 별세 1
장기표(79) 신문명정책연구원 원장이 22일 별세했다. 장 원장은 이날 오전 1시...
-
멘탈 나감 0
정시준비중인데 ㅈ반고 가서 수시로 대학가면 되지 왜 어렵게 정시로 대학감 대충 이런...
-
저런 병신같은 글을 쓰면서 본인의 열등감을 드러내는 찐따 하나쯤은 있을 수 있다고...
-
근데 의대에선 내신식 암기능력이 더 필요하지 않나요? 1
안가봐서 모르지만
-
전 둘 다 합격할 건데 기회를 뺏네요,,
-
대학가는 놈이 승자 학점 잘 따는 놈이 승자 취업 잘하는 놈이 승자 승진 잘 하고...
-
화학 질문 3
쌍극자 모멘트 합이 0이 아니라서 ㄷ선지 틀린 것 아닌가요?
-
이미 이런선택 해버린거 그냥 9모 유지정도만 됐으면 좋겠단 마인드로..
-
화2 재밌네 6
독서 과학풀다보니까 관련내용 자주나오길래 물리랑 화2 오랜만에 공부 중인데 생1에서...
-
그냥 수능접고 알바하러가야하나 ㅠㅠ 정신줄 놔버린듯
-
컷이라도낮아조제발
-
같은 모의고사에요
-
내년 수능 만점을 진심으로 목표 삼고 지금 공부중인데 8
아니 내년에 의대 정원 다시 돌아오는 거임?? 대학 다니면서 남는 시간마다 공부중인데 x발 ㅋㅋㅋ
-
근데 오르비 글자를 반대로 쓴 듯요
-
왜 힘든 정시의 길을 걷나?
-
이번 9모 수학 시험지 풀어봤는데 찍맞없이 80점 정도 나왔습니다. 뉴런 수1 들어도 될까요..?
-
맞팔 3명만유 17
갈색 테두리 없애고픔 ㅜㅜ
-
실모풀러 스카옴 0
전과목실모를벅벗
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김