Java & Spring (23) 썸네일형 리스트형 [JAVA / 알고리즘] - 이진 탐색 이진 탐색 (Binary Search) 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방식으로, 찾으려는 값과 중앙 값을비교하는 방식이다. 이때, 찾으려는 값이 중앙 값 보다 더 작으면 왼쪽부분에서 이진 탐색, 찾으려는 값이 중앙 값 보다 더 크면 오른쪽 부분에서 이진 탐색을 진행한다. 알고리즘 시간 복잡도 : O(logn) [JAVA / 알고리즘] - 정렬 정렬 데이터를 원하는 기준으로 순서대로 배치하는 방법으로 구현 버블 정렬 (Bubble Sort) 인접한 데이터를 비교하면서 위치를 바꾸는 방식 알고리즘 복잡도 : O(n²) 삽입 정렬 (Insertion Sort) 앞의 데이터를 정렬하면서 삽입 위치를 찾아 정렬하는 방식 알고리즘 복잡도 : O(n²) 1번 인덱스부터 시작 앞쪽 데이터들이랑 비교해서 작으면 변경 선택 정렬 (Selection Sort) 최소 or 최대 값을 찾아서 가장 앞쪽이나 뒤쪽부터 정렬하는 방식 (최소값을 찾아서 가장 앞쪽부터 정렬 or 최대값을 찾아서 가장 뒤쪽부터 정렬) 알고리즘 복잡도 : O(n²) 합병 정렬 (Merge Sort) 배열을 계속해서 분할하여 길이가 1이 되도록 만들어주고, 인접한 부분끼리 정렬하면서 합병하는 방.. 이진 탐색 트리 이진 탐색 트리를 중위 순위로 나열하면 오름차순이 된다. 이진 탐색 트리 - 탐색 루트 노드부터 시작하여 데이터를 찾음 찾는 데이터가 없으면 null 반환 어떤 데이터를 찾던지 최대 트리 높이 만큼 탐색이 이루어짐 이진 탐색 트리 - 삽입 루트부터 비교 시작 ( 중복 키 발견시 노드 추가하지 않고 종료) 이진 탐색 트리 - 삭제 1. 삭제 대상 노드가 Leaf 노드인 경우 삭제 대상 노드 삭제 부모 노드의 해당 자식 링크 null로 변경 2. 삭제 대상에 자식 노드가 하나 있는 경우 자식 노드를 삭제 대상 노드의 부모 노드에 연결 삭제 대상 노드 삭제 3. 삭제 대상에 자식 노드가 둘인 경우 - 1) 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택 - 2) 삭제 대상 노드의 오른쪽 서브 트리에서.. [JAVA] - 힙 (Heap) 힙(Heap) 완전 이진 트리 형태이며, 최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조이다. 완전 이진 트리는 마지막 레벨을 제외한 모든 노드가 채워져 있어야 하고, 모든 노드들은 왼쪽부터 채워져 있어야 한다. 최소 힙 (Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 최대 힙 (Max Heap) 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태 표준적으로 트리구조는 특정 인덱스에 바로 접근할 수 있는 배열로 구현되고 있다. 일반 배열과는 다르게 시작 인덱스인 root는 0이 아닌 1부터 시작한다. 그리고 각 노드와 대응되는 배열의 인덱스는 변하지 않는다. 배열로 구현한 성질 1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 2. 오른쪽 자식 노드 인덱스 =.. [JAVA] - 데크 (Deque) 데크 (Deque) 스택 (Stack)과 큐 (Queue)를 합친 형태로 양쪽에서 삽입과 삭제가 모두 가능한 자료구조이다. (Deque : Doubly-ended Queue) 데이터를 앞쪽에 넣고 뒤쪽에서 빼면 큐 (Queue), 데이터를 앞쪽에 넣고 앞쪽에서 빼면 스택 (Stack)과 같다. 데크에서 한쪽의 입출력을 제한할 수 있는데, 한쪽의 입력을 제한한 데크를 입력제한 데크 (Scroll)라고 하며, 한쪽의 출력을 제한한 데크를 출력제한 데크 (Shelf)라고 한다. 데크 공간 : 데이터가 존재할 수 있는 공간 front : 데크 공간의 맨 앞부분 rear : 데크 공간의 맨 마지막 부분 데크 (Deque) 사용법 및 주요 메서드 import java.util.ArrayDeque; import ja.. [JAVA] - 큐 (Queue) 큐 (Queue) 먼저 들어온 데이터가 가장 먼저 나가는 구조로 선입선출 (First In First Out; FIFO) 자료구조라 불린다. 데이터가 입력된 순서대로 계산이 필요한 경우 사용된다. (프린터 출력 대기열, 너비 우선 탐색 - BFS 등) 쉽게 이해하려면 은행 창구 앞에서 번호표를 뽑고 먼저 뽑은 사람먼저 상담을 진행하는 경우를 생각하면 될 것 같다. 큐 공간 : 데이터가 존재할 수 있는 공간 Front : 큐 공간에서 데이터가 처음으로 들어가는 부분, 큐 공간의 맨 앞 부분 Rear : 큐 공간에서 데이터가 마지막으로 들어갈 수 있는 부분, 큐 공간의 맨 뒷 부분 Dequeue : 데이터가 꺼내지는 동작 Enqueue : 데이터가 삽입되는 동작 큐 (Queue) 사용법 및 주요 메서드 im.. [JAVA] - 스택(Stack) 스택 (Stack) 마지막에 들어온 데이터가 가장 먼저 나가는 구조로 후입선출(Last In First Out : LIFO) 자료구조라 불린다. 이 특성으로 인해 데이터가 입력된 역순으로 계산이 필요한 경우 사용된다. (수식 계산, 인터럽트 처리, 함수 콜 스택 등) 쉽게 이해하려면 상자 안에 물건을 하나씩 넣거나 빼는 경우를 생각하면 될 것 같다. 스택 공간 : 데이터가 존재할 수 있는 공간 Bottom : 스택에 처음으로 삽입된 데이터 Top : 스택에 마지막으로 삽입된 데이터 스택 (Stack) 사용법 및 주요 메서드 import java.util.Stack;// Stack 클래스 import Stack stack = new Stack();// Stack 선언 위와같이 Stack 클래스를 impor.. [JAVA] - 문자열 String 타입 String 문자열을 다루는 class로 참조 자료형이다. (※참조 자료형 : 객체에 주소값을 가지고 있고 해당 객체에 값이 있는 형태) // 1. String 타입 변수 선언, 변수에 값 대입 String name; name = "임동현"; // 2. String 타입 변수 선언과 동시에 값 대입 String age = "26"; 위와 같이 String 변수를 생성하고, 변수에 값을 대입하면 문자열은 String 객체로 생성되고, 객체의 번지가 대입된다. JAVA에서는 문자열 값이 동일하면 String 객체를 공유하도록 설계가 되어있어, 새로 생성한 String 변수에 선언해 준 값이 이전에 선언했던 값이라면 아래와 같이 동일한 String 객체의 번지가 저장된다. String name1 = "임동현".. [JAVA] - JAVA의 구조 및 동작 원리 JAVA는 프로그램을 JVM에서 실행시키기 때문에 운영체제에 따라 코드를 다시 작성하지 않고 바로 사용할 수 있는 독립적인 특징을 가지고 있다. JVM JAVA 어플리케이션을 실행하는 가상 머신이다. JDK JAVA 어플리케이션을 개발하기 위해 필요한 도구를 제공해주는 JAVA 개발 환경이다. 자바 컴파일러(javac)와 어셈블리어(javap) 등이 있다. JRE JVM, 라이브러리, JAVA 어플리케이션 실행에 필요한 파일들을 포함하고 있는 JAVA 실행 환경이다. 동작 원리 JAVA 소스코드를 작성하면 .java의 확장자를 가진 파일이 생기게 되고, 자바 컴파일러는 JAVA 소스코드를 컴퓨터가 이해할 수 있는 언어로 번역해준다. 이 과정을 컴파일(javac 명령어)이라고 하며 .calss확장자를 만들.. [JAVA] - StringBuilder 대부분 문자열을 사용하게 되면 String을 사용한다. String은 불변 객체로 한번 생성된 String 객체는 변경이 불가능하다. 이런 String 객체들을 하나로 합치고 싶으면, 합치고자 하는 String 객체들을 더해서 새로운 객체에 합쳐지는 방식인데, 더하는 과정에서 메모리 할당과 해제가 발생하여 성능이 비교적 떨어진다. 이런 성능저하 문제를 해결하기 위해 비교적 부하가 적은 StringBuilder를 쓴다고한다. 간단한 예제를 작성하여 사용을 해보겠다. public class MyClass { public static void main(String args[]) { String A = "example"; String B = "test"; // StringBuilder 객체 선언 StringBu.. 이전 1 2 3 다음
