정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
국영수 111은 첨받아보긴 한데 과탐도 첨 보는 등급나왔네 물리랑 지구랑 10점...
-
아는 동생이 고1인데 식 전개나 이항 이차함수 꼴 변형 이런것도 버벅거리고 막히는...
-
빡모 이게맞음? 4
빡모 보면 보통 76~80인데 6,9평 각각 2,1뜸 오르비 다른글 보면 3등급이...
-
사회 계약은 정치제에 그 단체의 전 구성원을 지배할 절대적 권력을 부여한다 이거...
-
다들 경제지문 엄청 푸네요
-
똥글을 싫어하는거 같은데 똥글을 두 번이나 메인보내는걸 보면.... 사실...
-
뭐냐... 10월 중순에 qcc 정산부터 들어올거 많긴 하네
-
서바 13 0
22 풀수있을거 같은데 답안나와서 빡침 15 22 30 틀… 컷개높겠지
-
미적 29 30 틀 공통 6 9 12 14 15 21 22 틀 6번 안풀리는데 뭐지...
-
수학 무보정에서 오를까요..?
-
저딴 거 안 써도 충분히 변별력 있는 문제들 만들 수 있을텐데 그냥 문제 딸깍딸깍...
-
서시대 논술 3-a 에서 답 약분 잘못해서 틀림 얼마 깎임
-
보통 기출에서 갖고오나?
-
1/4부터 1까지 적분때린게 1 1/8부터 1/2까지 적분때린게 1/2 1/16부터...
-
체감상 6모 개씹어먹는데? ㅋㅋㅋ
-
도표 처음하는데 마더텅 기출풀고 해설지 보는걸로 충분할까요? 아니면 임정환 도표...
-
구체제 마지막 수능 + 개정 교육과정 첫 수능 환장의 조합 단년체제라 예비시행도...
-
미용실에서 자 버릴 듯요
-
넉넉잡아도 5달밖에 안남았단게 슬퍼서 울었어 ㅜㅜ
-
옆집동생 조용한애인줄알았는데 샤워하면서 뭔 노래를씨부랄 워어어어어~~!!...
-
한국가수 중 보카로일본노래풍 작곡가인데 반갑네요 보카로 한국어버젼이 노추에 나오는...
-
이 문제 있잖아요 수특 수1 51p 레벨3 4번 전 그냥 이렇게 그래프 추론해서...
-
그 말이 옳을까?
-
감격의 눙물.. 0
태어나서 처음으로 사설 29번 맞췄.. 문해전에서 이거랑 비슷한 아이디어 쓰는 훨씬...
-
시립대 홍대논술은 언급이 별로없네
-
조려 vs 가천 2
어디가 나음
-
어디가 나음
-
논술시즌이구나 0
현역때 수능 개조지고 5개 야무지게 갔던거 기억나네
-
84점 12, 15, 21, 22 틀 그냥 썰렸음 ㅎ.. 11번까지 무난 12번...
-
이번 9모 보고 물1 진지하게 후회됨
-
고일수가 없는 이유가 따로 있나요
-
아니 이거 a 상수인데도 성립하는거임? ㅠㅠ
-
저는 지구 지엽을 돌아보거나 오답노트를 보거나 한국사를 하거나 합니다 공부하기 싫을...
-
기계과썼고 답 맞춰봐서 아는데 정확히 4개틀렸음 기계과썼는데 합격가능성 있을까요ㅠㅠ
-
너무 슬프다 2
왤케 글이 튕기지 글을 읽었는데 기억이 잘 안남 ㅠㅠ 머리가 멍해
-
언확사사 백분위 98/99/2/96/96 붙나요..?
-
학기 중 꿀알바 과외. 이제는 잡을 수 있습니다. 한창 중간고사 중이거나 끝나는...
-
ㅋㅋㅋ
-
문학 왜이럼
-
강아지보고싶어 0
본가에 있는 강아지보고싶어서 미치겟슴 강쥐 맡기고 한 1주일정도는 아무렇지도 않다가...
-
아수라 리트지문 1
아수라 총정리과제에 수록되어있는 리트엠디트 독서 지문들 ebs 소재랑 연관된 지문들인가요?
-
ㄷ 선지가 맞는 이유가 나가 방출에너지양과 질량 둘다 다보다 높지만 방출에너지양이...
-
부분으로서의 전체
-
교육청문제중 ㅅㅌㅊ인거같음
-
본인 썰 4
전에 뉴스에서 확통하고 미적 표점차가 10점 넘는다는 내용이 나와서 엄마가 "확통...
-
김현우 시즌1 0
김현우쌤 겨울 커리 난이도 많이 높나요... 내신 때문에 퐁당퐁당 공부 해서 기출...
-
사문은 답지가 없음요?? 생윤은 어직 안 뜯었고 사문1회만 풀었는데 봉투에 답지가 안 보이네
-
뒤로 가면 챕터당 4점문제만 20문제 이상인데 한시간 안에 가능한가요…? 기본...
-
군수중인데 진짜 오랜만에 강k영어 구해서 풀어봤는데 너무어렵내요 그래도 현역때 거의...
-
롤스가 빈국을 원조할때 부권주의적 간섭은 허용x 다만 인권을 강조하는거ㆍ 괜찮다고...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김