정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://iu.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를 선물하세요.
-
걍 지문 뒤져가며 푸는데 이비에스 다 이해+암기 하고 가는방법밖엔 없겠죠?
-
씹ㅋㅋㄱㅋㅋ. 아니 재종반 아조씨들이 "야 기생집 봤냐 어떰?" "음 ㅋㅋ...
-
내 이상형 5
25수능 표점합 400 이상
-
ㅇㅇ? 살만함?
-
원래 학교에서 보내주시다 이번엔 현장배부만 하신데서 팩스로 평가원에 신청해야 할 거...
-
고등수학 ㅈ반고 문제입니다 누가 오류라던데 어디가 잘못됐는지 모르겠어요
-
현역때 시발점 3회독 했고 지금 아이디어 하고 있는데 확실히 얻어가는게 있긴 한데...
-
수강율이 1%넘는데 수강율1%미만으로 계속 거절당하는데 어떻게해야되나요?
-
9번문제 좀 많이 치사하지 않나 평가원이 이렇게 치사한 집단이 아니였는데 모두...
-
유산을 물려받음 3
기분이 묘하네
-
냥! 7
냥!?이치?니?산 ?냥!☺️아리가또 ?냥!?이치?니?산 ?냥!☺️아리가또...
-
내용 좋아서 북마크해도 며칠 지나면 삭제돼
-
고1때 만든 통합과학으로도 풀리는 문제 생2로도 풀 수 있음 꽤 신유형이긴함...
-
진짜 입시커뮤네 1
과거의 오루비구나
-
국어 6모 언매 86점 표점?? 백분위??
-
셔츠 데님 팔찌 목걸이까지 ㄷㄷ 하다못해 남녀합반이면 몰라…
-
집중 잘되나요...? 관독에 코 훌쩍이는애땜에 걍 집앞독서실에서 독재할까생각중인데ㅜㅜ
-
배고프지도 않고 입맛도 없고 잠도 안오고 눈물만 남.. 수능은 어떡하지
-
양승진 4코 0
시즌1 풀었는데 보니깐 시즌2랑 3랑 비슷한거 같은데 바로 시즌3 풀어도 괜찮을까요?
-
이거 마지막에 ㅣg(x)ㅣ그래프 그리면 접점이 m=0, m양수, 음수일때 해서...
-
단식 들어간 서울아산병원 교수 "환자·전공의들에게 미안해서" 1
"건강 괜찮아…힘든 상황에 동참하는 것 같아 마음은 편해" (서울=연합뉴스) 성서호...
-
서울대 경영 수시 일반으로 붙으신 선배님들 ㅠㅠ 질문하고 싶은 게 많아서 구합니다ㅠ...
-
"웹소설 원작 말고, 옛 소설을 원작으로" "솔직히... 한 번쯤은 상상해 봤잖아"...
-
뭔가 익숙하다 했더니 작년에 이미 풀어본거였네 ㅋㅋㅋ 어쩐지 문제가 지문이...
-
국어실력올리려면 1
낯선지문을 봐도 이해할수 있다는 그 자신감이 중요함?? 마치 수학에서 어려운문제를...
-
3월 4일 시작... 진짜 거의 3개월 공부하고 6모 쳤네용 수학은 맞힐 수 있는...
-
풀다가 오기 생겨서 30분동안 붙잡으니까 진도 ㅈㄴ 안나가네 걍 넘겨야지 ㅡ.ㅡ
-
연대 정시 출결 0
고1이고 학종이랑 수시 버리고 지금부터 정시 준비하고 있습니다. 학폭 때문에 출결이...
-
힘 조절 실패함ㅎㅎ
-
후반부에서도 폼 유지하는 게 없어 ㅋㅋ 나히아 진짜 ㅈㄴ 난잡하던데
-
기출은 크포 한다음 하고 일단 스타팅 포인트부터 하는데 겁나 오래걸리네요 원래...
-
보통 시험에서 과탐을 조지면 "아 과탐 공부 열심히 해야겠다"가 나와야 하는데...
-
저격 18
-
복무 500일차 4
밥이…점점 다 되었군..
-
정병훈T : 2025 6평 최초풀이 때 답만 낸다면 공통+선택 미적분 30분컷 가능하다
-
분러 단과 0
바자관 다니는 중인데 단과 째면 벌점 받나 강윤구 9모 확통 연대 박광일 사탐 국어 기하 의대
-
지2러 공감짤 5
갓직히 이거 두개면 천체 국밥이다 ㅇㅈ?
-
남친구함 4
존잘남찾음
-
김승리 이원준 정석민 김동욱 들어봤는데 체화가 1도 안됨 내 뇌가 체화를 거부함...
-
뭔가 이상한기원
-
난 잘하는게 없어 14
언젠간 생기겠지?
-
28일차
-
[정보] 모의고사 성적표 팩스 신청법 - 오르비 (orbi.kr)...
-
마더텅 풀고 틀린문제 있을땐 다시 천천히 읽어보면서 답 고치고 맞으면 어디서 잘못...
-
군캉스 재시작 0
휴가복귀중
-
3합3맞추는 그날까지!!
-
국영수로대학가자
-
부탁해!
-
작수 독서 -12 문학 -4 언매 -16 3등급이고 (백분위 77) 이번 6평 독서...
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김