정보) 컴퓨터공학과 과목 맛보기 - 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를 선물하세요.
-
출토시기: 2019년 말~2020년 초 미공개 정보 사유 : 보닌 개인정보(이름,...
-
김승리쌤 '유기적 연결', '이면 뜻 파악(추론)' 질문있어요 제발... 0
올오카 독서 듣는데 벌써 Theme 3을 눈앞에 두고 매월승리 1호 다 마쳐도 진짜...
-
대성마이맥 패스 0
번장이나 이런데서 사도 ㄱㅊ나요?
-
현역 53334 재수 41311 여태 수능 공부 놓았는데 삼반수 고민이 요새...
-
"초등생 딸 뇌진탕"…엘베서 춤추다 '쿵', 천장 구조물 떨어져 1
초등학생이 인천의 한 아파트 엘리베이터 안에서 춤추다가 천장 구조물이 머리 위로...
-
은성수 “아들 병역비리 고발 취하를” 병무청에 13차례 전화 1
문재인 정부 당시 금융위원장(장관급)을 지낸 은성수 전 위원장(사진)이 아들의...
-
출동이라는 답을 받았다
-
개신당!개신당
-
1. '4점 기출' 다 풀면 평가원 기출 중에 꼭 필요한 평가원 기출 3점 문제,...
-
널 위해 준비한 오백가지 멋진 말이 남았는데
-
우리 갤... 정말 대단해! 다른 사람이 욕할 바에야 내가 욕한다, 이런 건가?
-
원함수 도입하고 남는 조건 하나 쓰면 끝
-
단어 1권(능률 보카)는 4회독 했고 워마2000 2회독 중인데, 이번에 5모 62...
-
음 일단 나중에 돈을 많이 벌고 싶은데 그러려면 연구원을 해야될 것 같고….....
-
작년기준 내가본바론 "지인선팀가람 1 2회" 얘가 가장 정신나갔었음ㅋㅋ
-
기대돼요
-
"대통령은 이재명!"…국민 3명 중 1명, 이재명 차기 대통령 원해 4
[헤럴드경제=채상우 기자] 국민 3명 중 1명은 차기 대통령으로 이재명 더불어민주당...
-
수의대 화작질문 1
수의대 가고싶은데 화작 1컷뜨면 갈수있나요 미적 백분위99 영어1 과탐1컷기준이요
-
현재 리밋을 다 끝낸 상태인데 리밋다끝내고 리미티드부교재를 할까 아님 임팩트를...
-
나가기싫다…. 0
집들어왓는데 스카가기싫어요
-
술게임 못하니까.. 그냥 건전하게 놀아야 하려나 그렇다고 둘이서만 있으면 어색할거 같은데
-
[단독] 김동아 고교 짝꿍의 육성 고백 "친구 폭행 알고 있었다, 진심으로 사과해야" 1
【 앵커멘트 】 서울 서대문갑 김동아 당선인의 학교폭력 의혹 제기 이후, 김...
-
부처님내말을들어줘요학교도불교대학으로갔는데.....
-
스피드러너나 풉시다
-
5모 메가는 국어 뱍분위 89인데 ebs는 93으로 나와서 아니면 편차가 원래 심한가요?
-
어쩐지…계속병신짓하더라…
-
인강 책 등등
-
다 찍으면 올려보겠습니다
-
-
친구랑 왔는데 스마트 tv로 십덕 공연영상 틀어놓고 보니까 극락이네 ㅋㅋ
-
아 이걸 뭐라고 설명해야하지 암튼 뭔가 중요한 물건이 없어진 기분
-
2024년 시행 고3 5월 학평 국어 문학 지문분석 및 변형문제 배포 0
안녕하세요. 나무아카데미입니다. 2024년 시행 고3 5월 학평 국어 문학 지문분석...
-
믿어봐 문장편. 들을까하는데 믿어봐 문장편. 24년 책과 25년 책이 내용이...
-
평소에 0
아이패드로 국어 기출 푸시는 분 있나요?
-
안녕하세요? 제가 연말에 전역인데 국영수가 다 6등급이 나왔습니다... 그래서...
-
소음 입력 개열받네
-
설입에서 10분거리에 7호선을 만나는 곳은 대림역, 거기서 31분 가서 환승치는곳은...
-
잘잤다 3
-
야뎊을 쓰는것도 아니고 정품을 훔치는건 ㅋㅋ
-
자기 선택 과목만 아는게 일반적임? 아니면 고딩 때 배우기는 다함?
-
언매 구개음화 5
언매 풀다가 해설지에 ’닫힌[다친]‘ 이 ㅎ축약 + 구개음화라고 돼있는데 구개음화는...
-
환승4번해야함
-
5모 푸는데 너무 불편해 글씨도 작고 ;
-
엄청 어려웠다는데 얼마나 어려울지
-
외국 면허 의사, 국가·학교 안 따져… 개원 못하고 대형병원서 진료 3
정부, 의료 공백 장기화에 ‘초강수’ 그동안 외국에서 의대를 나오고 의사 면허까지...
-
아무래도제가가르치는데는소질이..
-
현역이라 시간이 없어서 최대한 효율적인 수단을 찾고 있습니다 문학론은 오티랑 맛보기...
-
실시간 해강 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 찬양해
와 어지럽네
사실 이건 알고리즘 중에서도 극히 일부인..
레드 블랙 트리 구현 때문에 이진 탐색 혐오 조금 생김