본문 바로가기

알고리즘/실전 (10)

반응형
알고리즘/실전

[알고리즘] JAVA 큐(Queue) 알고리즘

- FIFO(First-In-First-Out) 선입선출 구조 (먼저 들어간 것이 먼저 나간다) - 대표적인 예 : 은행 창구(먼저 번호표 뽑은 사람이 먼저 서비스를 받음) 자바로 구현한 소스 코드 package com.company; interface Queue { boolean isEmpty(); boolean isFull(); void enqueue(char item); char dequeue(); char peek(); void clear(); } class Main implements Queue{ private int front; private int rear; private int queueSize; private char queueArr[]; public Main(int queueSize) ..

2020. 2. 19.
알고리즘/실전

[알고리즘] 실제 스택(Stack)사용 예제 자바(JAVA)

웹 방문 기록을 스택에 쌓아두는 예제입니다. 이전 : pop 앞 : push Browser.class package com.company; import java.util.Stack; class Browser { public Stack back; //이전 방문 기록 public Stack forward; //다음 방문 기록 public Browser() { this.back = new Stack(); this.forward = new Stack(); } //주소를 입력하면 웹사이트 방문 public void goUrl(String url) { System.out.println(url + " 접속함"); back.push(url); } //방문기록 확인하기 public void histroy() { if(!..

2020. 2. 19.
알고리즘/실전

[알고리즘] JAVA 스택(Stack) 알고리즘

스택(Stack) - 자료구조 중 하나 - LIFO(Last-In-First-Out)의 후입 선출구조 - 대표적인 예 : 브라우저, 후위표기의 수식 계산, 하이노탑 push : 데이터 삽입 pop : 데이터 삭제 peak : top이 가리키는 데이터를 읽는 작업 Stack 클래스 package com.company; public class Stack { private int top; private int maxSize; private Object[] stackArray; //스택 생성, 스택의 최대 크기로 생성 public Stack(int maxSize) { this.maxSize = maxSize; this.stackArray = new Object[maxSize]; this.top = -1; // ..

2020. 2. 19.
알고리즘/실전

[알고리즘] JAVA 계수 정렬 (Counting Sort) 알고리즘

- '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 - 계수 정렬의 시간 복잡도는 O(N) - 기존의 정렬 알고리즘은 위치를 바꾸는 것이고, 이번 계수 정렬은 '크기를 기준'으로 개수만 세우면 되기 때문에 위치를 변경할 필요가 없다. - 모든 데이터에 한 번씩 접근하면 되기 때문에 매우 효율적 문제 - 1, 3, 2, 4, 3, 2, 5, 3, 1 , 2, 3, 4, 4, 3, 5, 1, 2, 3, 5 ,2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1을 오름차순으로 나타내시오. 소스 코드 package com.company; public class Main { public static void main(String[] args) { int[] count = new int[6]; int ..

2020. 2. 17.
알고리즘/실전

[알고리즘] JAVA 힙 정렬 (Heap Sort) 알고리즘

힙 정렬은 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘 - 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법 힙 정렬을 알기 전에 이진 트리에(Binary Tree)에 대해 알고 있어야 한다. 이진 트리 - 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조 - 모든 노드의 자식 노드가 2개 이하인 트리 구조 완전 이진 트리(Complete Binary Tree) - 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리이다. 즉, 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 가득 찬 구조의 이진 트리이다. 힙 힙(Heap)은 최솟값이나 최대값을 빠르게..

2020. 2. 16.
알고리즘/실전

[알고리즘] JAVA 병합 정렬 (Merge Sort) 알고리즘

- 분할 정복 방법으로, 퀵정렬과 다르게 항상 시간 복잡도가 O(N*logN)을 보장 - 일단 반으로 나누고 나중에 합친다. → 피벗이 없는 이유 : 항상 반으로 나누기 때문 - 합치는 순간에 정렬 - 기존의 데이터를 담을 추가적인 배열 공간이 필요 → 메모리 낭비 문제 - 5, 3, 2, 6, 4, 7, 8, 1을 오름차순으로 나타내시오. - 정렬배열은 반드시 전역변수로 선언 소스 코드 package _38_midian; import java.util.Arrays; public class MergeSort { static int[] sorted = new int[8]; public static void merge(int a[], int m, int middle, int n) { int i = m; //..

2020. 2. 15.
알고리즘/실전

[알고리즘] JAVA 퀵 정렬 (Quick Sort) 알고리즘

- 퀵 정렬은 피봇값을 기준으로 분할정복하는 알고리즘이다. - 퀵 정렬의 평균 시간 복잡도는 O(N*logN)이다. - 퀵 정렬의 최악 시간 복잡도는 O(N^2)이다. 문제 - 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 나타내시오. - 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 소스 코드 package com.company; public class Main { private static int data[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; private static int number = 10; public static void quickSort(int[] data, int start, int end) { if (start >= end) { return; } ..

2020. 2. 15.
알고리즘/실전

[알고리즘] JAVA 삽입 정렬 (Insert Sort) 알고리즘

- 무조건 위치를 변경하는 선택 정렬, 버블 정렬과는 다르게 필요할 때에만 위치를 변경 - 시간복잡도는 선택 정렬, 버블 정렬과 같은 O(N^2)으로 비효율적 - 하지만, 데이터가 이미 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다. - 적절한 위치에 삽입하는 알고리즘 문제 - 다음 숫자들을 오름차순으로 정렬하시오. - 1, 10, 6, 8, 4, 2, 3, 5, 9, 7 소스 코드 package com.company; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int arr[] = new int[10]; for(int k=..

2020. 2. 13.
알고리즘/실전

[알고리즘] 버블 정렬 (Bubble Sort) 알고리즘 자바(Java)

- 바로 옆에 있는 값과 비교해서 더 작은 값을 앞으로 옮기는 방법 - "가장 비효율적" - 버블정렬의 시간 복잡도는 O(N^2); 선택정렬과 버블정렬의 시간복잡도는 같은데 왜 버블정렬이 가장 비효율적인지? - 버블정렬은 옆에 있는 숫자와 계속해서 비교해야하고 선택정렬은 한 번만 비교하면 된다. 문제 - 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. - 1, 10, 5, 9, 8, 3, 2, 6, 7, 4 소스 코드 package com.company; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int i,j, t..

2020. 2. 13.
알고리즘/실전

[알고리즘] JAVA 선택 정렬 (Select Sort) 알고리즘

선택 정렬은 가장 작은 것을 선택해서 맨 앞으로 옮기고 바꾸는 것을 의미한다. 굉장히 비효율적이고 빅오표기법으로 표기하면 O(N^2)이다. * 빅오 표기법 - 특정한 알고리즘의 수행시간을 간단히 표기 문제 - 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 3 2 9 10 5 8 7 6 4 소스 코드 package com.company; import java.util.Scanner; public class Main { public static void main(String[] args) { int arr[] = new int[10]; Scanner sc = new Scanner(System.in); for(int k=0; k

2020. 2. 13.
반응형