IT 지식/자료구조
Deque를 통해 버킷정렬(Bucket Sort)을 해보자.
저번시간에 만들었던 Deque를 사용하여 버킷정렬을 연습해보기로 했다. 우선 버킷정렬이 무엇인지 알아보자. 버킷정렬(Bucket Sort) 이란?? n개의 데이터를 정렬할 때 같은 크기의 간격을 갖는 n개의 버켓에 데이터를 분배한다. 입력 데이터가 균일하게 분포되었다면 각 버켓에는 1개의 데이터가 있게 되지만, 균일하게 분포되지 않으면 다수의 데이터가 버켓에 들어 갈 수 있으며 각 버켓의 데이터는 정렬하여 저장한다. n개의 모든 데이터를 버켓에 분배하였다면 버켓 번호 순으로 스캔하여 출력하면 정렬된 데이터를 얻게 된다. [예제] 최대 2자리를 갖는 정수 (0부터 99까지의 정수) 10개를 버켓 정렬한다고 하자. 각 버켓은 같은 크기의 간격 (0-9, 10-19, 20-29,…, 90-99)을 갖는 10개..
Deque를 직접 구현해보기
큐는 삽입과 삭제가 리스트의 한쪽 방향에서만 이루어지지만 deque는 리스트의 양쪽 끝 모두에서 이루어질 수 있다. 따라서 양쪽 방향 모두 삽입과 삭제가 이루어질 수 있으므로 기존의 큐나 스택으로 사용할 수 있어 유연하게 사용할 수 있다. 사진출처 : https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/ 이런 Deque를 직접 구현해 보자. 우선 Deque의 기능을 정리한 인터페이스이다.1234567891011121314151617181920212223package practice3; public interface Deque { public void addFirst(T item); public void addLast(T item); public..
Stack을 이용한 문장 완성도 판별 프로그램
개발을 진행하다보면 기본에 대해 잊어갈때가 있다. 잊지 않기위해 오늘 부터 매주 하나씩 자료구조를 이용한 문제를 풀어봐야겠다. 오늘은 Stack 첫번째 시간으로 문장의 완성도를 확인하는 프로그램을 작성하여 보자. [제약사항] - {[(에 대한 괄호들이 정상적으로 닫혀있어야 한다. - 주석 //, /* 안에 포함된 내용은 무시한다. - "" double quote에 들어있는 내용을 무시한다. 간단한 프로그램이라 설명은 생략한다. - Text를 읽고 판별을 진행하는 Main 클래스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686..
Stack - 후위 표기법으로 된 식 계산
1 3 + 4 * 와 같이 후위 표기되어있는 식을 계산하는 프로그램을 stack을 이용해서 만들어라 주의사항 - 피연산자가 너무 많으면 오류를 발생시켜라. - 피연산자가 적어도 오류를 발생시켜라 - 연산자가 사칙연산 이외의 것이 나오면 예외를 발생시켜라 - 결과는 소수점 둘째까지 반올림해서 표현하라. - 예외는 이 프로그램을 위한 예외를 새로 만들어라 구성 - 파일을 읽는 메서드가 담긴 util 클래스 - 동작이 진행되는 Main 클래스 - 이 프로그램의 예외 OperatorException 클래스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626..