알고리즘
1.알고리즘 1일차 - O(n^2) 정렬 , 버블 정렬, 삽입 정렬, 선택 정렬
1. 기본 정렬 알고리즘 고등학생 때, 나는 행렬을 굉장히 잘했다. (요즘 세대는 행렬을 고등학생 때 안배운다 카더라) 왜 난 행렬을 잘했고, 그 뒤에 있던 다른 수학 내용은 못했을까?? 아주 단순하다. 행렬은 수학책 첫장에 있었기 때문이다. 행렬은 해치웠지만, 그
2.알고리즘 2일차 - O(nlogn) 정렬 , 병합 정렬(merge sort)
지난 시간에 배웠던 정렬 알고리즘들은 O(n^2) 시간인 반해, 앞으로 소개할 정렬 알고리즘은 O(nlogn)이다.참고로 O(nlogn)과 O(n^2)이 별로 차이가 안나보여도 엄청난 차이가 있다.직접 종이를 가져와서 N = 10^5을 넣어보고 값의 차이를 보면 체감할
3.알고리즘 3일차 - O(nlogn) 정렬, 쿽정렬
이전에 병합 정렬이 O(nlogn)에 실행된다는 것을 알게되었다. 퀵정렬은 병합 정렬보다는 구현과 이해가 어렵지만, 메모리적으로 이득이 있어 많은 정렬 프로그램에 사용되는 알고리즘이다. 가장 대표적인 예로 c++의 sort stl은 내부가 퀵정렬로 구현되어있다.병합 정
4.알고리즘 4일차 - O(nlogn) 정렬, 힙과 힙정렬 개요 - 1부
안타깝게도 hip이 아니라, heap이다.힙정렬을 배우기 전에 힙을 먼저 알아야한다. 정리하자면힙 = 자료구조힙정렬 = 알고리즘으로, 힙이라는 자료구조를 이용한 정렬 알고리즘으 힙정렬이라는 것이다.트리라고하면 굉장히 어려워보이지만, 힙은 굉장히 단순한 트리구조를 갖는다
5.알고리즘 5일차 - O(nlogn) 정렬, 힙과 힙정렬 최대힙, 최소힙 - 2부
살려줘그렇다면 힙은 어떻게 사용할 때 유의미하게 사용할 수 있을까??그것이 바로 최소힙과 최대힙이다.최대힙은 힙 원소들 중 가장 큰 값이 맨 위에 있는 것을 의미하며, 최소힙은 반대로 힙 원소들 중 가장 작은 값이 맨 위에 있는 것을 의미한다.최대힙 또는 최소힙은 부모
6.알고리즘 6일차 - O(n) 정렬, 계수 정렬
왜!! 정렬 알고리즘은 끝이 없는 것인가!!하늘은 왜! O(N) 정렬까지 낳으신 것인가!!라고 해도 어쩔 수 없다. 그러나 이전에 맛본 O(nlogn)보다 훨씬 더 쉽고 간단하다.이전에 O(n^2) 알고리즘은 자신의 옆에 수와 비교해야하므로 n^2의 한계를 벗어나지 못
7.알고리즘 7일차 - O(n) 정렬, 기수 정렬
아뇨 시작하고싶지않습니다. 싫습니다기수 정렬은 정말 한 번도 문제 풀이에 써본적도, 프로젝트에서 써본 적도 없는 것 같다. 그냥 이런 알고리즘이 있구나 정도만 알고 넘어가도 문제가 없을 것 같다.계수 정렬과 마찬가지로 O(n) 알고리즘이다. 이제 기수 정렬을 살펴보자기
8.알고리즘 8일차 - 그래프, 기본 용어, 인접 리스트 표현
광기의 비트코인 그래프 떡상가즈아아아아이번 시간부터는 그래프에 대해서 알아볼 것이다. 지난 번에 힙정렬을 공부하면서 잠깐 트리를 공부하였는데, 트리는 계층이 있었다면 그래프는 계층이 없는 트리라고 생각하면 된다. 정렬 문제들이 면접에서 기본적으로 물어보는 알고리즘이라면
9.알고리즘 9일차 - 그래프, 그래프 순회, DFS
신입들이 싫어합니다프로그래머로서 취업을 하려면 코딩 테스트롤 통과해야한다. 물론 코딩테스트가 없는 회사도 있지만, 굳이 코딩테스트를 포기하여 다양한 회사의 선택지를 줄일 필요는 없다. 물론, 코딩테스트를 통과한다해서 끝인 것은 아니다.흔히 말하는 공룡 IT기업들이 원하
10.알고리즘 10일차 - 그래프, 그래프 순회, BFS
흔한 신입들의 상황 그래프의 순회에는 DFS와 BFS가 있다. DFS는 이전 시간에 알아보았지만, 기억이 안날 것이므로 원리만 간략하게 요약하면 다음과 같다. > 시작 정점에서 끝까지 찔러들어가고, 갈 곳이 없다면 돌아가자 요약은 개뿔 ㅎㅎ 필자의 글솜씨로는
11.알고리즘 11일차 - 그래프, 최단 경로 알고리즘, 다익스트라
피곤하다.. 그래도 해야한다 그래프에 관한 알고리즘이 워낙에 많고 시험에도 자주 나오니 대략적으로 정리하면 다음과 같다. 그래프의 순회 DFS BFS 그래프의 최단 경로 다익스트라 벨만포드 플루이드 와샬 최소 비용 그래프 연결(MST) 프림 크루