정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://ys.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를 선물하세요.
-
물리는 한과목 고정하고 지구 vs 사탐 하면
-
기아 1.6배 ㄷ lg 2배 Kt 2.4배 ㄷ ssg 1.4배 롯데 1.9배 ㄷ...
-
Plz!!!
-
기출 다 풀었습니다
-
작수 27 28 29 30 못 풂.. 시간 말고 실력부족 현재 미적분 쎈 끝났어요...
-
어려울려나용
-
6모 이전까지 뭘 먼저하는 게 좋을까여… 통기출 안 하고 수분감 한완기만 해서...
-
오타니가 이승엽보다 대단하다 하니까 싸우네ㅋㅋㅋㅋ
-
고민상담소 오픈 18
수탐 재종 학습 대학 뻘소리 등등… 아무거나 받습니다 댓 ㄱㄱ
-
. 0
그나저나 머리가 왜 안 길지 그야 자르니까.. ㅎㅎ 근데 안 자르면 신경쓰인다구염...
-
국어 안정 1~2 뜨시는 분 중에 문제 이렇게 푸시는 분 계신가요 14
인문지문 사회지문은 이 정도로 더럽게 풀진 않는데 과학기술지문은 정말 이렇게 풉니다...
-
안티프라자 0
거짓으로가득찬어쩌구
-
현역 고3 화생러인데 화학은 꽤 적성에 맞는거 같은데 유전 심각하게 못해서 2등급...
-
내가 나중에 밥 사줄게 ㅠㅠ 기분 나빠하진 않겠지??
-
투표) 벨런스 게임! 17
인서울에 미쳐있는 우리 오비르 여러분들의 인식이 궁금하여. 다음과 같은 벨런스...
-
실전 개념은 대충 할 지 몰라도 기출 분석 완벽하게 하고 n제 넘어가요? 아니면...
-
지문읽고 문제는 그래도 다 맞추는데 므ㅓㄴ가 좀 애매한 느낌 뭔지 알지? 이럴때는...
-
. 0
근데 산책 중인데 날씨가 많이 더워져써.. 허허 일광욕 중..
-
고딩 때 놀아본 애들이 더 잘 노는 듯 고딩 때 공부만 주구장창 하면서 사회와...
-
암살 교실 카르마랑 아사노가 싸운 그 문제 체심 입방 면체가 뭔지는 왜 화2에서야...
-
갠적으로 개적폐전형이라 생각함
-
https://tjukanovt.github.io/notable-people...
-
수능수학 기출분석에도 도움되고 N제와 유사한 감각을 기르는데도 도움되는듯 (범준쌤...
-
작수기준 언매 미적 영어 물1 지1 순서로 94 92점인99 1 96 97...
-
한국이 끝인 거 같기도
-
경제를 내신으로 해봐서 그런지 브레턴우즈는 이해는 가는데 pcr, 키트지문 이런건...
-
찍맞 다 빼면 수학 작수 56점 4등급 3월 학평 73점 2등급 그냥 난이도...
-
뉴턴 운동법칙 3가지 쓰시오 역학적에너지보존법칙 쓰시오 보통 응용문제를 내기...
-
쎈B문제 0
고3인데 쎈B 첫문제랑 마지막문제(+난이도 상) 만 풀고 넘어가도 될까요..? 3모...
-
독해력 좋아짐 인강보다 줄글이 좋고 편해짐..
-
시범과외 후기 14
특성화고라 교과서 수업 받는다 입갤 개꿀이긴함 제발 한다고해라
-
기함수 질문이용 1
기함수 2개 원점 제외 2점에서 만나면 원점 무조건 중점인가용
-
누가 제 전글에 대한 반박 부탁드려요 저도 저 상황을 틀렸다고 보고싶은데 저는...
-
너드학개론 이거 보다가 중간에 꺼버림 하... 사실적시명예훼손아님 어떻게 이렇게...
-
제가 공부 하다보니 약점 몇개를 파악했는데요 우선 1. 수학 - 중학도형과 고1...
-
확통 0
확통 마더텅 수특 n티켓 풀었는데 n티켓 정답률 71%나왔어요. 그냥 너기출같은...
-
구글 검색에도 안뜨게 하는 법은 없나요??
-
앱키스마 2
앱스키마 구매했는데 아직 교재신청은 안되는건가요?
-
아미노산
-
1인실 아니고 남들 뭐하는지 다보이는 개방형이고 삼색볼펜 딸깍거리는것도 소음으로...
-
18수능 0
가형 88점 왜이리많음ㅋㅋㅋ 예전 성적인증글중에 건대부터 의대라인까지 수학은 표점...
-
'4천만원 벌었네'…까르띠에 다이아 귀걸이 2만원에 산 남성 2
멕시코 남성이 고가 브랜드 까르띠에 정품 귀걸이를 정가의 1000분의 1 가격으로...
-
[오늘의 독해7] LET ENGLISH BE ENGLISH 0
오르비 학생분들 안녕하세요:) 저 개인적으로는 수능영어를 가르침에 있어서 보다는...
-
하 고민
-
하나로 베고 0
다른 하나로 봉인하리
-
의대 증원 2000명은 무슨 1000명 확정이어도 예과생들 절대로 안돌아갈 거라는데...
-
개같이 2뜨고 개빡세게 하는중
-
공부를 안하다가 시작해서 3모 성적 52656 나왔습니다 수학은 해놨어서 그나마...
-
1. 만약 한완수를 메인커리로 삼으면 현우진T 커리 기준 어떤 인강을 듣나요?...
-
매체 다맞고 언어 두개틀림 저때 언매 시작한지 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김