들어가며
코딩테스트를 잘 보기 위해서는 자료구조와 알고리즘을 공부해야한다고는 하는데
이 둘이 정확히 뭔지 둘 사이의 관계는 무엇인지 코테는 왜 이러한 지식을 요구하는지
이번에 정리하고자 한다. 둘 사이의 관계가 너무 헷갈렸다..
자료구조
단어 그대로 자료를 담는 구조를 말한다. 그 구조는 논리적인 규칙으로 정해는 것이다.
예를 들어보자! 책장에 책을 꽂아두는 상황에서, 아무렇게나 꽂으면 원하는 책을 찾기 어렵다.
규칙1. 가나다 순으로 꽂아넣기
규칙2. 분야별로 꽂아넣기
등등 규칙을 정해서 꽂아넣으면 찾기 쉬울것이다.
하지만 여기서도 문제가 생길 수 있다. 규칙2로 정해진 책장 구조에서 분야별로 동일한 공간을 마련했지만
소설책은 거의 없어 공간이 널널하고, 만화책은 너무 많아 공간이 비좁다면, 공간을 비효율적으로 사용한 것이다.
책장은 메모리, 책은 데이터라고 볼 수 있다.
규칙 즉 자료구조를 선택할 때 메모리 공간을 효율적으로 사용하는 것도 생각해주어야 한다.
자료구조의 종류
자료구조는 구현을 기준으로 분류할 수 있고, 형태를 기준으로 분류할 수 있다.
구현 기준 분류
- 배열
- 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
- 해시테이블
형태 기준 분류
구조와 자료간 관계가 1:1이면 선형구조, 1:N 또는 N:N (N>=2) 이면 비선형 구조,
파일 구조가 있다.
- 선형 구조
- 스택
- 큐
- 원형 큐
- 덱
- 비선형 구조
- 그래프
- 트리
- 힙
- 파일 구조
알고리즘
알고리즘은 어떤 문제를 해결하기 위해 정해진 절차나 방법을 공식화한 형태로 표현한 것이다.
자료구조가 선택되면 그에 적용할 알고리즘이 명확해진다.
책장의 예시를 다시 보며느 자료구조에 저장된 책들을 찾기 위해서 알고리즘을 사용하면 된다.
방법1. 왼쪽부터 순서대로
방법2. 역순으로
방법3. 중간부터
"나루토" 라는 만화책을 찾으려면, 규칙1의 자료구조에서는 방법1로 찾는 것이 빠를 것이고,
규칙2의 자료구조에서는 해당 분야 책장부터 찾아야할것이다.
좋은 알고리즘이란?
알고리즘을 선택하는 기준을 뭘까. 당연히 좋은 알고리즘을 선택하는 것이다.
좋은 알고리즘이란 뭘까.
- 정확성
- 작업량
- 저장공간
- 최적성
- 복잡도(Big-O)
이러한 기준을 따져보고 알맞은 알고리즘을 선택하는 것이다.
(복잡도에 대해서는 추후 포스팅 예정)
알고리즘의 종류
주제별 분류
- 정렬
- 탐색
- 그래프
설계 기법,전략별 분류
- 재귀호출
- 동적계획법
- 탐욕 알고리즘
- 백트래킹
자료 구조와 알고리즘의 관계
위의 내용을 정리해보면,
자료구조 : 데이터를 어떠한 구조로 담을 건지에 대한 규칙.
생각할내용: 어떤 자료구조를 써야 자료를 효율적으로 담을까?
알고리즘 : 저장된 데이터를 어떠한 절차로 찾고 이용할까에 대한 방법.
생각할내용: 문제 해결을 위한 절차를 어떻게 짜야할까?
프로그램은 특정 문제를 해결하기 위한 처리 방법+순서를 기록한 명령어의 집합이다.
이 프로그램이 실행되려면 메모리에 올릴 데이터가 필요하고 이 데이터를 담아내는 방식은 자료구조인 것이다.
프로그램 = 자료구조 + 알고리즘 이라고 볼 수 있다.
공부해야지
효율적으로 프로그램을 짤 수 있는지에 대한 역량이 코테로부터 파악할 수 있기때문에 기업에서는 코테를 도입하는 것 같다.
개인적으로 자료구조나 알고리즘은 딱딱해서 공부하기 싫었지만, 글 정리를 하면서 공부해야 할 동기를 얻었다.