정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
근데 20번 뭔가 해설하고 다르게 풀었는데 제가 생각한게 맞는지 확인 가능하실분 계실까요
-
6모 1 9모 2 10모 2 현돌 파이널 44 47 50 걍재미로 ㅇㅇㅇ ㅎㅎ
-
근데 쉽게내려고 계속 깎다보니 이래 됐다고 들음 친구 학교 쌤이 그럼 평가원 자주 가신다던데
-
20때 bis는 다맞았는데 계약 한문제 틀림 열차표 내용일치 문제 이거 아직도 헷갈림
-
생체 리듬 돌려놓기 프로젝트 1일차
-
도덕이란 뭘까 2
요즘 고민임
-
안떴다. 해모 시즌 1~4 중에 하나만 추천좀 그냥 멘탈 힐링용으로 파이널은 풂...
-
쌍사특 0
세계사 : 이게 1컷 50이라고? 동아시아사 : 이게 1컷 50이 아니라고?...
-
사문 강k 15 0
사문 강k 15번 어떤방법으로 푸는건가요 풀려고해도 안풀려서요
-
난 만점이다 0
오늘 비록 6시에 뛰쳐나와서 피방롤을 조지긴했지만 수능은 잘볼것이다 반드시.
-
아예 과거버전도 못보게 막아놨네 어휴
-
레어 사고 싶다 2
현재로서 구매가능한 레어는 괴산군 레어뿐.. 괴산군 잘 몰라요.. 안 땡겨요 ㅠ
-
엄청 나중에 돌아와서 몇명만 딱 팔해놔도 누군지 알고 평소엔 커뮤 잘 안하는데 딱...
-
올해 계속 수학 쉽게 내라고 명령 여러번 떨어졌다고... 9평도 그 일환이고
-
1. 관대한 pdf 예전엔 누가 피뎊 쓰다 걸리면 메인글이 그사람 욕으로 도배되고...
-
미헌법중,1조는 정부의 입법부 즉 미국 의회를 정의하고 있다. 여기에는 하원과...
-
내일은 비역학 개념책 조진다
-
카톡으로 용돈 보내주셨는데 수능 끝나고 받는게 맞겠죠? 감사인사는 드렸는데
-
(✷‿✷)
-
수능은 자신감이 2
ㅣ진짜 중요한가보네요… 윤도영쌤도 그렇게 말씀하시고 저희 학원쌤도 똑같이 말씀하시던데
-
이제 미적 전범위 개념학습(미친개념 찍먹하고 예제+연습문제 공책에다 풂) 끝나서...
-
풀수있는문제가 꽤 많았네
-
내년 고3이라 가을때부터 천천히 심맨님 커리 따라갓엇는데 이제 곧 끝나서 커리중에...
-
https://orbi.kr/0009658324/ 전 이거
-
없겠져..?
-
독서지문 (1) 비극과 희극 두 부분으로 되어 있는 듯하지만 희극을 다루었을 자료중...
-
왜 난 느낌상 3
올해 수능이 국어 24독서보다 살짝어렵 24문학보다 쉽 수학 23,22어딘가 영어...
-
저 불닭 사먹게 덕코좀요 ㅈㅂㅈㅂ
-
원래 삼각함수 덧셈정리 문제는 수능에 잘 안 나오나? 7
최근 미적기출들에서 삼각함수 덧셈정리문제는 잘 못 본 거 같은데 그냥 범위가 많은데...
-
젠장잠이안와 1
어떻게 고친 수면패턴인데...어제한번 늦게잤다고 다시 와장창
-
888484 3
훈훈훈호훈호
-
-
평가원스러운 지문 들고가려 했는데 그게 어떤건지 잘 모르겠어요 보통 어떤 지문 들고...
-
이건 사람 글씨가 아니야..
-
남자인게 대놓고 티남 ㅋㅋ
-
1. 이혼 시 부부협의 없이 가정법원이 지정한다 2. 부부 협의로 결정한다 두...
-
글씨 잘ㅆ는데 7
플래너 올려주고싶다
-
찜뱃 얻는 법 10
https://orbi.kr/00010821728 여기 나와있네요
-
작수컷이 47인가.. 괴물들이네 진짜 강민웅쌤은 보통 쉬운회차도 45정도라고 말씀하시던데
-
영어2 진짜 너무 간절함 작수71 6모미응시(논술반수) 9모76 요즘들어서는 하루에...
-
영어 국어 정말 약하기도 하고 학원이 잘 맞아 영어 국어는 계속 다니되 수학은 끊고...
-
김승모 3회 1
애끼다가 풀었는데 독서 문학 너무 술술 풀려서 처음으로 시간 남았음. 그런데 너무...
-
25 9모를 풀로 풀어야겠다
-
현정훈T 인강 1
오늘 현강에서 내년에 어디서 수업 할지 정해진 거 아무것도 없다고 메가대성...
-
그걸 어케 기억하고 어케 쓰는 거야
-
아님 그냥 실모 치고 채점 후 점수 확인만 하시나요 전 독서 문학에서 아아주 골고루...
-
개인사정으로 재수로 붙은 대학을 못 다녔음 (현 21) 재수로 붙은 대학도 그리...
-
그땐 일주일에 국어 실모 3개 이상 풀면 대평가원 논리에 반역을 든 허수취급 받음 지금은 반대인듯
-
숨마국어 이분 아시는분 연계작품 보는데 은근 그림으로 연상잘됨
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김