자료 구조와 알고리즘 : 기본적인 자료구조 7가지의 개념, 알고리즘 소개

자료구조와 알고리즘

프로그래밍에 있어 상황에 따라 다른 자료구조와 알고리즘을 사용해야 효율적이고 빠른 설계 가능!

배워서 직접 구현, 적용을 해보자!

자료구조 (데이터 구조)

자료구조를 잘 적용한다면 원하는 데이터를 더 빠르게 정렬과 검색이 가능하다.

속도를 빠르게 하면 메모리가 더 들고, 메모리를 더 적게 사용 하려면 속도가 느려지는 트레이드 오프가 존재.

이를 최소화하고 효율적으로 다루려면 자료구조가 필수!

1. 배열

데이터가 인덱스를 바탕으로 접근하는 일련의 연속적인 형태

생성 용이, 효율적 탐색 (인덱스 접근), 정렬 용이.

저장 메모리 크기 고정, 삽입과 삭제가 빈번할 때는 비효율적. (연결 리스트가 바람직)

테이블, 벡터, 행렬의 구현. 다른 데이터 구조에 사용 됨.

2. 스택

쌓음. 늦게 들어온 것이 먼저 나옴.

동적인 메모리 크기, 순서대로 정렬

마지막에 들어온 데이터만 처리 가능. 한번에 하나의 데이터만 처리 가능

가장 마지막에 입력된 것부터 순차적으로 처리하고 싶을 때, 브라우저의 뒤로 가기, 실행 취소, 재귀

3. 큐

줄세우기, 먼저 들어온 것이 먼저 나옴.

동적인 메모리 크기, 순서대로 정렬

처음 들어온 데이터만 처리 가능. 한번에 하나의 데이터만 처리 가능

반복적이고 자주 받는 데이터를 비동기적으로 처리 할 때 효율적, 순서에 민감한 데이터 처리, 먼저 입력 받은 데이터 처리.

4. 연결 리스트

데이터가 메모리의 주소로 연결된 일련의 형태, 한 방향의 Single Linked List, 양 방향의 Double Linked List가 존재

동적인 메모리 크기, 효율적 메모리 사용 (대용량 데이터 처리 적합), 수정과 추가가 효율적.

검색에 불리. 또한 배열에 비해 주소를 저장하기 때문에 메모리를 더 사용.

메모리 크기가 정해져 있지 않을 때, 삽입/제거등이 빈번하게 필요 할 때, 이미지 뷰어, 갤러리, 음악 플레이어 등

5. 해시 테이블 (해쉬 맵)

해쉬값 (key)와 value 쌍을 바탕으로 저장, key로 접근하는 형태

추가/ 삭제 용이, 빠른 검색

충돌 가능성 (입력된 키의 해시값이 이미 데이터가 저장된 곳을 가리킬 수있다.), 충돌로 인한 해시함수를 잘 다뤄야 함.

데이터 베이스 , 사용자 로그인 인증 등

6. 그래프

노드(데이터)와 노드를 연결하는 간선(edge)으로 구성된 형태. 연결되어 있는 객체의 관계를 표현한다.

지도, 지하철 노선도, 전기회로 소자, 도로, 선수과목 등

 

다양한 그래프 (무방향 그래프, 방향 그래프, 가중치 그래프, 연결 그래프, 비연결 그래프, 순환 그래프, 비순환 그래프 등)

네트워크 모델, 2개 이상의 경로 가능, 루트 노드라는 개념이 없음 (부모 자식 관계의 개념이 없음. 트리에는 있다.)

7. 트리

노드로 구성된 계층적인 그래프

트리의 종류 또한 다양.

트리 구조 용어

최상위 노드 (루트), parent node와 child node, depth, sibling 등

알고리즘

문제를 해결하는 절차. 입력이 주어지면 원하는 출력을 만드는 일련의 과정들.

특정 문제를 빠르게 해결하는 좋은 알고리즘이 많이 발견 됨. 이 것을 잘 익히자!

 

알고리즘의 요소 : 문제, 입력, 출력

문제를 정확하게 해석. 컴퓨터는 주어진 명령을 구체적이고 명료한 계산 과정을 통해 수행!

여러 방법 중 어느 방법이 더 좋은 지 판단 또한

입력 크기(메모리)와 계산 횟수(속도)는 수행 성능에 영향을 주는 것을 고려해야 한다.

 

알고리즘 개발 분석 요인

정확성 : 문제 설명 내용, 제안된 알고리즘 내용, 구현내용 등에 대한 정확성

작업량 : 입력 데이터 크기에 따른 알고리즘 실행 시간

사용 공간 : 입력 데이터 크기를 초과하는 추가 공간 (시스템 자원)

최적화 : 다른 알고리즘과 비교.