정보) 컴퓨터공학과 과목 맛보기 - 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
-
저는 n수이후 전문대를 간 사람이구요. 대략 n수비용 1천만원정도의 자금을 날린...
-
sin+cos= @@ 으로 나타냈을때 숫자로 추론하기 어려운 숫자 값 조합이...
-
남자향수는 0
아묻따말닥여사비이사후말 아 묻지도 따지지도 말고 닥치고 여기서만 사라 존나 비싸고...
-
벼랑 끝에는 나락이 있다 라는 말을 조정석쌤인가? 암튼 영어선생님이 했던 말인것...
-
일주일에 한 세네번정도 단원별로 1~3개씩 풀고 지금 문제가 각각 4~5개 정도...
-
절약좀하자 시발롬아 돈도 없음시롱
-
내 주변엔 먹고살 정도만 벌면 된다 이런 사람들이 은근 많아서 갑자기 궁금해짐
-
5덮 0
국어-코막혀서 코뚫을려고 옆으로 누웠다가 눈떠보니 20분지났음 "이렇게된거 그냥...
-
백분위 95~98을 노리는 문돌이입니다.(수학 선택관련) 0
경제학과를 다니다가 우연한 기회에 다시 입시판에 들어오게 되었습니다. (목표...
-
난 죽을때까지 들고 다닐거같음.. 약간 추억저장
-
분리변표 0
쓸 지 안 쓸 지는 수능 끝나기전까진 아무도 모르는건가요? 사탐런하고 미적사탐으로...
-
연대가고싶다 0
아
-
요즘날씨에 켜고자면 덥네요
-
추억이 새록새록
-
방에 크게 씹덕 노래 풀어놓음
-
올붕이 굿나잇 0
여름 시작이 수능시작이지 진짜는 이제부터
-
전부 높은 확률 계산해보니 88%로 밝혀져 방송 발췌 (다소 수정 있음)
-
이수만, 다시 엔터사업 뛰어드나…'A20 엔터테인먼트' 상표 출원 3
이수만 전 SM엔터테인먼트 총괄 프로듀서가 엔터테인먼트 상표를 출원한 것으로...
-
대학교 시험인데 이런 경우는 어떡하나요,,?
-
1. 컨디션 난조인데 그래도 억지로 손움직여서 뭔가를 하긴 한 그런 애매타취쓰한.....
-
확통인데 5모 6등급 받았습니다 국어나 영어는 1아니면2 나와서 상관업ㄱ는데 수학이...
-
입시판 좀 뜨고싶음
-
방금 단톡에서 얘기나왓는데 나만 그런게 아니라는데 1. 살면서 SKY 성, 한...
-
인강 강사 개념책 회독이 본 걸 계속 보는 걸까요? 인강도 계속 반복하여서 보는게...
-
정석민 양자역학 2
정석민 양자역학 (18년 9평) 지문 해설 듣는데 예전에 커뮤에 달 해석에 관해서...
-
프사랑 잘 어울려 맘에든다
-
사회문화 과목 대수능 1등급/ 사설 만점을 받은 것을 인증합니다.
-
침공국이라지만, 473,400명이라는 사상자는 정말 안타깝게 느껴진다. 전쟁은...
-
3일 뒀네...
-
오답 방금까지 하고 후기 국: 독2 문3틀 90점 문학 ㅈㄴ어려움 진짜...
-
오늘(22일)안으로 일반사회 칼럼 하나 올라갈 거 같습니다 2
저 팔로우하시고 잡담태그 알림 해제하시면 칼럼이 올라가면 알림이 올 거에요...!
-
선착순/우선선발/특별전형 3개가 있는데, 3개 다 해당되거든요... 그냥 아무...
-
수능 끝나면 1년안에 3천만원 갚아야하고 군대도 끌려가게 생겼구만 애를 빨리낳아서...
-
궁금합니다 2
안녕하세요 24학번 성균관대학교 경영학과 재학 중인 학생입니다. 친구들이 많이...
-
현재나의상황 2
누워서 남은 학교생활과 졸업 이후를 걱정하며 당장 다음주까지 해야 할 일을 미루고있음
-
이건 비밀인데 8
전 아직도 온수매트 틀고자용
-
먼저 푸나요?
-
지구 질문..! 2
일본해구는 해양판-대륙판 경계인가요 해양판-해양판 경계인가요? 일본‘열도’ 이니깐...
-
소수점 빼고 국어 90 수학 96 물리 83 지구 88 떴는데 누벡은 96임 ㅋㅋㅋㅋㅋ 어이가 없네
-
이력서 쓰는중 8
도대체 어디에 쓰이는지 모를 이력서 사실 이력이 있어야 이략서를 쓸텐데…..
-
. 0
잠이 안온다..
-
나도 수능전에는 4
'간세포에서 프로트롬빈과 혈액응고인자들이 활성화(카르복실화되어 칼슘과 결합)되고...
-
I feel too sleepy now…
-
이감만큼 문학 평가원과 필작하는 퀄리티로 출제하는데가 없는듯 고난도 문학 n제 내면 대박날텐데
-
너무 슬프다 6
자고 일어나면 공부를 해야 한다고? 자기가싫군
-
펜 가격 진짜 오프라인 너무 비쌈 온라인 배송비 3000원 받는건 10개이상으로 주문하면 문제업음
-
근데 미필 6수로 대학교 다시 들어가면 군대는 어캄 4
1학년 되자마자 바로 군대 가야하나요??
-
매월승리 5678 kbs 수완 남은 대성패스 15에 양도 합니다...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김