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

자료구조와 알고리즘

    1. 자료구조

 

• 배열 - 동일한 데이터들을 여러개로 묶어 관리하기 위한 가장 기초적인 자료구조
• 리스트 - 제너릭하게 넣을 수도 있고 오브젝트하게도 데이터를 넣을 수 있는 자료구조
• 세트 - 해쉬를 이용한 세트와 트리를 이용한 세트가 있으며 중복된 데이터의 저장은 허용하지 않는 자료구조
• 맵 - 세트와 마찬가지로 해쉬와 트리를 이용한 맵이 있으며 키와 값이 한쌍으로 들어간다. 해쉬 충돌에 대한 이해가 필요하다.
• 스택 - 후입선출(LIFO) 구조로 나중에 들어온 데이터가 먼저 나가도록 설계된 자료구조
• 큐 - 스택과 다르게 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 방식
• 덱 - 스택과 큐를 결합한 방식의 자료구조
• 트리 - 위의 자료구조는 선형적인 방식이었다면 트리는 비선형적인 방식이다. 계층적인 구조로 되어있으며 부모노드가 자식노드를 가지는 형태로 되어있다
• 그래프 - 트리보다 더욱 비선형적이다. 노드와 그 노드들을 잇는 엣지들의 연결 형태로 되어있으며 bfs,dfs나 최단거리 알고리즘에 사용되어 매우 중요하다

 

 

   2. 알고리즘

 

• 브루트포스 - 무차별 대입법이라고도 불리우는데 말그대로 모든 가능한 경우의 수를 순회하며 해답을 찾는 알고리즘
• 정렬 - 데이터들의 집합을 특정한 규칙에 따라 배열시켜놓는 알고리즘. 버블소트, 셀렉트소트, 라딕스소트, 카운팅소트, 머지소트, 힙소트, 셸소트 등 여러가지 정렬방법들이 있다 
• 재귀 - 하나의 함수에서 자기 자신을 다시 호출하여 작업하는 알고리즘. 주로 동일한 문제의 조금 더 작은 경우를 해결할 때 사용함
• 백트래킹 - 재귀를 이용해 브루트포스적으로 들어가되 만일 중간에 해답이 아닐법한 경우가 있으면 bruning을 거치면서 해답에 접근한다
• 그리디 - 단계 단계마다 최선의 선택을 해가며 나아가는 방식의 알고리즘. 언뜻 잘못 설계하면 그렇게 해나간 최종 선택이 문제에서 요구하는 해답이 아닐 수도 있다
• 이분 탐색 - 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘. 반드시 정렬된 데이터여야 한다
• DP - 큰 문제를 작은 문제로 나누어가며 해결해나가는 방식의 알고리즘
• bfs - Breadth-First-Search 너비우선탐색이라고 불리며 시작 정점으로부터 가까운 정점을 먼저 방문, 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
• dfs - Depth-First_Search 깊이우선탐색이라고 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 다익스트라 - DP와 bfs를 활용한 대표적인 최단경로 탐색 알고리즘. 양의 간선만 존재해야 한다
• 벨만 포드 - 음의 간선이 존재하는 그래프에서 최단경로를 탐색할 때 쓰이는 알고리즘
• 플로이드 워셜 - 모든 지점에서 다른 모든 지점까지의 최단경로를 구할 때 쓰이는 알고리즘
• 투 포인터 - 배열이나 리스트에서 두 개의 포인터를 사용해 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘

 

 

코딩 테스트

코딩 테스트 연습은 주로 백준 온라인 저지 사이트나 프로그래머스와 같은 사이트에서 연습할 수 있다.

물론 더욱 세계적인 영역에서 연습하길 바란다면 코드포스라는 사이트도 있지만 대부분이 영어이므로 이를 잘 숙지하고 들어가보는 것이 좋을 것 같다.

 

코딩 테스트는 무조건적으로 제약조건이 있는데 시간 제한과 메모리 제한이 걸려있다.

이는 자료구조와 알고리즘에 대한 이해가 얼마나 뛰어난가에 대한 척도를 쟤기위한 용도로

예를 들어, 데이터의 갯수 N이 50,000 이고 이를 제한시간 1초내에 데이터들을 오름차순으로 출력하여라 라는 문제가 있다고 하자.

 

만일, 그저 버블 소트, 셀렉트 소트, 라딕스 소트 같은 이중 포문을 이용한 방법을 이용해 오름차순 정렬을 한다면

시간복잡도가 O(n^2) 이므로 50,000^2 > 1억 이 넘어 1초안에 오름차순으로 정렬하는 것은 실패하게 된다.

 

알고리즘, 자료구조 이해도가 여기서 더 뛰어나 머지소트나 힙소트 방법을 알고 있었다면 O(n log n) 시간안에 정렬이 가능해 성공했을 것이다.

 

이와같이 알고리즘과 자료구조에 대한 이해도를 올리는건 당연하게도 코딩 테스트를 원활하게 통과하는데 도움을 주고 필수적인 것이다.