1. 개념
알고리즘이란 어떤 문제를 해결해나가는 과정을 의미한다.
다만 같은 문제를 해결하는 여러가지 방법 중 더 효율적인 방법이 있기 나름이므로 알고리즘 공부가 필요한 것
다만 알고리즘이란건 수천, 수만종류 이상이 있다.
예시로 정렬알고리즘이라는 하나의 카테고리 안에서도 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬 등등 아주 많은 종류가 있으며 또 그 각 정렬 내에서도 적용 가능한 기법들이 다양하다.
그러므로 세상의 모든 알고리즘을 공부할 수는 없으며 우선적으로 컴퓨터공학에서 자주 사용되는 알고리즘부터 공부해나가면 된다.
단, 알고리즘 공부하기 전에 자료구조 공부가 선행되어 있어야 한다.
2. 종류
기본적인 컴퓨터공학 알고리즘
우선 알고리즘 공부를 시작하는 단계에서 배워볼만한 알고리즘들이다.
일반적인 코딩테스트 수준에서 사용되는 알고리즘들이며 위에서 아래순으로 공부는 하되
중요도 순서가 아니라 위의 내용을 알아야 아래의 내용을 알 수 있는 경우가 몇몇 있다.
다만 하나씩 마스터하고 다음 알고리즘으로 가는게 아니라
전부다 개념공부 -> 전부다 브론즈문제 -> 전부다 실버문제 이런식으로 섞어쓰면서 발전해나가면 좋다.
두개 이상의 개념을 합쳐서 사용하거나 다른 방식을 쓰는게 더 쉬워지는 문제들도 많기 때문이다.
1) 복잡도개념 : 시간복잡도, 공간복잡도, BigO 표기법에 대해 알아야 함
2) 누적 합 : 알고리즘이란 이런것이구나 느낄 수 있는 간단한 알고리즘
3) 그리디 / 스위핑 / 투포인터 : 셋이 각자 다른 개념이지만 특정 알고리즘이라기보단 방법론이라 묶어둠
4) 비트마스킹 : 이진수 개념인 비트로 부분집합을 나타내는 방법론
5) BFS, DFS, 트리순회 : 그래프(트리) 순회(탐색)하는 알고리즘, 그래프이론 공부 선행 후 공부해야 함
6) 최단거리 : 그래프(트리)에서 목적지까지의 최단거리를 찾는 알고리즘, BFS 공부 선행 후 공부해야 함
7) 완전탐색, 백트래킹 : 다양한 방법으로 브루트포스하는 알고리즘, DFS 공부 선행 후 공부해야 함
8) 정렬 알고리즘 : 대부분 언어에서 지원하는 sort가 있지만 개념은 알아야하므로
9) 이분 탐색 : 데이터에 찾고자 하는 value가 있는지 빠르게 찾는 알고리즘
10) DP : 문제를 작은 문제로 쪼개고 작은 문제의 해결을 통해 큰 문제를 해결하는 알고리즘
11) LIS : 수열 중 몇개의 수를 뽑아 가장 긴 부분수열을 만드는 알고리즘, 이분탐색 선행 후 공부해야 함
12) 세그먼트트리, 펜윅트리 : 알고리즘보다는 자료구조에 가깝지만 해당 자료구조를 활용하는 알고리즘
또한 코딩테스트 사이트 하면서 맞는것 같은데 왜 틀리지? 라는 생각이 들땐 개인적으로
40%는 자료형 범위 벗어나서(세심함 부족)
30%는 사이드 케이스 테스트 안해서(귀찮음으로 인한 게으름)
20%는 시간초과(알고리즘 이해 부족)
10%는 진짜 틀려서 인듯하다
사이드케이스 테스트 꼭 하고 제출하고, 자료형 범위 벗어날 여지가 있는지 한번씩 확인하기
심화 컴퓨터공학 알고리즘
공부해본 알고리즘
1) 신발끈 공식 : 알고리즘이라기보단 수학적 개념
2) 유니온 파인드 : 서로소집합 또는 분리집합이라고도 불리며 선택한 두 노드가 연결되어 있는지 확인하는 개념
3) MST 알고리즘 : 최소신장트리(Minimum Spanning Tree)를 만드는 알고리즘인 크루스칼, 프림 알고리즘
4) 위상정렬 : 비순환 단방향 그래프의 방문순서를 정하는 알고리즘
아직 공부하지 않았거나 이해하지 못했지만 나중에 공부해볼 가치가 있는 알고리즘
1) KMP & 보이어무어 => 문자열 탐색 알고리즘
2) 에이스타
3) 분할정복
4) lazy propagation
5) 트라이(trie) 자료구조
6) 얍문블로그 재귀 글들