정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://i9.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를 선물하세요.
-
원서등록전 최초합격권으로 생각하고 경희대를 썼는데 예비8번이 떴습니다,,...
-
20명 뽑는 과인데 예비 4번 받았습니다. 작년엔 18명 모집 13명 추합 재작년엔...
-
이대 논술 추합 0
이화여대 불어불문학과 논술 예비 3번인데 추합 가능성 있나요??
-
한양대 에리카 기계공학과 학종 예비번호 13 떴는데 추합 가능성 있나요.. ?
-
아무리 찾아도 없는데 어디에 나오나요?
-
성대 추합 1
학종 계열모집형 추합부터는 예비번호 안뜨는 합불만 뜨는건가요 ???
-
다군 홍대이고 100번에서 34번까지 옴 전추 가능이냐? 5차에서 5명빠짐.....
-
전찬 뱃지 0
‘전화찬스->안감’이라 합격증은 없는데 합격자 조회 창에 ‘불합격’이 아닌...
-
타대학들도 그렇고 내가 지원한 대학들도 그렇고 유독 2018, 2019, 2020에...
-
자리 하나 났어요
-
빠졌는데 작년에는 1차 몇 명 빠졌나요?ㅠ 저 정도면 많이 빠진건가용...?
-
추합 0
인천대 중어중국학과 예비 10번 받았었는데 1차에서 6명빠져서 지금 4번인데 2차때...
-
한번 더 전화오나요? 아님 다른 가족 폰으로 가나요
-
되신분 중에 빠지는분 있나요? 논술전형이요
-
부산대 추합했는데 수강신청 하려고 들어가니까 자리가 하나씩 밖에 안남았드라고요 근데...
-
전화 돌고 있나유? 내일까지 전화 안오면 마감인건가유
-
시립대 컴과 예비 12
예비번호 6번... 가능할까요?
-
영남대 의대 면접전형 빠지시는 분 있나요 ㅜㅜ 오늘 저녁 9시까진데 빠지실 분 미리...
-
추합발표가 대학마다 약간 다르긴 하지만 비슷비슷하잖아요 만약 제가 A대학에서 추합이...
-
추합 전화 시간 2
보통 추합전화 몇시쯤까지 오나요??
-
연대 전찬 전체적으로 모든 과가 많이 도는편인가요?? 아니면 대부분의 과는 이미...
-
서강대 영미문화 예비1번 합격했어요!!!! 다 여러분들 덕입니다....! 31
우선 댓글, 쪽지를 통해 응원해주신 모든 분들께 감사드립니다...특히 Saint님과...
-
서강대 영미문화 예비1번....이륙 부탁드립니다...간절해요.. 25
서강대 영미문화 예비4번에서 1번이 됐는데요..오늘 될 줄 알았는데...
-
점공에서 확인했는데 한양 행정 예비 5번 = 연대 행정 최초합 추합 엄청날듯; 컹s
-
추합가능? 작년 40명 모집에 65프로 추합돌았었는뎅
-
재업) 연대 최초합이랑 2차 추합 대우 차이 없죠? 10
제가 모종의 이유로 학종 최초합이 아니라 교과 2차 추합으로 등록했는데 손해는...
-
저와 아주 가까운 분이 한양대 학생부종합 전형에서 추가합격을 기다리고 있습니다....
-
동기들 사이에서 장난스럽게 주고가는 이야기가 아니라 학교 차원에서 수시 최초합...
-
한양대 추가합격 6
한양대 추합 9시 발표 아닌가요? 왜 안나오죠ㅠㅠㅠ
-
홍대는 최초합격자 포함해서 나오더라고요 논술 정원16명에 순위18등예비2번인데...
-
나머지는 다 떨어지고 삼수하러 간다고 해서 당구치는데 전화왔네요. 부끄러운줄도...
-
948.63점 입니다. 추합 가능 할까요?.. 중대 떨어지면 강제 삼수라 너무 간절하네요ㅠㅠㅠㅠ
-
제가 예비15 받았는데 4차 추합까지 10명빠졌거든요 8차까지 5명 빠질까요..?
-
최초합한 대학에 등록한 상태에서 추가합격을 했을 경우에1. 추가합격한 대학에...
-
추합에서 3
1차 추합에서 1배수이상은 어떻게 빠지는거죠?? 전부터 ㄹㅇ 궁금해서...
-
숭실대 추합 0
숭실대 가군 경영 예비 30극후반인데 추합될까요?? 추가합격 감이...
-
다군 국어국문이 모집인원 13명이고 전 예비 14번입니다. 작년 같은 경우에는 예비...
-
성대 나군 인문 4
이번에 추합률이 얼마나 될까요?그리고 빠지시는 분 있으면 댓글좀 남겨주세요. 암울합니다. ㅜㅜ
-
나군 인문에서 빠지시는 분 있으신가요??? 제발..그리고 이번년도 추합은 어디까지 돌까요??
-
연세대추합권 7
화생공 예비번호 68번인데 안되겠죠?ㅋㅋ 유니스트붙고 재미로써봤는데, 점수치곤...
-
서강대는 5차추합 이후를 전화로 통보하는게 아니라 입학처에서 발표한다는데 진짠가요?
-
주위에 빠지는 분 있으면 알려주세요.....죽고싶어요
-
논술전형에서 최저등급 못맞춰서 떨어진사람들은 추가합격도 없는거죠?
-
공주교대 변환점수 수능성적:347.19 비교내신:375.09 합:722.28입니다....
-
15명 뽑는 전전컴에서 추합번호가 6번인데 이거 합격할 수 있을까요?이거 떨어지면...
-
정원 33명에 예비8번인데 가능할까요? 그리고 입학처에문의해보니 작년 추합상황이...
-
인하대 기계 나군 33명정원 예비8번 작년 입시문의해보니 가군 1.4 나군 1.2...
-
경희대 추가합격 4
저 지금 영어 학부 후보 7번인데 작년에 34번까지뽑혓던데 가능성잇을까요??
-
경찰대 추합 2
여자 추가합격 작년이나 보통 얼마까지 도는지 아시나요?
-
추합전화 ! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김