TodayWhatIStudy_algorithm

코딩테스트를 왜 보는가?

• 주어진 상황을 코딩할 수 있는가를 평가
• 현업에서 개발할 수 있나라는 기초평가
• 고급알고리즘을 잘아는가? -> 이거는 대회수준
• 기초 알고리즘을 얼마나 잘 활용하는가

필요한 역량

• 추상화(상황 분석)
• 절차적 사고
• 구현 능력

코딩테스트 대표 유형

• 구현: 파싱, 해싱, 정렬, 시뮬레이션
• 탐색: DFS, BFS, 완전탐색(백트랙킹)
• 구조: 자료구조(스택, 큐, 힙 등)
• 알고리즘: Greedy, DP, 이분탐색

C++? Python?

결론적으로는 둘 다 쓰자(각각의 장점을 활용)

• C++
  • 언어 자체 속도 빠름
  • STL등의 장점이 있음
  • 재귀의 깊이가 깊은 문제, 자료구조를 많이 활용해야하는 문제에 유용
• Python
  • 문법이 쉬움
  • String, 정렬, 파싱, 객체를 다뤄야하는 문제에 유용

코딩테스트 유형별 알고리즘 분류

• Type Of CodingTest

알고리즘 풀이

• BAEKJOON

알고리즘에 필요한 파이썬 내용들

• Algorithm with Python

알고리즘 종류

1. Search
2. Sorting
3. Recursive
4. DynamicProgramming
5. Greedy Algorithm
6. Minimum Spanning Tree
7. Back Tracking

시간복잡도 VS 공간복잡도

• 개념
  • 시간 복잡도: 얼마나 빠르게 실행되는지
  • 공간 복잡도: 얼마나 많은 저장 공간이 필요한지
• 필요한 이유: 좋은 알고리즘을 짜기 위해
• 요즘은 대용량 시스템이 보편화-> 시간 복잡도가 우선
• But 공간복잡도가 필요한 경우
  • 기존 알고리즘에서는 공간 복잡도에서도 제약을 두는 경우가 있음.
  • 면접시에도 간혹 묻는 경우가 있음.
  • 변수의 갯수를 생각해주면 계산하기 쉬움.

몇가지 Tips

• and, or, not >>, << ... 활용
• 현재 상태를 저장하는 자료를 활용
• 코드는 간결하게 _ 나눠서 함수로 진행하기
• 여러 자료구조 또는 메서드, 함수 활용
• 처리의 우선순위 정리 후 코드 짜기
• 예제, 최소, 최대, 예외, 랜덤 .. 케이스 직접 만들어보기