(24.08.26) 코딩테스트 - 알고리즘 준비

Sparta Coding Club의 내일배움캠프를 최종 프로젝트를 끝으로 종료가 되어

이제부터는 이력서, 포트폴리오 작성과 취업을 취한 대비를 본격적으로 진행을 해야한다.

 

무조건적으로 내 스스로가 준비를 해야하는 것이기 때문에

내배캠에서 잠시 최종 프로젝트를 진행하면서 잠시 멈췄던 Code Kata의 연장선으로 코딩테스트 공부를 시작한다.

 

알고리즘, 그리고 관련 정보는 블로그, Notion에 정리를 하고,

기존에 TIL에 정리를 했던 것들도 다시 한번 살펴보면서 알고리즘 기준으로 정리를 할 계획

 

관련 코딩테스트관련한 강의와 여러 자료를 찾아보면서 환경 구성과 어떻게 진행을 해야할지 잠시 오늘 정리를 하고,

내일부터 본격적으로 코딩테스트에 도전을 할 계획이다.

 

---

테스트코드 알고리즘 유형 분석

• 구현 유형
  • 특정 알고리즘이 아니라 요구사항을 풀 수 있는 클래스 등을 구성해서 문제를 해결하는 문제가 중점
  • 그리디 알고리즘과 함께 특정 유형이나 패턴을 규정할 수 없음
• BFS/DFS , 그리디
  • 탐색, 특정 값을 찾는 문제
• 정렬
• 다이나믹 프로그래밍

필수 알고리즘과 트랜드

필수

탐색

BFS/DFS	완전 탐색
이분탐색	구간 탐색
투포인터
슬라이딩 윈도우

• 구간탐색 중 **슬라이딩 윈도우(구간을 움직이면서 특정 값을 찾는 탐색 알고리즘)**은 무조건 하나는 나옴

구현 & 수학

누적합 구간 내의 합 구하기

유클리드	최소공배수 / 최대공약수
에라토스테네스의 체	소수 빠르게 구하기

• 누적합에는 많은 알고리즘이 있지만 많이 사용하기 때문에 한 두개만 알고있어도 가능
• 에라토스테네스의 체는 연산횟수, 시간복잡도에 의한 시간이 초과되는 것을 방지

 

선택

• 반드시 무조건 알 필요는 없이 필수 알고리즘만으로도 구현이 가능하지만, 알고 있으면 빠르게, 또는 효율적으로 코테 코드를 짤 수 있는 알고리즘=

다익스트라	최단거리 구하기
플로이드 와샬
유니온파인드	같은 그룹인지 확인
크루스칼, 프림	Minimum Spanning Tree
Monotonic Stack	오름자순 / 내 림자순 개수
Bitmask	적은 메모리로 최대 효율
Trie	문자열 검색

• 다익스트라
  • CSS기본 지식과 관련된 알고리즘이기 떄문에 플로이드 와샬 알고리즘과 같이 알고 있으면 좋음
• 유니온 파인드
  • 같은 그룹을 찾는 알고리즘을 빠르게 찾을 수 있는 알고리즘
• 크리스칼, 프림 알고리즘 우선순위 X
  • Monotonic Stack(Stack을 다루는 스킬), Bitmask(2진번 기술로 메모리 효율을 위한 알고리즘), 많은 데이터를 훑지 않고 값을 찾는 알고리즘 역시 우선순위 X

 

---

알고리즘 기반 코딩테스트의 트랜드 중에 필수적인 알고리즘을 구분을 했다.

기존에 Code Kata를 통해서 공부를 했던 내용들과 많이 겹치는데, 

당시에는 그저 한문제 한문제 단위로만 봤다면, 이번에는 좀더 알고리즘 별로 진행할 수 있도록 해야한다.

 

Programmers 기반으로 난이도를 올려가면서 보고,

부족한 알고리즘이 있을 경우, leetcode를 활용해서 연습을 할 계획이다.

 

실제 테스트 시간처럼 오전 중에는 관련 알고리즘 공부와 알고리즘 코드를 직접 짜는 연습,

오후는 취업 관련 이력서, 포트폴리오, 면접 준비등을 할 계획.