본문 바로가기

java30

[자료구조] 연결리스트 (LinkedList) / 배열리스트 (ArrayList) LinkedList (연결리스트) ■ 정의 - LinkedList (연결리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 - 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값을 가지고 각 포인터 변수의 주소도 따로 존재 ■ 생성자 - LinkedList list = new LinkedList(); ■ Code 더보기 import java.util.Comparator; public class LinkedList { class Node { private E data; private Node next; Node(E data, Node next) { this.data = data; this.next = next; } } private Node hea.. 2023. 3. 28.
[JAVA] 에라토스테네스의 체 에라토스테네스의 체 ■ 정의 소수를 찾는 방법 중 하나로, '소수가 되는 수의 배수를 지우면 남은 건 소수가 된다' 라는 알고리즘 소수가 무엇인지 찾을 필요가 없으며, 2부터 자기 자신을 제외한 배수가 되는 것을 지움 ​ - 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는데, 이것이 100 이하의 소수이다. - 7까지 찾는 이유는 8, 9, 10은 2와 3의 배수이므로 이미 지워진 상태이고, √100 < 11이기 때문이다. ■ 사용 예 (백준 No.17103) 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이.. 2023. 3. 20.
[JAVA] 유클리드 호제법(GCD / LCD) GCD (최대 공약수) ■ 정의 1. 22 x 8 크기의 직사각형을 짧은 변(8)을 한 변으로 하는 정사각형으로 분할 2. 정사각형을 제외한 8 x 6 직사각형을 짧은 변(6)을 한변으로 하는 정사각형으로 분할 3. 남은 6 x 2 직사각형을 2 x 2 크기의 정사각형 3개로 분할 ☞ 마지막까지 나누어 떨어진 정사각형의 한 변의 길이가 최대 공약수가 됨 ■ Code import java.util.Scanner; public class EuclidGCD { static int gcd(int x, int y){ if(y == 0) return x; else return gcd(y, x % y); } public static void main(String[] args){ Scanner sc = new Scan.. 2023. 3. 15.
[Algorithm] 버블 정렬(Bubble Sort) 버블 정렬 (Bubble Sort) ■ 정의 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)이라고도 함 ■ 사용 예 - 총 3번의 Pass를 통해 [1, 3, 4, 6, 7]로 오름차순 정렬을 만들 수 있음 - 사진에서는 모든 비교과정을 표시하였지만, 이미 정렬된 수와의 비교는 굳이 진행하지 않아도 됨 ■ 장점 - 구현이 매우 간단하고, 소스코드가 직관적 - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 => 제자리 정렬(in-place sorting) - 안정 정렬(Stable Sort) ■ 단점 - 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장.. 2023. 3. 9.
[자료구조] 덱(Dequeue, Double-ended Queue) 덱 (Dequeue, Double-ended Queue) ■ 정의 - Dequeue(덱)은 양쪽에서 넣고 빼고가 가능한 큐 - 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라 스택, 큐 모두 사용 가능 - 스케줄링이 복잡해질수록 큐와 스택보다 효율이 잘 나옴 ■ 메소드 Deque dq = new LinkedList(); 메소드 의미 addFirst(int item) 덱의 앞 쪽에 item 삽입, 용량 초과 시 예외 발생 offerFirst(int item) 덱의 앞 쪽에 item 삽입, 용량 초과 시 false 리턴 addLast(int item) 덱의 뒤 쪽에 item 삽입, 용량 초과 시 예외 발생 offerLast(int item) 덱의 뒤 쪽에 item 삽입, 용량 초과 시 false 리턴 r.. 2023. 2. 24.
[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.
[Algorithm] 선형검색(Linear search) / 보초법(Sentinel method) 선형 검색 (Linear search) ■ 정의 - 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 기법 ■ 사용 예 - 찾으려는 값이 2일 경우 - 찾으려는 값이 7일 경우 - 찾는 값이 3으로 존재하는 경우 앞에서부터 순차적으로 검색 후 index 값이 3에서 탐색을 종료 함 - 찾는 값이 7로 존재하지 않는 경우 마지막까지 검색 후 -1을 return 후 종료 함 ■ Code - while문으로 작성한 선형검색 public class SeqSearch { static int seqSearch(int[] a, int n, int key){ int i = 0; while(true){ if(i == n) return -1; if(a.. 2023. 2. 13.
[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] 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.

티스토리툴바