백준8 [Algorithm] 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ■ 정의 - 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조 - 힙(heap)을 사용하여 정렬하는 알고리즘 · 힙(heap)이란?: '부모값이 자식값보다 항상 크다' 조건을 만족하는 완전이진트리 · 최대힙: 부모노드 값(key 값) ≤ 자식노드 값 (key 값) · 최소힙: 부모노드 값(key 값) ≥ 자식노드 값 (key 값) ■ 인덱스 관계 - 부모노드 인덱스: a[(i-1) / 2] - 왼쪽 자식노드 인덱스: a[i * 2 + 1] - 오른쪽 자식노드 인덱스: a[i * 2 + 2] ■ 힙 정렬 과정 Step 1. 최대 힙의 루트 노드를 마지막 배열 값과 교환, 가장 큰 값을 마지막 배열에 저장 후 힙에서 제거 Step 2. 다시 힙을 .. 2023. 4. 8. [자료구조] 스택(Stack) / 큐(Queue) 스택(Stack) ■ 정의 - 데이터를 일시적으로 쌓아 놓는 자료구조 - 데이터의 입력과 출력 순서는 후입선출 (LIFO: Last In First Out) ■ 메소드 Stack s = new Stack(); Stack s = new Stack(int capacity); // 스택의 capacity 결정 메소드 의미 push(int item) 스택에 데이터를 저장 pop() 스택의 꼭대기에 있는 데이터를 제거하고, 그 값을 반환 isFull() 스택이 empty 상태인지 확인 isEmpty() 스택이 full 상태인지 확인 clear() 스택의 모든 요소를 삭제 peek() 스택의 가장 최상위(마지막)에 위치한 데이터 출력 capacity() 스택의 용량 확인 (스택 전체 크기) size() 스택의 크기.. 2023. 2. 22. [Algorithm] 이진검색 (Binary search) 이진검색 (Binary search) ■ 정의 - 이진검색은 요소가 오름차순으로 정렬된 배열인 상태에서 검색하는 알고리즘 - 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색 - 리스트의 중간 부분에 찾는 원소가 있는지 확인, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색 하거나 중간부터 검색 ■ 사용 예 - 39를 찾는 과정 1. index 0과 10을 기준으로 2로 나눈 값 index 5를 살펴본다. 2. index 5의 값이 찾으려는 39보다 작으므로 index 5 이하는 더 이상 살피지 않는다. 3. index 6과 10을 기준으로 2로 나눈 값 index 8을 살펴본다. 4. index 8의 값이 찾으려는 39보다 크므로 index .. 2023. 2. 14. [JAVA] contains() / replace() contains() ■ 정의 - 문자열이 특정 문자열을 포함하고 있는지 확인한다. - boolean형이므로 포함하고 있으면 true를, 아니면 false를 반환한다. - 대·소문자, 공백을 구분한다. ■ 사용 예 public class contains { public static void main(String[] args) { // TODO Auto-generated method stub String str = "my name is jaein"; System.out.println(str.contains(" my"));//false System.out.println(str.contains("name")); //true System.out.println(str.contains("is")); //true Sy.. 2023. 2. 7. [JAVA] StringBuilder ■ 정의 - StringBuilder 클래스의 인스턴스는 그 값을 변경할 수 있고, 추가할 수 있는 가변객체(mutable) => 문자열을 바로 추가할 수 있으므로, 공간의 낭비도 없으며 속도도 매우 빨라짐. - 동기화 되어있지 않다. => StringBuffer에 비해 가벼움. 특별한 이유가 없다면 StringBuilder를 사용하는 것이 일반적. ■ 생성자 StringBuilder sb = new StringBuilder(); // 객체선언 StringBuilder sb = new StringBuilder("str"); // 문자열을 바로 넣을 수도 있음 ■ 메소드 종류 메소드 의미 반환형 append() 인수로 전달된 값을 문자열로 변환한 후, 해당 문자열의 마지막에 추가 StringBuilde.. 2023. 2. 6. [JAVA] Overloading / Overriding Overloading ■ 정의 - 같은 이름의 메소드 여러개를 가지며 매개변수의 유형과 개수가 다르도록 하는 기술 ■ 특징 - 메소드 이름 동일 - return형이 같아도 되고 달라도 됨 - 매개변수 갯수가 달라야 함 - 매개변수 갯수가 같을 경우, 데이터 타입이 달라야 함 ■ 사용 예 package chap11; class Person{ private int regiNum; private int passNum; Person(int rnum, int pnum){ regiNum = rnum; passNum = pnum; } Person(int rnum){ regiNum = rnum; passNum = 0; } void showPersonalInfo() { System.out.println("주민등록 번호:.. 2023. 1. 30. [JAVA] EOF (End Of File) ■ 정의 - EOF(End Of File)란 컴퓨팅에서 파일의 끝(End of FIle)을 나타내며 데이터 소스로부터 더이상 읽을 수 있는 데이터가 없을 때 반복문을 종료 - Ctrl + Z를 누르면 동작 ■ 종류 자바에서는 대표적인 입력 클래스로 Scanner, BufferedReader가 있음 ■ 사용 예 Scanner sc = new Scanner(System.in); while(sc.hasNextLine()){//입력데이터 문자열 sc.nextLine(); } while(sc.hasNextInt()){//입력데이터 숫자 sc.nextInt(); } BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWr.. 2023. 1. 28. [JAVA] BufferedReader / BufferedWriter ■ 정의 - 버퍼를 통해 읽고 쓰는 함수 - 입 출력 데이터가 바로 전달되지 않고 중간에 버퍼링이 된 후 전달 - Scanner를 사용하는 것보다 속도가 빠름 ■ 생성자 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); ■ 메소드 종류 메소드 명 기능 BufferedReader(Reader rd) rd에 연결되는 문자 입력 버퍼 스트림 생성 BufferedWriter(Writer wt) wt에 연결되는 문자 출력 버퍼 스트림 생성 int read() 스트림으로부터 한 문자를 읽어 int형으.. 2023. 1. 26. 이전 1 다음
