정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
연세의대 교수들 "정부 정책, 자율성 훼손…의사 정체성 위협"(종합) 1
10일 의사들 휴진 속 '의정갈등 심포지엄' 열어 교수·의대생·전공의 등...
-
고대식 내신 1.44 전년도 등수 124/198 Ai 생기부 점수 94.1...
-
현역이고 올오카는 다 끝냌ㅅ었요 매월승리 + 수특kbs 듣고있는데 마더텅으로 기출...
-
앙대 다니는 사람중이 메가 환급 받은 푸앙이 있어?
-
드릴 중고로 사려고 돈보냈는데 사기당한 느낌드네요 수험생상대로 사기는 좀.. 너무 악마같네
-
한번 누를 때마다 5000원씩나가게해야됨 습관적으로 빵빵거리는 xx들
-
野지지 4050 “이·조 사법리스크 문제 안돼”… 정의 중시 2030과 상반[4050 그들은 누구인가] 1
■ 4050 그들은 누구인가 왜곡된 윤리·도덕 의식 심화 지난 4·10 국회의원...
-
21번 반원 추가 안한 상태로 푸는 법 없나요?????
-
한 치 앞도 알 수 없는데 남들보다 몇 년은 늦춰진 상태라 자그만한 실수 하나도...
-
저번 해설 이해가 힘드셨던 분들을 위한 해설 영상입니다 최소한 제 사고가 언어로...
-
기출에 나온 소재 적당히 버무렸다는데 뭘 보면 도움이 될까요???
-
전 현실에서.. 13
두 사진 다 우측이 저랍니다
-
전에도 생각했던 건데 극상위권을 목표로 공부하다 보니까 내가 운동선수 같다는 생각을...
-
잼파파 프사는 좀 그렇고
-
자주쓰긴함 ㅇㅇ게이야 이런건 좀 그래
-
진짜로 개화난다 자리를 바꿔야 하나 새로 와서 뭐라하기도 좀 그런데
-
조건 1. 163cm 2. A형 3.225mm 4. 좌 1.0 오 0.1 부등시
-
이라고 현실에서 일부러 외치지는 않아요 말실수라면 모를까.
-
주간지 따로 안팔고 패키지에 끼워팔지. 작년에는 주간지 묶음 패키지만 따로 있었는데...
-
걍 언매 존버가 답인게 분명한게 문디컬이 꼭 사탐만 받아주는 곳은 거의 없다고...
-
불확실한 미래에 배팅하는 게 진짜 고통인 건데
-
한탕tv 0
-
강평들 모여봐 1
정석민하다가 독서갈아타볼까 하는데 강기분 안하고 새기분 부터해도됨?
-
너나 하라고 시발
-
유튜브 보니까 cpa 9수만에 2차 합격 35세? 형님 합격영상 후기있던데 이걸...
-
수시할걸.... 4
아...
-
개념 공부를 3주 정도 안하고 시험봐서 개념을 흔들린 것 같습니다. 당장은 국수생에...
-
원서 뭐 쓸지 고민하다 서울대라는 이름만 들으면 막 가슴이 웅장해짐.. 낭만...
-
고3이지..
-
자료해석, 얕은추론형?에 가깝다고 판단하고 틀리면 틀린대로 어케해야 답인지 정오판단...
-
닉네임 원하는걸로 바꾸겠습니다 선착 댓 5명 거기서 룰렛 돌려서 할게요
-
이제 음해를 멈춰주세요.
-
모든 항이 자연수일 수밖에 없는 수열임을 파악하고 1,4. 2,3. 3,2....
-
아. ... 언어스트레스 화작 마렵다
-
종강하고 가려다가 걍 맘 바뀌어서 지금 가려는디 지금 들어갈 수 있나요? 지금가면...
-
입결 괜찮은 일반고 국영수사과 1.19 국영수과 1.21 전교과 1.28 학교내에서...
-
3일 뒤 평양 (니나님) 으로 갈 예정인데 심심하니 평양 다음에 갈 행선지를 미리...
-
일주일 내로 완성해서 올릴 예정 해강 반응이 좋으면 자작 모의고사도 배포하겠습니다
-
콧물감기 ㄹㅇ
-
덕코 주세요 ㅈㅂ.... ㅠㅠ 덕코를 받고 싶은 밤이네요.........
-
아오 열역학시치 0
탈모오겠다
-
목동시대 - 수업료 70% 장학 충족 - 수업료 30%+급식+독서실+컨텐츠비 = 월...
-
어지럽네
-
정답이 4번이라는데 선지의 앞부분 녹운이 ㄱ을하고 난후 위연청에게한말 =(글을지어...
-
많이 어려워 질지도.... 최대한 다운시켜봄...
-
분명 뉴비였는데!
-
썸네일 어그로 14
30시간연속작업은 에바긴한듯 대가리깨질것같네
-
비내린다 비내려
-
'라인'만 뺏기는게 아냐…페이, 포털, 쇼핑몰까지 날아간다 1
네이버가 13년 공들여 키운 메신저앱 라인 경영권이 일본에 위협받고 있는 가운데,...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김