본문 바로가기

자바 알고리즘

자바로 구현하는 큐 (Queue) 큐(Queue) ? 큐(queue)는 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. Queue 의 과정 큐의 데이터 삽입, 추출 과정 큐에서 front 는 가장 먼저 큐에 들어온 첫번째 원소 이고, rear 는 큐에 가장 늦게 들어온 마지막 원소가 된다. 공.. 더보기
자바로 구현하는 퀵정렬 (Quick Sort) 알고리즘 퀵 정렬(QuickSort) 이란? 분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 왼쪽 부분 집합과 오른쪽 부분집합을 정렬 하는 방법 1. 전체원소 가운데 하나의 원소를 중심(Pivot)으로 2개의 부분 집합으로 분할 한다. 2. 기준값(Pivot) 보다 작은 원소는 왼쪽 부분집합으로, 기준값(Pivot) 보다 큰 원소들은 오른쪽 부분 집합으로 정렬한다. 3. 분할된 부분집합의 크기가 0이나 1이 될 때 까지 순환 호출을 이용하여 다시 분할 한다. 위 과정을 반복하는 것이 퀵정렬 입니다. 출처 - http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC C로 배우는 쉬운 자료구조 (한빛미디어) 서적의 수도코드 (pseudo code) 를 참고 하였으며, 서적.. 더보기
자바로 구현하는 선택정렬 (Selection Sort) 알고리즘 선택정렬이란? 제자리 정렬 알고리즘의 하나로, 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식 1. 주어진 원소중 최소값을 찾는다. 2. 그 값을 첫 번째 원소와 교환 한다. 3. 그 다음 작은 원소를 찾아 다음 위치의 원소와 비교하여 교환한다. 위 과정을 반복하는 것이 선택정렬 입니다. 출처 - http://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC 수도코드 예를들어, {80, 6, 2, 3, 1} 원소를 정렬하고자 하는 경우, (기준위치 를 빨간색, 최소값 위치 파란색으로 표시) 1단계 80 6 2 3 1 정렬후 : 1 6 2 3 80 2단계 1 6 2 3 80 정렬후 : 1 2 6 3 80 3단계 1 2 6 .. 더보기