백엔드 신입 개발자가 쌓아야 하는 역량은? - 자료구조/알고리즘/코딩테스트편

처음엔 자료구조/ 알고리즘등을 배우는 것이 코딩테스트만을 위한 것인 줄 알았다.

이번 주차에 CS강의를 들으면서 프로세스 실행 순서를 관리하는 스켸줄러 알고리즘이 큐를 사용한다는 것을 알게되었다.

이렇게 하나의 기능을 만드는데도 여러 자료구조와 알고리즘이 적용된다는 것을 보니 필수적인 지식인 것 같다.

 

자료구조

- 자료를 효율적으로 관리(저장, 삭제, 탐색)하기 위한 구조

- 목적에 맞게 사용한 좋은 자료구조는 실행시간 단축 / 메모리 용량 절감 효과가 있음.

- 알고리즘에 적절히 사용

 

선형 자료구조 : 자료들이 1 : 1 로 연결

  배열, 연결리스트, 스택, 큐, 데크 , 해시테이블

 

비선형 자료구조 : 자료들이 1 : N으로 연결

  트리, 그래프, 힙, 우선순위 큐, 트라이

 

---

알고리즘

종류 : 정렬, 이진탐색, 투포인터, 그리디, 백트래킹, 분할정복, 다이나믹 프로그래밍(타뷸레이션, 메모이제이션), 최단경로 (다익스트라, 벨만포드, 플로이드 워셜), 최소신장트리 (크루스칼, 프림)

 

- 이진탐색 : 정렬된 상태의 데이터에서 특저값을 빠르게 탐색하는 방법

  시간 복잡도 : O(log n)

 

- 투 포인터 : 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻음

  시간 복잡도 : O(N) // for문을 중첩해서 풀어야하는 문제들을 선형적으로 풀 수 있음.

 

- 그리디 : 매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법

   탐욕적 선택 특성과 최적 부분 구조를 만족해야함.

 

- 분할 정복 : 큰 문제를 작은 부분 문제로 나누어 해결하는 기법

  합병정렬, 퀵 정렬, 이진탐색 ....

 

- 다이나믹 프로그래밍 : 큰 문제를 작은 부분 문제로 나누어 답을 찾아가는 과정에서 계산된 결과를 기록하고 재활용하여 문제의 답을 구함.

  타뷸레이션(상향식) , 메모이제이션(하향식)

 

- 백트래킹 : 모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더이상 구하지 않는 방법

  * 재귀함수 구현 능숙해야함.

 

- 최단경로 : 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법

  다익스트라, 벨만포드, 플로이드 워셜

 

- 최소신장트리 (MST) : 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법

  크루스칼, 프림

 

정말 어렵고 아직도 잘 모르겠다... 개념을 다시 복습하고 유형별 문제를 풀어보면서 익혀야겠다.

 

---

코딩테스트

이전까지 좋은 점수를 받아왔던 코딩테스트에서 3차를 지나가며 다 맞추지 못 했다.

일단 알고리즘을 사용해야한다는 생각을 하니 무지성 구현을 하면 풀 수 있을 것 같은 문제들도 어렵게 다가온다.

어떤 알고리즘을 적용해야 하는 것까진 떠올려도 그것을 응용해서 구현하기가 너무 어렵다. 정말 모르겠는 느낌이다.

그래도 해야지 어쩌겠어 ... 반복하면 언젠간 되겠지 ㅠ

 

문제를 풀면서 시간 효율성, 메모리 효율성을 전혀 고려하지 못 하고 있는데 아직 자료구조와 알고리즘에 익숙하지 못 한 탓 같다.