정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://i.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를 선물하세요.
-
안녕하세요! 영계입니다! 오늘은 판단력 비판을 읽다가 한 단락을 문제화 했습니다!...
-
잇올주변 gs는 실패
-
작수 연고 낮공점수였음 정확히 기억은 안나는데 국수 백분위 96 98 영어 2 탐구...
-
물리 처음할 때는 역학도 퍼즐인 줄 알았는데 조금씩 깨우치다보니 역학이야말로 진정한...
-
1. 아 아는건데 2. 왜 안되지? 3. 이게 뭔 소리지?
-
韓 언론자유지수 '양호'→ '문제 있음'… 1년 새 15단계 하락, 이유는? 1
한국의 언론 자유가 지난해보다 악화됐다는 평가가 나왔다. 국경없는기자회(RSF)는...
-
매장 안을 가득 채우는 씹덕브금에 알바분이랑 눈 마주쳤어요오.. 이제 저 지점은 못가요
-
지금 기시감 다 끝나고 림잇 복습도 끝나서 이제 실개완 아니면 킬쿼모 풀려는데 둘...
-
ㅇㅈ 8
룸카페에서...
-
서울대에서 1~2점이 당락을 결정하기 때문에 (자기 입으로 말함 그걸 자기들도...
-
기출에 보면 정답률 40% 아래 제외하면 앵간치 기출 풀리는 정도 딱 베이스만 있는...
-
옛날 18살 하얗고 말랐을때 학원에 여자애들이 힐끗힐끗 쳐다보는애들이 종종 있었는데...
-
블아빵 선반 한칸이 통채로 털려있다
-
식비 한달50이상 실화냐
-
솔텍하는 사람 0
나만 오늘 2단원 n제 끝냈나.... 좀 느린듯
-
얼음 쌓기 ㅇㅈ 5
쌓느라 힘들었어요 이 글을 쓰는 와중에도 한숨좌는 한숨을 쉬고있음
-
적절히 조합해서 단어를 만들면 무엇일까요? 1. 사람이름 2. 농기구이름...
-
작수 4등급 선택이랑 문학풀면 한 25분남음 (모고는 3~4등급정도) 문학...
-
먹구 수학 2차전간다
-
느그들이 내 욕을 쳐 하던 내려치길하던 딸이나 쳐라 ㅋㅋ
-
어려운 문제들은 준킬러정도 되나요? 선택 미적 푸는데 꽤 어렵네요.
-
3단원 시민불복종 4단원 전체 6단원 해외원조론 못 건드렸는데 수특이라도 풀면서...
-
3분마다 한숨 쉬면서 10분에 한번씩 하... 진짜... 이러고 이제 다리도 떠는데...
-
뭐하냐? 못하는 말이 없어
-
공통 26분 걸렸고 잘했으면 45분 안에 풀 수도 있었을거같은데.. 29번 안...
-
96 98 2 1 96 90 언매 미적 사문 지구
-
다른 학원들도 그런건가... 그렇게 되면 학교에서 단체 응시하는 일부 현역들...
-
아니 지금까지 다섯번정도는 해봤는데 싹다 거의 꼴등상이거나 꼴등에서 살짝 위임ㅋㅋㅋㅋ 돈 아까워
-
지방러라 첨타보는데, ㄹㅇ 기분좋네 뭔가 미래 기차 타는느낌이고 ㅎㅎ 근데 방금...
-
3모 89 2등급, 평가원도 보통 풀면 2등급 중간뜸 T339 + 문해원 했고,...
-
으앙 피곤해애애애앵
-
갑자기 생각난건데 한 4일전에 백신맞았는데 아프면 타이레놀먹으라고 의느님이 그러셔서...
-
예정은 YES인데 아직은 NO
-
개 무섭네
-
독서실에 딸딸이 빌런 18
열람실에서 같이 1인실 쓰고있는데 시간만 되면 불끄고...
-
애니프사 카르텔생김‼️ 제가 선장임
-
하이콩 1
방긋로아콘
-
2026 대학 입시 요강을 대학에서 바꿀 수도 있음 ? 1
지금 발표한 입시요강에선 서강대는 26년도에 내신 안본다고 했고 정시에서 성대도...
-
정부 "소수지만 전공의가 돌아오고 있다…최근 이틀새 20명 복귀" 3
(서울=뉴스1) 천선휴 기자 = 의대증원에 반발해 사직한 전공의들이 최근 매우...
-
집으로오~
-
"서북 지방의 여자들은 매우 건강하고 민첩하니, 이들에게 포를 쏘는 연습을...
-
쪽지를 두개나 썼는데 안들어쳐먹으니 그냥 제가 버즈를 끼겠읍니다
-
매문독언
-
약간 귀납법으로 찾아낸 치료법이랄까 동상 다한증 심지어 임신한약도 뭔가 한약이 정말...
-
기본적으로 열이 많아서 대부분의 한약재료하고 안맞고 웬만하면 다 먹고 위아프고...
-
신택스 작년 교재 사용해도 괜찮을까요?? 별차이 없을려나용 ??ㅠㅠ
-
이번주 수업에서 뭐하나요? 수업 시작 전까지 풀어야되는 거 있나요?
-
안녕하세요! 오늘로 단대부고까지해서 학생들의 내신이 완료되어 다시 수특영어...
-
우리 엄마가 몇달전에 온몸에 두드러기 났었는데 일반병원 몇군데 다녀도 안낫던게...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김