[Java] 자료구조,알고리즘 용어/개념 정리

---

자료구조,알고리즘 용어/개념 정리

 

자료구조

• 코드상에서 데이터를 효율적으로 처리하기 위해 데이터를 구조화 한 것

 

알고리즘

• 어떤 문제를 해결하기 위한 절차 또는 방법

 

배열(Array)

• 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

 

큐(Queue)

• 먼저 넣은 데이터를 먼저 꺼낼 수 있는 데이터 구조 (FIFO, LILO)  

 

스택(Stack)

• 나중에 넣은 데이터를 먼저 꺼낼 수 있는 데이터 구조 (FILO, LIFO)

 

링크드리스트(LinkedList)

• 떨어져 있는 데이터를 포인터로 연결해서 관리하는 데이터 구조
• LinkedList
  • LinkedList는 데이터와 다음 노드의 주소를 가지고 있는(포인터) 구조
  • ArrayList와 같이 데이터의 추가,삭제시 불필요한 데이터의 복사가 없어 데이터의 추가,삭제 유리
  • 데이터의 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
  • 데이터가 많을 수록 접근성이 떨어짐
• ArrayList
  • ArrayList는 데이터의 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사 하는 방법을 사용
  • 대량의 자료를 추가/삭제 하는 경우에는 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하 
  • 반면 각 데이터는 인덱스를 가지고 있기 때문에 한번에 참조가 가능해 데이터의 검색에는 유리한 구조
  • 비효율적인 메모리 사용
• ArrayList/LinkedList 둘 다 데이터 공간을 배열처럼 미리 할당하지 않아도 됨

 

해쉬(Hash)

• Kye에 데이터를 매핑할 수 있는 데이터 구조 (Key, Value 형태)
• hashmap,hashtable 차이 (map 인터페이스를 구현한 클래스)
  • hashtable 동기화가 보장되는 map 계열의 클래스, null 값 허용 안함, 멀티 쓰레드 사용 적합
  • hashmap 동기화가 보장되지 않는 map 계열의 클래스, null 값 허용, 멀티 쓰레드 사용 부적합
      

힙(Heap)

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리

 

트리(Tree)

• Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 이진트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
  
  

BFS(너비우선탐색)

• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식, Queue로 구현
    

DFS(깊이우선탐색)

• 정점의 자식들을 먼저 탐색하는 방식, Stack으로 구현
    

Greedy(탐욕) 알고리즘

• 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

---

main

	public class MainProcess {

		public static void main(String[] args) {
			ArrayList<Integer> data = new ArrayList<Integer>();
			for (int i=0; i<100; i++) {
				data.add((int)(Math.random()*100));
			}
			System.out.println("MergeSort result : " + MergeSort.mergeSplitFunc(data));
			System.out.println("QuickSort result : " + QuickSort.sort(data));
			System.out.println("factorial result : " + factorial(5));
			binarySearch(11, quickSort(data));
		}
	}

factorial

	public static int factorial(int num) {
		if (num > 1) {
			return num * factorial(num - 1);
		} else {
			return num;
		}
	}

quicksort

import java.util.ArrayList;
import java.util.Arrays;

public class QuickSort {

	public QuickSort() {
		// TODO Auto-generated constructor stub
	}
	
	public static ArrayList<Integer> sort(ArrayList<Integer>dataList) {
		if(dataList.size() <=1 ) {
			return dataList;
		}
		int pivot = dataList.get(0);
		
		ArrayList<Integer> leftArr = new ArrayList<Integer>();
		ArrayList<Integer> rightArr = new ArrayList<Integer>();
		
		for(int index = 1; index < dataList.size(); index++) {
			if(dataList.get(index) < pivot) {
				leftArr.add(dataList.get(index));
			} else {
				rightArr.add(dataList.get(index));
			}
		}
		
		ArrayList<Integer> mergedAll = new ArrayList<Integer>();
		mergedAll.addAll(sort(leftArr));
		mergedAll.addAll(Arrays.asList(pivot));
		mergedAll.addAll(sort(rightArr));
		
		return mergedAll;
		
	}

}

binarysearch

    private static void binarySearch(int key, List<Integer> list) {
        int mid;
        int left = 0;
        int right = list.size() - 1;

        while (true) {
            if (right >= left) {
                mid = (left + right) / 2;

                if (key == list.get(mid)) {
                    System.out.println(key + " is " + mid + "th index.");
                    break;
                }

                if (key < list.get(mid)) {
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }

            }else if(right < left){
                System.out.println(key + " is not found.");
                break;
            }
        }
    }

mergesort

import java.util.ArrayList;

public class MergeSort {
	public MergeSort() {
		// TODO Auto-generated constructor stub
	}
	
	public static ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList) {
		if (dataList.size() <= 1) {
			return dataList;
		}
		int medium = dataList.size() / 2;

		ArrayList<Integer> leftArr = new ArrayList<Integer>();
		ArrayList<Integer> rightArr = new ArrayList<Integer>();
		leftArr = mergeSplitFunc(new ArrayList<Integer>(dataList.subList(0, medium)));
		rightArr = mergeSplitFunc(new ArrayList<Integer>(dataList.subList(medium, dataList.size())));

		return mergeFunc(leftArr, rightArr);
	}

	public static ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList, ArrayList<Integer> rightList) {
		ArrayList<Integer> mergedList = new ArrayList<Integer>();

		int leftPoint = 0;
		int rightPoint = 0;

		// CASE1 : left,right 둘 다 있을 때
		while (leftList.size() > leftPoint && rightList.size() > rightPoint) {
			if (leftList.get(leftPoint) > rightList.get(rightPoint)) {
				mergedList.add(rightList.get(rightPoint));
				rightPoint += 1;
			} else {
				mergedList.add(leftList.get(leftPoint));
				leftPoint += 1;
			}
		}

		// CASE2 : right 데이터 없을 때
		while (leftList.size() > leftPoint) {
			mergedList.add(leftList.get(leftPoint));
			leftPoint += 1;
		}

		// CASE3 : left 데이터 없을 때
		while (rightList.size() > rightPoint) {
			mergedList.add(rightList.get(rightPoint));
			rightPoint += 1;
		}
		
		return mergedList;
	}

}