정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://i.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를 선물하세요.
-
다 모르겠고 나보다 세보이는여자 ㅈㄴ 많은데 걔낸좀 델고 가면 안됨? 국가적 낭비...
-
못해먹겠음 그냥. 모의고사 공부는 재밌고, 무엇보다 근거가 명확함. 억울하지도...
-
9덮 성적표 0
인증코든거 뭐시기 있어야 하는거? 아 기숙와서 다를탠데 원래랑 시발 ㅜ
-
전우애 실시!!!!!!! 이 짤 나만 생각남?
-
엉엉
-
강x등급컷 1
예상등급컷 뜨는거 보정인가요 무보정인가요?
-
오늘 성적표받았는데 당연히 3인줄 알고 봤더니 4찍혀있네요
-
9덮 석차 0
석차낼때 표점으로하나요?? 원점수로 하나요??
-
내년 커리 0
수학 기초는 세젤쉬(이미지) 나머지는 배성민 커리 타고 국어는 유대종(언매) 풀커...
-
화학내신 개쉬우ㅏㅆ는데 나 맨마지막문제 5.1점따리 부피잘못봐서...
-
죄송합니다 3
안녕하세요 저는 오르비에서 어그로를 끌고있는 오르비언 오공입니다. 먼저 저의 말과...
-
ㅈㄱㄴ
-
그것이 초등논리라 해도..
-
시즌1이랑 비교불가,,,ㅇㅁㅇ 압도당한적 서바 이후로 처음
-
궁극의 증명 0
-
까진 아니지만 좀 늙으셨습니다
-
문학 기출분석 X 선지허용 X 문풀 루틴화 X 문제먼저X 보기먼저X only...
-
2025 킬링캠프 시즌2 1회 리뷰 큐브 질문 와서 시즌1 다 풀지도 않았는데 먼저...
-
공부합시다 0
유지민입니다
-
하..
-
학벌... 7
옯하하
-
누구라고 얘기는 안 하겠지만 본인이 선택해서 안 간 길이라면 굳이 까내릴 필요도...
-
설거지 알바 대학생활 때 1학기동안 학식 설거지 알바했는데 엄지 검지로 식기 계속...
-
없으면 왜 이나이 쳐먹고 수능준비함ㅋㅋ
-
두시간내내 사방에서 훌쩍킁킁우웩취대는데 쉬는시간에도 코 절대안풀고 마스크는 아뮤도안씀진짜존나싫어하
-
1컷 50이네 ㅋㅋ
-
사회성 기르기에 적합한 알바 뭐뭐 있나요?시급 짜도 상관없는데 추천가능할까요..ㅠㅠ
-
서술형에 일기기호 그리는게 나왔는데 온도랑 기압 적을때 원래는 단위를 안적는 다고...
-
밀리진않겠지
-
내가 중1로 돌아갈수있다면 공부말고 헬스부터 시작할거임 뇌는 어른이되도...
-
박선 300제 하신분 전체 볼륨 궁금해요 +천체쪽 계산문제 0
천체 공식은 다아는데 문제만 만나면 버버벅 거려서 연습 많이 하고싶거든요 300제...
-
내 이름은 코난 3
미래소년이죠
-
2025학년도 정시 전형 - 광운대, 명지대, 상명대, 가톨릭대 1
안녕하세요 나무아카데미입니다! 어느덧 수능이 두 달도 채 안 남은 가을이 왔습니다....
-
좀 논점에서 벗어난 말임 모든거 다 집어던지고 오로지 학벌만을 위해 주변사람 연락...
-
그냥 조언을 하지 말자^^ 각자 알아서 잘 살자. 가족끼리도 삼가자^^
-
...
-
기출을 풀면서 중요한 것이 애매함을 없애는 과정이라고 생각합니다. 단순히 이럴 것...
-
빨리 좀 싸줘 0
뻘글 싸줘
-
ㄷ ㄷ
-
이게 최상위권 입시 커뮤니티의 현실이라니...
-
6시 수업이라 5시 쯤 혼밥하고 빨리 들어가려 하는데 정자역 근처 식당들 그...
-
지금 어지러움...
-
사관학교 문학이랑 실모 중에 평가원 문학과 괴리가 덜 한 건 뭘까요?? 적당히 익힌...
-
예 수고하시고
-
그냥 개념어 인강 하나듣고 기출풀면 되나요,,독서는 공부 어케해야할지 알겠는데 얘는 감도 안잡힘,,
-
-늦은 반수를 시작해서 이제 기출 2회독 다 끝나가는데요 딱 2컷 목표인데 기출...
-
ㅠㅠ 여태까지 의뱃 달고 똥글 싼 게 얼마인데 ㅠ
-
풀긴는했는데이계산이 안돼서 답지를 보니까 k=t+α해서 α 상수고 바로 미분하는 건...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김