정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
맑스주의 기반이라거나 글쓴이가 화를 낸다거나 가르치려는 투로 말하는 책이면 읽다가도...
-
갈래나 제재로 나누어서 몇분 컷에 끊어야 한다 이런 강박은 도움 1도 안되는 듯...
-
우파쪽이 강세네 반대가 워낙 뻘짓을 많이했
-
수학 문제 데일리 형식으로 풀만한 책 없을까요?
-
원 안 봤는데 봐도 무방?
-
먹은 거라곤 설렁탕 국물 5숟가락 타코야끼 2알 라면 1개 친구들이 억지로라도...
-
사람을 피곤하게만드려고 작정을했나
-
맛점 0
밥먹으러 갈게요 봉구스다
-
천만덕 가쥬아
-
진짜 하나도 없네. 구버전은 있는데 개정버전은 어째 인터넷에 안보이냐.
-
내신 시즌만 되면 이의제기글 장난아니게 보임 ㅋㅋㅋㅋ
-
개념1회독 하고 모의고사 풀어봤는데 18 19 20 21 3월 다 2등급 나왔어요....
-
가이 센세!! 지켜보고 계십니까!! 이게 바로 당신이 언급한 >입니다!! C-FOOT!!!!!!
-
님들 학교에서 채점한 점수랑 평가원에서 채점한 점수가 다를 수 있음? 0
성적표엔 백분위 94 표점 132 찍혀있음 (78점) 아래 사진은 학교에서 보여준...
-
좋아하던 수학마저도 하기 싫음
-
( 의평원장 2~3년내 의대 증원 불가 인터뷰?! , 의대증원 인증 탈락 여부 변수-->서남대 전철? ) 1
https://www.newsis.com/view/NISX20240704_0002799415
-
모의고사 신청 늦어서 성적표 안나오게 시험친다고 해도 안된다시네 그래 이게 공무원이지 아..
-
독학으로 국어하고있는데 슬슬 ebs 하려 합니다 너무 헤비하진 않은 선에서 재밌는...
-
아 1
수시 폭망
-
어제 올린 문제 풀이 10
미안하게 됐다…실제로 존재하지도 않는 삼각형 가지고 이상한 문제 풀게 해서…게다가...
-
시청역 사고 현장에 ‘토마토 된…’ 조롱 쪽지 남긴 20대 남성 자수 3
‘서울 시청역 역주행 사고’를 추모하는 공간에 “토마토 주스가 돼 버린 (희생)자...
-
평가원하고 다른느낌들어요 정보량만 때려박고 연결성이 없는 느낌이에요 허수라서 걍...
-
뉴스글 올리면 2
잡담태그 차단해도 알림에 뜨나요? 뜨면 안쓰려고 하는데...
-
13분정도 걸리고 한두개틀려요
-
74뜨고 멘탈 갈림
-
수능국어 기준 정답률 몇퍼쯤 됨?
-
“의사 늘린다고 응급실 뺑뺑이 안 없어져… 수가 현실화가 최우선” 1
[의대 증원 갈등] 김인병 대한응급의학회 이사장 김인병 대한응급의학회...
-
문학.. 그냥 기괴하다라는 말이 가장 잘 어울리는
-
밀려드는 경증환자, 멱살 잡힌 전공의… 응급실이 앓고 있다 1
[의료개혁, 이제부터가 중요] [8] 응급실 고질병 지난 2일 오후 4시 서울...
-
레전드 공하싫 2
공부하기 싫어ㅜ미치겠네
-
설경 경한 0
경한 반영비가 특이해서국잘(백분위 98이상)수망(1컷-높2)탐구만점(정법 사문)이면...
-
정도 난이도 n제추천해주새요…plz 대성패스잇숨댜
-
관리 상태 ㅆㅅㅌㅊ네 ㅋㅋ
-
개념강의만 150개는 버겁네..
-
아웃풋은 광운대로 아는데 맞나..?
-
제가 아직 ebs를 극초반 몇 작품만 봐가지고 잘 모르는데 그 중 하나가 시험지에...
-
글 좀 잘 읽자 0
수식된 정으ㅣ 사례 원리 연결 차이점 비교
-
2달동안 달려야지
-
하 하필 이런시험에 걸리냐 가나 한개 날렸는데 가나 쉬웠음?
-
몇시가 마지노선?
-
2학기 내신과목은 생1해놨는데 정시돌리고 사탐런 해서 생윤 사문 개념 한 바퀴씩...
-
수능특강 영어는 수능영어랑 비교할때 난도가 어떤가요??? 4
비슷한가요??? 아니면 수특이 많이 쉬운가요???
-
고신대 의대 인식이 어느정도인가요?
-
7덮국어 11
나만 ㅈㄴ어려웠나.. 언매 첫장도 ㅈㄴ 어렵고 문학도어렵고..
-
최근에 분 국어 시험중 가장 어려웠던것 같은데.... 쉬어갈 지문이 안보였움
-
오늘 늦잠 자버림 지금 일어닜네 밥 먹고 얼른 가서 공부해여지 오늘 더프 보시던데 잘들 보세여
-
전부 문제에서 처막힘 ㅅㅂ 분명 읽을땐 쉬웠는데
-
ㄹㅇ
-
수능 국어를 피지컬로 2등급 맞는다면 1등급이 되기 위해 뭐가 필요할까요? 2
어릴 때부터 독서를 많이 해서 기본적인 국어 공부와 기본적인 문법 지식만으로도수능...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김