정보) 컴퓨터공학과 과목 맛보기 - 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) 김민지 기자 = 서울 강남역 인근 건물 옥상에서 자신의 여자친구를...
-
중3때 미술쌤 되게 친절하고 유쾌한 분인 줄 알았는데 저 졸업하고 다음해에 아내...
-
Q. 여자친구가 헤어지자고 했을때 당신의 선택은? 1.그냥 쿨하게 받아들이고 새...
-
"이 건물인줄 몰랐어요" 시민들 깜짝…의대생 살인 강남빌딩 가보니 1
"가세요. 저희도 힘들어요. 우리도 피해자예요." 8일 서울 서초구 서초동...
-
(서울=뉴스1) 김민지 기자 = 서울 강남역 인근 건물 옥상에서 자신의 여자친구를...
-
왜 정당화되는 거지 범주화 다르게 해서 "역시 한남은 데이트 폭력이 일상이노"...
-
"실습때 XX짓…사람 취급 못받아" 여친 살해 의대생 신상 털렸다 1
서울 강남에서 여자친구를 살해한 의대생 A씨(25)의 신상정보가 빠르게 확산하고...
-
미분법 킬러 두개 푸니까 50분 지나노 하아아 내 지능의 한계인가 뭔가 오래걸리니까...
-
오르비언들 단체로 뒷목잡게 하고 싶은데 올리시는 사진 보니 아직 오피셜로 뜬 건 아닌 듯 해서요
-
오늘을 기억하자 1
다음엔 사설찍맞뽀록이 아닌…
-
[단독] 범죄자 신상공개 '디지털교도소' 부활... 새 운영자 "검증 철저히 할 것" 6
"한국은 악성범죄자에게 관대한 처벌을 내리는 등 사법시스템이 정상 작동하고 있지...
-
풀어보긴 했는데 맞을런지는 의문
-
저도 제가 수능날 국어 말아먹을 줄 몰랐습니다 4월 6월 10월에 국어 100점...
-
같은 상황에서도, 충분히 욕 안먹을 수 있는 상황에서 국민들 깜짝 놀래키는 말만...
-
엄
-
'기수열외', '휴학불참' 이런거 쓰는거 자체가 의대 이미지 먹칠임 5
진짜 경악스럽다
-
해보지도 않고 올려치기 너무 심한듯
-
치대 못가겠다 2
수학 실력 개퇴화함
-
걍 거기출신일 뿐인데
-
조심
-
그냥 가해자 나쁜놈이다 욕해도 충분한데 '기수열외' '휴학불참' 이런거 언급을 굳이...
-
[정오뉴스] ◀ 앵커 ▶ 서울 강남 한복판에서 의대 재학 중인 남성이 여성을 흉기로...
-
3000부 판매신화 기록 지구과학 핵심모음집을 소개합니다. (현재 오르비전자책...
-
여친살해 의대생까지 100명 신상공개…디지털교도소 다시 문 열었다 1
범죄 혐의자 신상을 무단으로 공개하는 웹사이트 '디지털교도소'가 다시 등장해 논란이...
-
https://naver.me/xTbtzHPj 전공의 집단 사직에 따른 의료...
-
'수능 만점' 의대생 살해 사건 피해자 유족 "억울한 계획 범죄" 1
서울 서초구 한 건물 옥상에서 서울 소재 한 의과대에 재학 중인 것으로 알려진...
-
[단독] '여친 살해' 의대생 “2020년 성적 이유 유급… 집단휴학 참여 않고 최근까지 학교 다녀” 2
서울 강남역 인근 건물 옥상에서 여자 친구를 살해한 명문대 의대생 A씨가 재학 중...
-
폰 바꾸면서 0
사진첩이랑 파일에서 오르비와 커뮤의 흔적을 전부 삭제함..
-
이번수능 목표 3
에피눈알 장착하기
-
생각 0
결과를 책임질 수있다면, 과정에서 그 누구의 간섭도 받지않겠다.
-
06을 너무 과대평가하지 마라.... 3평 그 좁밥도 1컷 78 나온 애들이다......
-
ㅈㄴ어럅다
-
통합수학도 예시문항이랑 22수능까지는 정상이었는데 해가 갈 수록 흑화중 통사 통과도 볼만 할 듯
-
모의고사 공부법 0
막상 시작하려니까 뭐부터 해야할 지 모르겠네요 각 과목 간략하게 좀 알려주실 수 있나요 ㅠㅠ??
-
혹시 원생이 아닌 사람도 학원에서 더프 볼수 있나요..?
-
.
-
'코인 천재' 아내 덕에 전업주부로 살고 있다는 한 남편의 사연이 전해졌다. 최근...
-
강기분 같은 기출분석 강의만 듣구 주간지, N제(?) 요론 문제들만 풀어두 실력이...
-
속보) 교육부 차관 "증원된 의대 32곳 중 12곳 학칙 개정 완료" 4
https://naver.me/FHAhR6DF 이 싸움도 거의 종바지에 이르고...
-
ㅜ
-
모고는 5시에 0
뜨죠…? 아 빨리 풀고 싶네 마렵다 진짜….왜케 야하게 생김
-
내척추도렬줘요
-
이걸 입학하고 두달뒤에나 알았네..
-
ㄹㅇ 오랫만 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김