정보) 컴퓨터공학과 과목 맛보기 - 4. 알고리즘
게시글 주소: https://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
울었어 알파메일 씹기만자들은 오르비 나가세요
-
애초에 군대가 거의 남자들의 조직이고 그런 남자들을 가장 잘 이해하고 다룰 수 있는...
-
원래 3만 떠서 설마하고 1회차 풀고나서 보니까 미적 65점임... 공통 객관식에서...
-
귀속지위 잘받고 태어나면 언론이 나서서 보호해주려 합니다
-
잼민이들 언제 가는거지 15
집에 있으니까 눈치보이네
-
이런 그림 진심 처음 봄
-
솔직히 전 여전히 어렵네요 매번 악순환으로 되서 그런지 그런지 자리를 피하더라구요...
-
백분위 몇정도 나올까요 중간2등급이라 가정했을때
-
사놓고 유기중이었던거 낼 풀려하는데 이번 영어는 별로다는 말이 있어서 걍 패스할까...
-
괜찮겠죠...? 유독 과탐만 이러네요 물지 둘다 모고는 1가깝게 나오는데 사설만...
-
지금부터 13
남초/여초발 성별 혐오 용어 및 발언 등등 컨관님한테 제보해서 정지먹일겁니다...
-
시바 듭으라 0
후드를 왜 쳐입고 왔을까
-
여자3수=남자 현역 맞음 일단 취업 기준으로 3수는 남녀 상관없이 큰 디메릿 없음...
-
정병 감성 MAX
-
앉아만 있으면 됨
-
문학 정공법 5
가장 이상적인 공부법이 뭘까요? 예를 들어 독서는 문장을 읽는 능력을 키우고 지문을...
-
이제부터 좋은 글만 쓰자 ㅠ
-
1시간 재고 푸는데 30초남기고 22번 풀어서 드디어 다 맞냐!!!!! 했더니...
-
정석킥!
-
월급빼고 다 오른다…오늘부터 초콜릿·김·콜라 등 가격 인상 4
6월부터 초콜릿과 김, 간장, 음료 가격이 줄줄이 오른다. 1일 식품업계에 따르면,...
-
학교에 6모 신청했는데 고3이랑 같은반에서 보는듯 ㅠㅠ 나 고3때 애들이 재수생...
-
메디컬한정해서는 맞말임 그래서 나랑은 상관없음ㅋㅋ
-
여성징병시 출산율 더 떨어진다고 주장하는 경우가 있는데 0
이건 저출산의 근본적 원인을 전혀 이해하지 못한 주장임. 굳이 출산시 병역 면제...
-
이번 사건은 "여자라서" 처벌을 안받았다기보단 그냥 군이 부조리를 덮으려고 쉬쉬하려...
-
참고로 단과는 물리 ㅎㅈㅎ이에요 거기서 브릿지 품
-
아님. 기업에서 당연히 군대 2년 계산함,,,, 여자 첫 취업 25~26선은 잡혀야됨
-
남녀 둘다 군대보내고 애낳으면 면제나 상근 저 아래 여초딩 1년 어리게보내자보다 백배는 나은듯 ㄹㅇ
-
졸려요 0
내가 선택한 4.5시간 숙면이지만 왜그랬을까..
-
고1모고 작년 6월꺼 풀었는데 처음부터 글 하나도 안 읽히다 한 20분째에 배...
-
저는 마계라구요
-
솔직히 여자 군대 가든 안가든 나라가 시키면 가겠다마는 4
안보내도 기본적인 군사훈련은 받았으면… 나도 총 쏴보면서 훈련하고 굴러봐야 동생이...
-
산책좀할까 2
오늘노래가다좋네
-
힘들다 1
하
-
리쌍에 빠지다 2
독기 나란 놈은 답은 너다 광대 내가 웃는게 아니야 헤어지지못하는여자...
-
이번 일로 훈련 장교는 여군 안뽑았으면 하네요... 어디까지가 수행할 수 있는...
-
ㄷㄷㄷㄷ
-
어머니 생1화1 강사 아버지 물1지1 강사로 중1 때부터 과탐 배웠고 하필 희망...
-
무슨 마음가짐인가요
-
지금까지 국어 n제를 할려고 기출을 휙휙 넘겼는데 그냥 옛기출이랑 최신기출 회독하고...
-
정신과 가는날 기모찌 16
외출하는 날이 제일 좋아 학원 너무 답답해~~~~~ 근데 슈발 오지게 덥네
-
나 최저 맞춰야한다고 ㅠㅠㅠㅠ
-
개더워서 담요 못덮음...
-
침대
-
[서울경제] 정부의 인구정책 평가를 전담하기로 한 국책연구기관 한국조세재정연구원이...
-
눈치 보인다.
-
예쁜 카페,사진 찍기 좋은 카페입니다 물론 음료 가성비라던가 카공 가능한 곳으로...
-
ㅜㅜ 괜찮나요 사람들 인식이나 전망..같은거
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS!
ㄱㅁ
PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! PS! 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김