알고리즘 쉽게 설명하고 이해하자-1 자료구조

알고리즘의 기본

참고서적 링크

알고리즘이란?

알고리즘(algorithm)은 계산이나 작업을 수행하는 순서를 말한다.

 

알고리즘과 프로그램 차이점

프로그램은 컴퓨터에서 실행하도록 컴퓨터가 이해할 수 있느느 언어로 작성한 것.

알고리즘은 프로그램을 작성하기 전에 사람이 이해할 수 있도록 작성한 것.

 

데이터 구조

 

테이터 구조란?

테이터의 순서와 위치 관계를 결정한다.

즉 데이터를 메모리에 저장할 때를 데이터 구조(자료 구조, data structure)라 한다.

 

전화번호부의 테이터 구조를 생각해보자.

이름과 전화번호	장점	두 방법의 장점을 조합
입력 순서대로 전화번호를 추가하는 경우	추가할 때 편함	가나다 첫 글자로 구분하여 표 작성
가나다 순서로 기록하여 관리하는 경우	검색할 때(찾을 때) 편함	가나다 첫 글자로 구분하여 표 작성

 

리스트

리스트는 데이터를 일직선으로 정렬한 데이터 구조를 말한다. 

테이터의 추가나 삭제는 쉬우나, 데이터에 접근하는 시간은 오래 걸린다.

기본적인 리스트의 경우 마지막 테이터는 포인터가 없지만 마지막 데이터의 포인트가 맨 앞의 데이터를 가르키게 하여 순환 리스트(원형 리스트)로 만들 수 있다. 

 

배열

배열은 데이터를 한 열로 연속해서 정렬하는 데이터 구조를 말한다.

리스트와 달리 특정 데이터에 접근할 때는 편리하지만, 추가 하거나 삭제할 때 시간이 오래 걸린다. 

메모리의 위치는 인덱스를 바탕으로 계산한다. 

 

리스트와 배열 표 정리하기

	접근	추가	삭제	키워드
리스트	느림	빠름	빠름	포인트
배열	빠름	느림	느림	인덱스

 

스택

후입선출 구조(Last in first out)를 말한다. 줄여서 LIFO 라고도 한다.

스택도 리스트와 배열처럼 일열로 저정하지만 추가와 삭제가 한쪽 끝에서만 이뤄진다.

중간에 있는 데이터에 접근하려면 해당 데이터가 맨 위에 놓을 때까지만 데이터를 팝(꺼내는 작업)해야 한다.

 

큐

선입선출 구조(First in First out)를 말한다. 줄여서 FIFO 라고도 한다.

큐도 스택 처럼 데이터를 조작하는데 위치가 제한되어 있다. 

스택은 같은 쪽에서 데이터를 추가 삭제하지만 스택은 추가하는 쪽과 삭제하는 쪽이 반대이다.

스택은 푸시와 팝이라고 하는데, 큐는 인큐와 디큐라고 한다. 

해시 테이블

해시테이블은 키와 값을 하나의 짝으로 저장하는 데이터 구조이다. 

일반적으로 키는 데이터의 식별자이며, 값은 데이터의 내용이라고 생각하자.

해시테이블은 해시 함수를 사용하여 배열 내 데이터에 빠르게 접근한다. 

해시값이 충돌하더라도 리스트를 사용하여 유연하게 대응이 가능하다.

 

힙

힙에서는 노드에 데이터를 저장한다.

데이터를 자유롭게 추가하지만 꺼낼 때는 항상 가장 작은 데이터를 꺼낸다.

보관중인 데이터의 최소값을 찾아야 할때 힙이 유용하며 다익스트리 알고리즘에서 힙을 유용하게 사용한다.

이진 탐색 트리

 

참고서적

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."