정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://iu.orbi.kr/00066884548
오늘은 '알고리즘' 과목입니다.
컴퓨터과학을 배운다면 빠질 수 없는 바로 그 과목이죠.
백준, 코드포스와 같은 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 지1 99 92 2 98 92 어문계열만 빼면 문이과 상관없고...
-
속상하다 2
독재학원에서 편두통땜에 아침에 버티다가 지금 조퇴했는데 약먹고 독하게 하는 애들도...
-
남녀를 불문하고 투표권 박탈시켜야 됨. 머리가 나쁜게 아니라 뇌가 없는 수준임....
-
이거 손가락걸기시, 현장에서 1번이 적절하지않다는 근거좀..ㅠ
-
생윤 vs 경제 7
반수하고 있는 05임 고2 때부터 해서 3년째 생윤 하는데 3등급에서 벗어날 수가...
-
오늘 공부 0
포기해야겠다다너무 힘들어요
-
이미지t의 미친개념을 듣고있는데 뭔가 내용적으로 부실하다는 느낌이 드는건...
-
"중등기하(논증기하)" =>이 새끼가 출제 범위(간접이긴 하지만)에 있는 이상...
-
친구한테 물어봤는데 국어 중간3 수학 1 영어 3 지구 3 사문 1 적당한 수능...
-
방금 전 올린 게시물과 관련해서, 오늘 물리학과 교수님과 면담이 있었는데 아주...
-
수학n제 1
빅포설맞이이해원이로운샤인미 중에 드릴5보다 쉬운 거 추천좀용
-
ㅈㄱㄴ
-
논술에는 나온다고 얼핏 들은 거 같은데 흠흠 현우진의 고1수학 특강 "시발시발점"...
-
고1 중상위정도 가르칠때요
-
이틀연속 혼코노.. 10
요루시카 노래 중에 花人局도 있는지 몰랐어 뭐 부르지 하면서 리스트 쫙내리니까...
-
경제학에 관심이 조금이라도 있었으면 들어볼 만하지 않았나 물론 나도 경제학에 대해...
-
트럼프 재집권 시 주한 미군 철수로 한국 핵무장의 시나리오도 예측된다 하는데 뭐가 나을 거 같음?
-
6모 전까지 공부 열심히 해서 낮 2라도 찍고 싶은데 (둘 다 높3) 뭘 해야할지...
-
안녕하세요. 전공과외 찾습니다. 제가 수업받을 학생입니다. 1.과외목적: 서울대...
-
질받 아무거나 뻘소리도 ㄱㅊ
-
여쭙고 싶은게 잏는디
-
지금 한 5번짜 읽는데 진짜 뭐 어쩌란건지 모르겠음 너무 스트레스임 하 아니...
-
조금 과분하긴하지만 인설의 목표이긴한데 설의 갈거 아니면 의대지망에선 원원이 이득이 더 많나요?
-
ㅎㅅㅎ
-
ㅅㅂ석방하라고
-
아..이번주부터 앱스키마구나
-
21학년도 까지는 연의가 놀랍게도 정시로 단!20명! 뽑았음
-
엄…….
-
국어 고정 2 뜨는게 기준인듯 솔직히 문과는 수학 3만 받아도 중경외시 가니까...
-
정보) 사회복무요원은 봉사활동에 허가를 받아야 한다 3
비영리로 행하는 봉사활동도 겸직에 해당하기 때문이다
-
방금 올해 법이 나오는 해인가 경제가 나오는 해인가 고민했음 23수능 법지문이 너무...
-
제가 예전부터 오랫동안 가져왔던 3가지 질문이 있는데요, 저희 학과 교수님이나 동...
-
ㅅㅌㅊ?
-
약 먹는 중이라 빠꾸당했어
-
나는 전혀 말할 수 없는 생소한 용어들을 전문가(ㅈ문가긴 하지만)처럼 말하는거보면...
-
수능 화학 생명 0
ㄹㅇ 인생 가챠 3~5 연차 정도 하면 한 번쯤은 괜찮게 나옴 엌ㅋㅋ
-
수능만점 가능한가요? 확통이라 가능할듯
-
난 저시험 1컷 44라는게 못믿겠음 그 대가로 2컷이 38이라는 화학급 등급컷 분포를 보여주는
-
알바출동 5
학교보다 학원을 더 많이 가는거같은데ㅋㅋ
-
핵형이 정상이다. / 클라인펠터/터너.다운증후군이다. 라는 조건이 있으면, 일단...
-
1. 내가 재능충이다 2. 대학이 지잡이다 1번은 거짓이므로 2번이 정답인듯
-
지금 이미 나오고 있는 2025 강대k 모고랑 올해 6월에 대인라에서 판매할...
-
가서 둘러볼게 있어서 그런데 가장 인기많은 서점이 어딘가용
-
국:2 수:7 영:1 사탐:유기 문돌이들 ㅇㅈ?
-
고2임 수학화학보는데 머해야됨? 양적관계랑 지수로그 봄 걍 문제만 벅벅 풀다 10시에 자면 됨?
-
‘더 내고 더 받는’안…20대女·4050男이 주도했다 13
[서울경제] 연금 개혁을 위한 숙의 공론화 결과 ‘더 내고 더 받는’ 1안(보험료율...
-
둘다 미성년자인데 상대는 제가 성인인줄 아는 상황이면 2
플러팅하면 역겹겠죠?잘되지 않는한 미자인걸 밝힐수는 없음
-
교재패스 배송비 아깝네 내일 kbs 고전 나오면 한번에 시켜야지 ㅡ.ㅡ 패스면 슈발...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김