프로그래밍/알고리즘
-
퀵 정렬 (Quick 정렬)프로그래밍/알고리즘 2018. 6. 19. 10:37
안녕하세요 오늘은 정렬 중 분할 정복으로 유명하고 빠른 정렬로 유명한 퀵 정렬에 대하여 공부해도록 하겠습니다출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC( 퀵 정렬을 간단히 나타낸 gif ) 먼저 간단한 예제를 통해서 무엇인지 알아보도록 하죠!!!위와 같은 배열이 있고 이를 퀵정렬로 정렬하기위해서는 어떻게 해야할까요? 먼저 퀵정렬의 특징은 pivot이라는 중간값을 선택하는 것부터 시작합니다 또한 이를 선택하는 방법에는 두가지가 있는데 1. 배열의 중간값 2. index의 첫번째 이중 1번째인 중간값을 선택한다고 했을때 Pivot의 값은 배열의 중간값인 9가 선택이 됩니다 다음 퀵 정렬은 다음과 같은 규칙에 의해서 정렬이 진행됩니다 1. ..
-
해시테이블이란?프로그래밍/알고리즘 2018. 6. 17. 22:31
해시테이블은 key와 value로 데이터를 저장하는 자료구조 중 하나입니다 (공간을 소모하여 시간을 얻는방법 혹은 가장 빠른 데이터를 검색하는 방식이라고도 부릅니다)출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ 각각의 객체는 고유한 주소값을 가지며 이를가지고 hash Function을 통해 이 값을 테이블에 넣어 저장하는 방식입니다 이를 해싱이라고 하며 해시테이블의 가장 큰 장점은 원하는 데이터를 바로 찾을 수있다는 점입니다 시간복잡도로는 O(N) ~ O(1)로 가능한데O(1)이 가능한 이유는 각각의 객체는 고유한 주소값을 가지고 이 주소값을 가지고 해싱한다면 똑같은 값을얻어 바로 원하는 key로 value에 접근이 가..
-
버블 정렬프로그래밍/알고리즘 2018. 6. 5. 20:22
지난 시간에는 선택 정렬에 대해서 알아봤습니다!!그렇다면 이번에는 또 다른 정렬 방법중 하나인 버블 정렬에 대하여 알아볼 계획입니다 먼저 버블 정렬이란?출처 : http://wonjayk.tistory.com/219 위의 사진과 같이 반복하는 정렬 방법입니다!!바로 옆의 Index와 값의 교환을 N번 까지 반복하는 간단한 정렬입니다 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int[] arr = new int[scanner.nextInt()]; for (int i = 0; i < arr.length; i++) { System.out.print(i + 1 + "번째 값 입력 : "); arr[i] = ..
-
경우의 수 출력하기프로그래밍/알고리즘 2018. 5. 22. 23:45
오랜만의 간단한 알고리즘 문제를 가지고 돌아왔습니다!! 문제)두개의 수를 입력받는다첫번째 입력 K에는 K의 수만큼 a를 출력하고두번째 입력 N에는 N의 수만큼 b를 출력하는데 규칙이 존재한다.a와 b의 우선순위에서는 ab의 순서로 출력이 되며 각각의 나올수 있는 경우의 모든 수를 출력한다. 예시) 입력- K : 2, N : 2출력 aabb abab abba baab baba bbaa 입력- K : 3, N : 2출력 aaabb aabab aabba abaab ababa abbaa baaab baaba babaa bbaaa 설명 먼저 K의 수만큼 a가 출력 되고 N의 수만큼 b가 출력됩니다.a와b가 출력 될수있는 모든 경우의 수가 출력이 되는데a와b의 우선순위는 a>b이기때문에 a부터 순서대로 b까지 출력..
-
KiwiJuice프로그래밍/알고리즘 2018. 5. 6. 09:54
오늘은 간단한 시뮬레이션 알고리즘 기초중 유명한 알고리즘인 키위주스 알고리즘을 풀어보도록 하겠습니다. 문제 타로는 맛있는 키위 주스를 준비했습니다. 타로는 맛있는 키위주스를 준비했습니다. 타로는 0부터 N-1이라 이름을 붙인 N개의 병에 키위주스를 넣었습니다. 이때 i번째의 병의 용량은 capaties[i] 리터이며 타로가 i번째 병에 넣은 키위 주스의 양을 bottles[i] 리터라고 합니다.타로는 병에 키위주스를 재분배하려고 하며, 0부터 M-1까지 M회 조작합니다.i번째의 조작은 타로가 병 fromId[i]부터 병 toId[i]에 키위 주스를 넣는 것을 의미합니다. 병 fromId[i]가 비어있거나 병 toId[i]가 꽉 차 있는 순간, 타로는 더 이상 키위 주스를 넣지 않습니다.N개의 요소를 가진..