Java 자료구조 - 자료구조와 알고리즘 개요
프로그램 = 자료구조 + 알고리즘 (예) 최대값 탐색 프로그램 = 배열+ 순차탐색
자료구조
자료구조란?
일련의 동일한 타입(숫자타입, 패턴이 정해져있는 문자의 조합(날씨, 시간 등))의 데이터를 정돈하여 저장한 구성체.
자료 연결리스트, 해시 테이블, 맵, 스택, 큐 등
- 자료구조 분류 기준 :
- 순서
- 중복된 데이터
- 검색 효율성
- 수정 효율성
-
데이터 정리정돈 목적 : 프로그램에 저장하는 데이터에 대해 탐색, 삽입, 삭제 등 연산을 효율적으로 수행.
- 자료구조를 설계할 때에는 데이터와 데이터에 관련된 연산들을 함께 고려해야 한다.
- 자료구조의 기본 연산
- 생성 : Creating
- 삽입 : Insertion
- 삭제 : Deletion
- 제거 : Removing
- 검색 : Searching
- 순회 : Traversing
- 정렬 : Sorting
- 병합 : Merging
알고리즘
알고리즘이란?
어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것,
계산을 실행하기 위한 단계적 절차를 의미한다. [나무위키]
-
생활속 알고리즘의 예시 <잠자기 알고리즘=""> : 폰을 내려놓는다. -> 불을 끈다. -> 침대에 눕는다. -> 이불을 덮는다. -> 안경을 벗는다 -> 눈을 감는다.
- 알고리즘 분류 기준 :
- 입력된 데이터의 크기에 따라 연산량이 어떤 경향으로 늘어나는가
- 공간, 시간 복잡도
- 어떤 자료구조를 이용하여 구현했는가
- 이상적인 알고리즘 : 최소한의 시간, 공간에서 효율적으로 처리하는 알고리즘.
Big-O 표기법
서로다른 두 알고리즘을 비교하기 위해서, 즉 누가 더 성능이 좋은지 판단하기 위해서는 무엇을 기준으로 측정해야할까?
-
프로그램의 실행 속도를 비교한다.
이 방법은 환경마다 (Ex. 컴퓨터 세팅차이, 운영체제, 디바이스) 다르기때문에 적절하지 않다. -
BigO 표기법을 사용한다.
객관적으로 알고리즘의 성능을 표현할 수 있다.
알고리즘의 효율성을 측정하기 위함.
컴퓨터의 성능(환경)에 의존적이지 않고, 기준이 명확함.
BigO 표기법을 이용한 알고리즘 성능 측정 과정
- 1단계 : 대략적인 계산
수행되는 연산(산술, 비교, 대입 등)의 개수를 대략적으로 판단한다.
public int Add(int N)
{
return N+N;
}
// 대략적인 연산 개수 : 1
public int Add2(int N)
{
int sum = 0;
for(int i=0; i<N; i++)
{
sum += i;
}
return sum;
}
// 대략적인 연산 개수 = N
- 2단계 : 제일 큰 차수만 남기고, 계수는 지운다.
- 제일큰 차수만 남긴다.
- 상수항과 앞에 붙은 계수는 지운다.
O(1 + N + 4*N^2 + 1)
= O(4*N^2) = O(N*2)
O(1)
대입, 산술, 비교를 한 번 할때를 연산 1회로 생각한다.
// 대입
int a = 0;
int b = 2;
// 산술
a += 3;
// 비교
if(a>b) {
}
O(N)
1차원 정수 배열안에 놓인 모든 값을 더하여 출력하는 알고리즘
int[] arr = new int[5];
int sum = 0;
// O(N)
for(int i=0; i<arr.length; i++) {
sum = arr[i];
}
O(Log2(N))
업다운 게임은 숫자 1~100 사이에서
상대방이 생각하는 숫자를 맞추는 게임이다.
상대방이 생각하는 숫자가 35라고하면,
나 : 75 ?
상대 : 다운!
나 : 16 ?
상대 : 업!
나 : 36 ?
상대 : 다운!
나 : 31 ?
상대 : 업!
나 : 35..?
상대 : 정답!
이렇게 상대가 생각한 숫자가 내가 말한 수보다 작으면
상대방은 ‘다운’이라고 말하고, 크면 ‘업’이라고 말하여 상대의 숫자를 맞추는 게임이다.
내가 말하고 싶은 숫자를 하나씩 말해보면서 정답을 맞추기보다는 규칙적으로
찾아보면 수월할 것이다.
우리가 해볼 방법은 이진 탐색이다. 이 방법에 대해서는 추후에 구체적으로 알아보자.
상대방이 생각하는 숫자를 N 이라하고, 우리가 말할 값은 K라고하자.
1) K는 상대방이 생각하는 숫자가 있을거라고 생각되는
범위의 중앙값이다. (범위의 크기가 홀수라면 중앙값 - 1)
2) 만약 N<K (or N>K) 이라면 N보다 작은 값 (or N보다 큰값)들
사이에 N이 있다고 말할 수 없다.
따라서 N보다 큰값 (or 작은 값) 들이 우리가 N이 있을 범위라고 생각할 수 있다.
업다운 게임에서는 데이터 개수가 100이였다. 만약 데이터 개수를 N 이라하자.
데이터를 절반씩 나누어서 N = 1 or 1에 가까운 수가 될 때까지 나누는 ‘연산횟수’를 X 라고 하면
N/2^X = 1
N=2^X
X = Log2(N)
Big O 표기법의 종류와 예시
| 종류 | 예시 |
|---|---|
| O(1) | 스택:push, pop/큐:enqueue,dequeue,peek |
| O(log2(N)) | 이진트리 |
| O(N) | 반복문 |
| O(Nlog2(N)) | 퀵 정렬, 병합 정렬, 힙 정렬 |
| O(N^2) | 이중 for문, 삽입정렬, 버블정렬, 선택정렬 |
| O(2^n) | 피보나치 수열 |
Big O 표기법의 의의
‘이 함수가 정확히 몇개의 연산을 한다’ 가 중요한 것이 아닌,
‘데이터가 늘어남에 따라 어떤식으로 연산량이 증가하는가?’ 이다.
참고자료 : 자료구조와 알고리즘 그리고 코딩테스트? 드림코딩 by 엘리 https://www.youtube.com/watch?v=okHGRlgR8ps
“Rookis” 님의 “[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘”
댓글남기기