정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://www.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를 선물하세요.
-
이번 5모 수학 난이도가 작년 수능 난이도랑 비슷한가요?.. 0
다른 모고 풀었을때 이 점수가 나온적이 없는데.. 이번 모고는 .. ㅠ
-
수능에 이렇게 나왔으면 막말로 3등급 블랭크도 나오는거 아님?
-
노잼이군 2
오르비도 과제도 하기싫다
-
수학 기출 인강 0
지금 n제 이것저것 풀고 잇고 기출 한번 더 하려고하는데 4점 중상위주로 수분감처럼...
-
확통 옛기출에 3
재밋는게 많네... 물론 실전에서 보면 머리가 새하얘질듯한
-
보이스피싱 왜 당하는지 알겠네 스트레스 확 받으니까 몸 확 아프네
-
삼반수 고민.. 1
작수 언미생지 13225였고 건동홍 전화기 중 하나 다니고 있는데...
-
수험생은 운동을 한주에 최소 몇시간 하는 게 좋을까요? 4
일주일에 한번만 해도 ㄱㅊ은가
-
실용적이고 아름다운 다리 건설에 이용되는 포물선' 이라는 주제랑 제 진로를...
-
다들 날 놀리고있어.....
-
6모 예상등급 0
국 4 수 5 영 5 세사 5 세지 5 ㅠㅠ
-
지문을 다시 다 읽어야 하는 게 너무 귀찮음
-
나라별 음식 만들어서 주고 그랬던 거 같은데
-
웨수능이200일도안남은거신.,,
-
6모 목표 2
11213 그저 목표일뿐...
-
대충어느정도 받아야함? 언미물지
-
몇년째 평가원 교육청 문제 계속 풀어보고 있는데 그래도 나름 교육청에서는 재작년까지...
-
현재 중경외시라인 공대 재학중, 2학기 휴학하고 최저준비예정 고대 학우 인공지능...
-
아니어떻게 6
어떻게 저렇게생각을하지 엠비씨라 독자풀이 좀 다른가
-
104세 철학자 김형석의 일침 "지도자의 무지는 나라의 불행" 2
"윤석열 대통령이 리더이기 때문에 어떤 주장을 하면 장관들은 모두 그 주장을...
-
막상 문제 푸니까 3개중에 1개밖에 못맞춤 ㅜㅜㅋㅋ
-
난 ㄱㅏ끔 1
고부 를 한ㄷr… ㅇ
-
6평 대비 공통 모의고사를 배포하려고 하는데 6평 일주일 전으로 잡으면 될까요? 한...
-
국어는 아 진짜 좀만 더 있었으면 이 느낌이면 수학은 아 ㅅㅂ 이걸 어케 100분애...
-
수능이 188일 남았네요 지금 시점에서 과탐 1등급을 노린다고 생각하면 지1은...
-
훈련소 안갔다고 하면 다들 알지 않나요....? ㅠㅠ
-
재밌는거 하고 싶은데 온라인으로 할 방법ㅇ ㅣ 딱히 안 떠오르네요 조작 쌉가능이라.......
-
야구보러왔는데 1
간만에재밌네
-
현우진 커리 1
안녕하세요 고2 통통이 입니다 지금부터 시발점 수1 수2 시작하려는데 시발점 끝내고...
-
수학 5에서 3 0
올해 3모 5모 전부 수학 5 받은 노베입니다 ㅠㅠ 올해 수능 때까지 수학 3으로...
-
의대 가서 뭐 배우는지 궁금해서 해리슨인가? 이거 pdf 보고 싶은데 구할 수...
-
거의 수학때매 재수하는건데ㅠ혼자 공부하고 조언해줄 사람이 없이 하니까 계속 불안해요...
-
쉬바
-
안녕하세요 수학강사 이대은입니다. 오늘은 5/8에 있었던 5월 모의고사에 대한 글을...
-
한화 얘네는 0
롯데한테도 체급차이가 나네
-
재미가 없음
-
피램 문학 질문 1
허용가능성 고려를 통한 선지판단은 정말 정말 마음에 드는데요 작품에 대한 해설은...
-
먹고 있던 참외 뱉을 뻔 했네..
-
저녁의 맞팔구 4
뭔가 사람이 살짝 생긴 느낌이 드네요? 그러니 맞팔구!! 맞팔을 해주세요,,,,,
-
슬금슬금 올라오는 엔수의 기운
-
학원알바퇴근 11
집가서 푹 쉬어야지 근데 요즘 왤케 공허하지
-
사실 풀 줄 몰라서 그냥 어거지로 푼 거…
-
50살, 9급공무원 입직 후 서울 중급지 아파트 1채 보유자를 25살 , 흙수저...
-
꼭 풀어야 되나요? 수학 고정 1 뜨는 친구는 안 풀어도 된다고 하긴 하는데 고민되네요
-
정법 OX 퀴즈 0
라이더
-
한주에 5문제 가능하려나
-
투과목은 교재는 받는데 수행평가 발표자료 만들때만 찾아보고 수업은 원과목 수특으로...
-
4월 더프 72점이었고 5월 모고는 집에서 시간 재고 풀었는데 80점...
-
5모 미적 14 21 22 29 30 틀리고 28찍맞 80임 수1,2는 기출 다...
-
20문제 다 풀었을 떄 타임어택이 있다면 몇분정도 인지.... 20문제 실전처럼...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김