๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ’ปTech/โ˜•Java

[Java] ์ž๋ฃŒ๊ตฌ์กฐ,์•Œ๊ณ ๋ฆฌ์ฆ˜ ์šฉ์–ด/๊ฐœ๋… ์ •๋ฆฌ

by _viper_ 2019. 6. 20.
๋ฐ˜์‘ํ˜•

์ž๋ฃŒ๊ตฌ์กฐ,์•Œ๊ณ ๋ฆฌ์ฆ˜ ์šฉ์–ด/๊ฐœ๋… ์ •๋ฆฌ

 

์ž๋ฃŒ๊ตฌ์กฐ

  • ์ฝ”๋“œ์ƒ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ๋ฐ์ดํ„ฐ๋ฅผ ๊ตฌ์กฐํ™” ํ•œ ๊ฒƒ

 

์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ์–ด๋–ค ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ์ ˆ์ฐจ ๋˜๋Š” ๋ฐฉ๋ฒ•

 

๋ฐฐ์—ด(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;
	}

}