정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://wwww.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를 선물하세요.
-
벌써피곤한데 이거뭐임..
-
안녕하세요. 2025 혜윰 모의고사 시즌1 정오표를 업로드합니다. 추가 정오 사항이...
-
다들 자니? 2
형 심심한데 유튜브 몰아보기 채널 추천 좀 해달라고 ㅅㅂ
-
그래서 경쟁자 제거에 들어간다
-
수능망침어차피 0
가짜에 유의하세요.
-
뭔가 익숙해서 봤더니 신기하다
-
오늘의 썰 2
한강에서 지인 만나서 놀고 또 늦게까지 놀다가 파하고 9호선 탔는데 술 취하면...
-
시바 뭔 10만원이 넘냐
-
텔그 진짜 뭐지 0
만점자들 대거 인설의 이상 빨간불 물1 했으면 가차없이 1% 입갤 아무리 시험이...
-
존내많네
-
갠적으로 생명은 0
방대한 양과 암기투성이 과목으로 시험진행하는게 맞다고 봄... 물론 논리를 요구하는...
-
너의 이름은, 너에게 닿기를 같은 느낌이요 순정 아련 로맨스
-
그걸 한 시험지에 냈다고..? 등골이 오싹해짐
-
김기철t 커리 탄 사람입니다. 조정식t tdyd가 평가원느낌 난다고 해서 풀...
-
ㄹㅇ 4시간동안 30문제 간당간당하게 푸는듯…
-
깊은 밤 하늘에 빛이 되어 노래할거야 날아올라 봉하산 가득 안고 싶어요 이렇게 멋진...
-
이유가 멀까
-
기출 다 끝내고 실모 들어가려고 하는데 임정환t 하트 모의고사랑 윤성훈t...
-
겪어보신적 있나요 .. 지금 제 상황인데 15년 키운 반려묘가 무지개 다리를...
-
생각해보니까 여기 아니면 불안함을 해소할 수 있는 장소가 마땅히 없다는 것을...
-
드릴 설맞이 품 인강컨 희망
-
자고 일어낫는데 1
무슨 아무일도 없엇던것처럼 기분 조아짐 ㅎㅎ
-
이타다키마~~~쓰!!
-
전 이형기 낙화 첫소절부터 문장 하나하나가 너무 이쁜듯
-
음악은좋네 7
언젠간풀콤할수잇을까
-
우는 모습도이쁨 7
-
지역: 서울시, 과천시, 성남시 과목: 수학 (미적, 확통), 물리학1 - 2022...
-
고1인데 영어 미니모의고사좀 추천해주세요..!
-
새벽TMI 주의) 내가 과몰입하면서 재밋게 본 웹툰 23
아메리카노 엑소더스, 천년구미호, 쿠베라, 이영싫, 소녀더와일즈, 갓오하, 전독시...
-
수학문제 1
요문제 어떻게 시작해야 할지를 모르겟네용 X에 0이랑 1만 넣어봤고 다음을 모르겟어용
-
물1풀어본사람난이도어느정도임?계속30점대나와서개빡침ㄹㅇ시간안에못풀겠다곡.하수능때도시간부족하면우짬
-
수능까지 어삼쉬사랑 수능기출3점만 달달히 복습하고 외우면 수능때 몇 뜨나요?? 저...
-
수학: 파데+킥오프로 개념 완벽하게 해놓기문학: 강기본 문학 수강비문학: 수국김...
-
국어 만점 아니라 죄송... 근데 충분히 보기 정도 줄 만한 문제 아니었냐? 보통...
-
물리 실모 추천 좀 해주실수있나욥 대성마이맥 캐쉬가 8만원 정도 남아서 그걸로...
-
오늘 자신감 바닥이네요
-
임의의양수입실론에대해그에종속되는델타가항상존재하므로참 QED
-
작년의 저처럼 간절한분들이 많이보이네요 꼭 후배로 만납시다
-
내가 가는 길이 곧 정답이다 개가 짖어도 기차는 달린다 Show and Prove...
-
저는 가문비나무 이 사진에 보이는 나무들이 전부 다 가문비나무임 크리스마스 트리도 가문비나무..
-
회계학과나 경영학과에서 수능 수학이 필요한가요??
-
연락와라
-
요즘 네웹 많이 안보네 18
옛날엔 진짜 많이 봤었는데 재밌던거 다 완결하고 내가 새로운 시도를 잘 안하는...
-
두 시즌만 사보려는데 ,, 2 4 사는거 어떨까요
-
식 깔끔하게 쓰고 조건 체크하고 이런거 중요함? 수학 잘하는 친구들은 그냥...
-
..
-
주희지문 이거 뭐냐 ㅅㅂ 글읽는데 진짜 이해 존나안되네 근데 신기한게 문제는 또 쉽게풀림..
-
수능날 화장실 4
수능날 화장실에가서 수능을 망치는것보단 차라리 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김