신입이 꼭 알아둬야 할 필수 알고리즘
* 참고 블로그 : 코딩테스트 문제 유형 정리
* 참고 블로그 : 알고리즘 공부 순서
* 코딩 테스트 사이트 : leetcode
* 코딩 테스트 사이트 : 프로그래머스
* 코딩 테스트 사이트 : 백준
"" 구현 / 완전탐색(DFS/BFS) / DP ""
Chapter 01. 자료구조
Chapter 02. 알고리즘s
1. 해시 테이블
* key-value쌍으로 저장되는 특성으로 자주 사용되는 자료 구조
프로그래머스 - 단어 변환
2020 KAKAO BLIND RECRUITMENT-주차 요금 계산
2. Stack & Queue
* 단독 보다는 구현하는데 필요한 자료구조 : 스택 - DFS , 큐 - BFS
* 선입 선출 / 후입 선출의 단서가 보이면 사용
3. 힙
* 우선 순위 고려하는 문제에서 사용 : 작은 수부터, 큰 수부터
* Java는 PriorityQueue를 사용한다고 하고 이는 개선된 다익스트라의 구현에 사용된다고 한다.
4. 구현
* 주어진 문제를 알고리즘을 통해 코드로 바꾸는 것 문제를 많이 풀어보는 수 밖에..
2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치
5. 완전 탐색 - 브루트 포스 ★★★★★★★
* DFS * BFS * 백트래킹(완탐은 아닙니다.)
* 모든 경우를 탐색해야 할 경우 사용 됩니다.
* 문제 조건에 따라 탐색을 최소한으로 만들어야 합니다.
2020 KAKAO BLIND RECRUITMENT - 양궁대회
5. 다이나믹 프로그래밍 [HARD]
* 복잡한 문제를 한 번에 해결 하는 것이 아닌, 조금씩 점차적으로 풀이하는 유형(점화식)
* bottom - up, top - down 을 모두 공부해야 합니다.
6. 그리디 [HARD]
* 부분적인 최적해가 전체적인 최적해가 되는 문제에서 사용
* 정렬, 우선순위 큐를 활용하는 경우가 많습니다.
7. 이분 탐색
* 순차적인 배열 탐색에서 시간초과가 나는 문제에서 하용
* 시간 복잡도가 O(logN) 으로 그냥 순회하는 O(N) 보다 빠르다
8. 트리
* DFS를 활용한 / 전/중/후위 순회, 루트 노드, 서브 트리, 높이, 너비, 그래프에서 트리의 수 찾기 등 다양하게 출제될 수 있습니다.
9. 그래프
* 최단 경로를 구하는 문제가 많이 출제됩니다.
* 다익스트라, 벨만-포드, BFS, 플로이드 - 워셜 알고리즘들을 사용합니다.
* 그래프 순회에는 DFS / BFS를 사용합니다.
+ 위상 정렬
2021 KAKAO BLIND RECRUITMENT-합승 택시 요금
10. 유니온 파인드
* 최근 자주 ㅊ기출
* 노드를 집합에 속하게 하는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어짐.
* 노드들을 루트 노드를 기준으로 하는 어떠한 집합으로 묶는다고 생각하면 이해하기 쉽습니다.
11. 최소 신장 트리
* 최소 신장 트리를 만드는데 필요한 비용을 구하는 유형
* 자주 기출은 안됨
* 크루스칼, 프림 알고리즘 공부하자요
12. 비트마스킹
* 문제에서 0, 1 로 표현할 수 있는 경우 비트마스크를 사용하여 효율적으로 풀이
* 비트마스크를 사용하면 수행 시간, 메모리에서 이점을 가집니다.
비트 연산자를 사용하기 때무네 AND, OR, XOR, NOT, SHIFT를 공부합시다.
'지식 창고 > 알고리즘' 카테고리의 다른 글
| *작성중* JavaScript 순열 & 조합 알고리즘 (1) | 2023.05.26 |
|---|---|
| *작성 중 ** [알고리즘] 피보나치 - 재귀함수와 동적계획법 알고리즘 (0) | 2023.04.25 |