꾸준히 개발하자

정렬 알고리즘이란? 정렬은 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말합니다. 1) 정렬 알고리즘의 안정성 만약 학번순으로 나열된 성적들의 배열이 있다고 하자. 이를 성적순으로 정렬했을 때 성적이 같은 값들이 학번순으로 정렬했던 것이 유지가 되면 안정된 정렬이라 하고 반드시 학번순으로 정렬되지 않는 정렬을 안정되지 않은 정렬이라고 한다. 2) 내부 정렬과 외부 정렬 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘이다. 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘이다. 3) 정렬 알고리즘의 핵심 요소 정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입으로 대부분의 정렬 알고리즘은 이 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 17. 04:14

하노이의 탑 1. 하노이의 탑 문제 알아보기 하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수는 없다. 2. 문제 푸는 알고리즘 짜기 우선 2개의 원반을 옮긴다고 생각해보자. 맨 위의 원반을 중간 기둥에 옮기고, 맨 아래 원반을 목표 기둥에 옮기고, 중간 기둥에 옮겨놨던 맨 위의 원반을 목표 기둥에 옮기면 완성된다(기둥 3개를 시작 기둥, 중간 기둥, 목표 기둥으로 부르자). 이번엔 3개의 원반을 옮긴다고 생각해보..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 13. 09:29

재귀 알고리즘 재귀란 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 한다. 재귀 알고리즘의 예시 1. 팩토리얼 구하기 팩토리얼은 본인을 포함해 본인보다 작은 자연수의 값을 다 곱한 값을 말한다. 그리고 0! = 1 로 정의 된다. 예를 들어 7!이 있으면 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 이되고 이는 7 * 6!과 같다. 이를 이용해 팩토리얼 구하는 알고리즘을 짜보자. static int factorial(int n){ if( n > 0) return n * factorial(n-1); // 재귀 호출 else return 1; // n=0 이면 0!=1 return } 다음과 같이 재귀를 이용하면 간단하게..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 13. 06:19

링 버퍼 앞선 게시물에서 큐를 구현할 때 링 버퍼를 사용했다. 링 버퍼는 배열의 끝과 끝을 연결해서 원형 배열을 만들었다고 생각하면 이해하기 쉽다. 그래서 보통 크기가 n인 배열을 순서대로 읽으면 index 0의 값, index 1의 값 ... index n-1의 값 이렇게 n개를 읽고 나면 끝난다. 하지만 링 버퍼에서는 index n-1 다음에 index 0이 이어진 개념이기 때문에 순서대로 읽으면 index 0의 값, index 1의 값 ... index n-1의 값, index 0의 값, index 1의 값 이런 식으로 계속 읽어낼 수 있다. 그렇다면 어떻게 링 버퍼를 구현할 수 있는가? 사실 그냥 배열을 쓰는 것은 일반적인 배열과 같다고 볼 수 있다. 하지만 요소값을 읽는 과정에서 차이가 발생한다..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 11. 12:02

스택(Stack) 이란? 스택이란 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출 (LIFO : Last In First Out)이다. 배열로 스택을 구현하기 배열로 스택을 구현해보면 훨씬 알기 쉬울 것이다. 우선 IntStack이라는 Class를 통해 스택의 구조를 알아보자. class Intstack{ // int형 고정 길이 스택 int[] stk; // 스택을 구현하기 위한 배열 int capacity;// 스택 크기 int ptr; // 스택 포인터 Intstack(int max){ ptr = 0; capacity = max; try{ stk = new int[capacity]; // 스택 본체용 배열 생성 }catch (OutOfMemoryError e){ //..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 10. 22:24

제너릭스 (Generics) 제너릭스는 처리 대상의 자료형에 의존하지 않도록 클래스 혹은 인터페이스를 구현하는 기능이다. 즉 제너릭 클래스(인터페이스)는 자료형 문제로부터 자유롭고 안전하다. 형식은 클래스(인터페이스) 이름 바로뒤에 형식의 매개변수를 붙여 선언한다. - class 클래스 이름 {/* ... */} (만약 매개변수가 여러개면 {/*...*/} - interface 인터페이스 이름 {/* ... */} 다음과 같이 매개변수의 이름을 작성하기 위해서는 규칙이 있다. 1) 대문자는 1개를 사용한다.(소문자는 가급적 사용x) 2) 컬렉션(collection) 내부 요소의 자료형은 element의 머리글자인 E를 사용한다. (컬렉션은 자바에서 제공하는 기본 자료구조를 모은것을 말한다.) 3) 맵(M..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 9. 23:13

Import 선언 Java에서 클래스나 인터페이스 등의 자료형(type)은 반드시 어떤 패키지에 소속되어있다. 예를 들면 Scanner 클래스와 Random 클래스가 소속된 곳은 java.util 패키지이다. 원래라면 클래스나 인터페이스등을 사용하고 싶을 때 패키지이름을 포함한 클래스 혹은 인터페이스를 적어서 사용해야한다. 하지만 매번 그렇게 쓰면 비효율적이기 때문에 맨 위에 import 선언을 이용해 한번만 패키지명을 포함한 클래스 혹인 인터페이스 선언한다. 이렇게 되면 다음부터는 클래스 혹은 인터페이스이름만으로 사용이 가능해진다. Java.lang 패키지 위와 같이 import선언으로 충분이 효율적이게 됐지만 Java는 더욱 더 편한 기능을 제공한다. Java 프로그래밍에 필요한 가장 기본적인 클래스..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 9. 18:02

검색 알고리즘 고르는 법 배열에서 검색을 하는 경우 보통 검색 속도가 빠른 알고리즘을 선택한다. 하지만 검색과 더불어 데이터를 추가, 삭제하는 작업이 필요한 경우 데이터의 추가, 삭제에 필요한 비용도 고려하여 알맞은 알고리즘을 골라야 한다. 따라서 어떤 목적을 이루기 위해 알고리즘을 선택한다면 종합적인 요소를 잘 고려해서 선택해야 한다. 선형 검색 선형 검색이란 원하는 값을 찾을 때까지 맨 앞부터 순서대로 검색하는 방법이다. while문으로 구현하면 다음과 같다. public class Main { static Integer line(int key, int[] a){ int i = 0; while(true){ if(i==a.length) return -1; // i가 a의 index를 넘어선 경우 검색 ..

자료구조와 알고리즘/자료구조, 알고리즘 2023. 1. 9. 17:36