JAVA 로 자료구조 구현하기 - 1.기초

JAVA 로 코딩테스트 문제를 풀면서 알고리즘을 공부하고 있다. 

 

알고리즘을 공부하는게 단순 문제를 풀면 된다고 생각했지만, 

언제 연결리스트를 써야할 지, 언제 배열을 쓰는게 더 효율적인지, 그리고 시간/공간 복잡도를 고려한다면 어떻게 최적화 할 수 있는지 알 수 없었다. 

 

지금까지 거의 단순구조만을 이용해 if 문, for 문을 남발하며 문제를 풀었는데, 이것은 좋은 알고리즘이 아닌 것 같다.

좋은 알고리즘이란 무엇일까?

 

우선, 자료구조를 직접 구현하며 각각에 대한 이해도를 키워야 할 것 같다.

 

 

지난 열혈자료구조 글에서 추상자료형 (Abstract Data Type) 가 무엇인지 지갑과 지갑의 기능을 들어 설명했었는데,

기억이 사라져 다시 글을 보고 왔다. 

 

typedef 지갑 {} 으로써 단순 C 언어적 측면에서 지갑 자료형을 정의할 수 있지만,

컴퓨터공학적인 측면에서는 지갑이라는 자료형을 구현하기 위해서 추상자료형(기능들의 나열)까지 정의해 주어야 한다. 

 

그렇다면 지갑 말고, 어떤 자료형이 있을까?

 

 

출처: 한국방송통신대학교

 

 

미리 정의된 자료구조는 프로그래밍 언어에서 제공되어 사용하는 것,

사용자 정의 자료구조는 개발자가 정의 및 추상화하여 사용하는 것이다.

 

다음 게시글부터 사용자 정의 자료구조에 있는 자료형들을 구현해 본다. 

 

출처 : 하나몬 개발자 일지

 

 

알고리즘을 구현할 때, 이러한 자료구조들로 데이터를 구조화 한다.

데이터를 어떤 자료구조형으로 구조화 하느냐는 알고리즘의 성능에 영향을 미친다.

알고리즘을 실행하는데 필요한 시간/공간의 복잡도로 알고리즘 성능을 분석할 수 있고, 알고리즘을 실제 실행하는데 걸린 시간으로 그 성능을 측정해 볼 수 있다. 

 

시간복잡도는 알고리즘 실행 횟수에 대한 함수로 그 경향을 봄으로써 예측해 볼 수 있고,

공간복잡도는 가변공간 + 고정공간의 합으로 계산한다.