[TIL] 내일배움캠프 46일차(23.06.29.) - 알고리즘 문제 풀이에 필요한 자료구조, 메소드 등 복습 및 공부

To-do

• 알고리즘 공부
• 스프링 개인과제 lv.3 확인 및 제출

 

TIL

• List -> ArrayList, LinkedList, Vector

[특징]
1. 순서 보장: List는 요소들을 특정한 순서로 저장. 저장된 순서대로 요소에 접근 가능. 요소의 순서는 추가한 순서를 유지
2. 인덱스 접근: List는 요소들을 인덱스로 접근할 수 있음. 인덱스는 0부터 시작하여 요소의 위치 나타냄
3. 중복 허용: List는 동일한 값을 중복해서 저장할 수 있음. 따라서 리스트에는 동일한 값의 요소가 여러 개 포함될 수 있음

[활용]
1. 순차적인 데이터 저장: 데이터를 순차적으로 저장하고, 순서에 따라 접근하고자 할 때
2. 검색 및 접근: 인덱스를 사용하여 특정 위치의 요소에 접근하거나 검색할 때
3. 순회 및 반복: for문이나 Iterator를 사용하여 List의 모든 요소를 순회하거나 반복할 때
4. 데이터 정렬: 요소들을 순서대로 저장하므로, 정렬된 데이터를 저장하고 관리하는 데 사용

[메서드]
* 요소 추가: add(element) 또는 add(index, element)
* 요소 삭제: remove(index) 또는 remove(element)
* 요소 조회: get(index) 또는 indexOf(element)
* 크기 확인: size()
* 리스트 비우기: clear()
* 리스트 순회: for-each, Iterator

 

• Map -> HashMap, TreeMap, LinkedHashMap

[특징]
1. Key - Value 쌍으로 이루어진 데이터를 저장하고 관리하는 자료구조
2. 유일한 Key: 중복된 키 없음. 만약 동일한 키로 값을 저장하면 기존 값은 대체됨
3. 순서의 보장: Map은 저장할 때 특정한 순서를 보장하지 않음 -> 순서가 중요한 경우 LinkedHashMpa과 같은 구현체 사용해야 함
4. 효율적인 검색: 내부적으로 효율적인 검색 알고리즘을 사용하여 키를 기반으로 값을 검색 -> 매우 빠른 검색 속도

[활용]
1. 사전(Dictionary): 단어와 해당 단어의 정의를 매핑하여 저장하는 용도로 사용
2. 데이터베이스의 인덱스: 데이터베이스에서 테이블의 특정 컬럼을 기반으로 데이터를 검색할 때 효율적인 인덱싱을 위해 사용
3. 캐시(Cache): 중복된 계산을 피하기 위해 결과를 저장하고 키를 기반으로 값을 검색하는 데 사용
4. 그 외 다양한 데이터 저장 및 조회의 용도로 활용

[메서드]
* 요소 추가: put(key, value)
* 요소 삭제: remove(key)
* 요소 조회: get(key)
* 키 존재 여부 확인: containsKey(key)
* 값 존재 여부 확인: containsValue(value)
* 키-값 쌍 수: size()
* 맵 비우기: clear()
* 맵 순회: for-each, keySet(), values(), entrySet()

 

• Set -> HashSet, TreeSet, LinkedHashSet

[특징]
1. 중복된 요소 제거: Set은 동일한 값을 중복해서 저장하지 않음. 이미 존재하는 요소와 동일한 값을 추가하려고 하면 해당 요소는 추가되지 않음
2. 순서의 보장되지 않음: Set은 요소들을 특정한 순서로 저장하지 않으며, 저장된 순서와 관계없이 요소에 접근. 따라서 요소들을 순서대로 순회하거나 인덱스로 접근할 수 없음
3. 고유한 값 저장: Set은 고유한 값을 저장하기 위해 동등성(Equivalence) 개념을 사용. 동일한 값을 갖는 객체를 동등한 객체로 취급하여 중복을 제거

[활용]
1. 중복 제거: 데이터에서 중복된 값을 제거하고 고유한 값을 유지하기 위해 사용
2. 멤버십 테스트: 특정 값이 Set에 속하는지 여부를 확인하기 위해 사용됨
3. 교집합, 합집합, 차집합 등의 연산: 두 개 이상의 Set 사이에서 교집합, 합집합, 차집합 등의 연산을 수행할 때 사용됨
4. 필터링: 특정 조건에 맞는 요소만을 선택하여 추출하기 위해 사용

[메서드]
* 요소 추가: add(element)
* 요소 삭제: remove(element)
* 요소 포함 여부 확인: contains(element)
* 요소 수: size()
* Set 비우기: clear()
* Set 순회: for-each, Iterator

 

• Stack

[특징]
1. 후입선출(LIFO): 가장 최근 추가된 데이터가 가장 먼저 제거
2. 제한된 접근: 스택의 요소에 접근할 때는 가장 상단 요소(top)만 접근 가능
3. 제한된 연산: 주요 연산 push(데이터 추가), pop(데이터 제거), peek(상단 요소 확인)

[활용]
1. 함수 호출의 실행 순서 관리: 함수 호출 시 스택에 호출된 함수의 정보 push하고, 함수 실행이 완료되면 pop하여 이전 함수로 돌아갈 수 있음
2. 괄호 매칭: 괄호의 쌍이 올바른지 확인. 여는 괄호를 만나면 스택에 push하고, 닫는 괄호를 만나면 스택에서 pop하여 매칭 여부 확인
3. 뒤로 가기 기능: 웹 브라우저의 뒤로 가기 버튼과 같이 이전에 방문한 페이지의 정보를 스택에 저장하고, 뒤로 가기 시 스택에서 pop하여 이전 페이지로 이동할 수 있음

[메서드]
* 요소 추가: push(element)
* 요소 삭제: pop()
* 요소 조회: peek()
* 스택이 비어있는지 확인: isEmpty()
* 스택 크기 확인: size()

 

• Queue -> LinkedList(연결 리스트를 기반), ArrayDeque(동적 배열로 구현)

[특징]
1. 선입선출(FIFO): 요소를 추가한 순서대로 저장하며, 가장 먼저 추가된 요소가 가장 먼저 제거됨
2. 요소 추가와 제거: 요소를 맨 뒤에 추가하고, 맨 앞에서 제거함. 이를 통해 새로운 요소를 저장하고 이전에 저장된 요소들을 처리할 수 있음
3. 다양한 구현 클래스: LinkedList는 요소의 삽입과 삭제에 효율적이며, ArrayDeque는 양쪽에서의 삽입과 삭제에 효율적

[활용]
1. 대기열 및 작업 처리: Queue는 대기열로 사용되는 경우가 많음. 예를 들어, 프로세스 작업 큐, 이벤트 처리 큐 등에서 요청을 대기하고 처리 순서를 유지할 수 있음
2. 너비 우선 탐색(BFS): Queue는 그래프 탐색 알고리즘 중 너비 우선 탐색(BFS)에 주로 사용됨. BFS에서는 인접한 노드를 방문한 후 큐에 넣어서 다음에 방문할 노드를 결정함
3. 캐시 관리: Queue는 최신 데이터 또는 자주 사용되는 데이터를 유지하기 윈한 캐시 관리에 활용될 수 있음. 캐시에서는 가장 오래된 데이터를 삭제하고, 새로운 데이터를 추가할 때 Queue의 특성을 활용할 수 있음
4. 이벤트 처리: Queue는 이벤트 처리 시스템에서 이벤트를 관리하는 데 사용될 수 있음. 이벤트가 발생할 때마다 Queue에 이벤트를 추가하여 순차적으로 처리 가능

[메서드]
* 요소 추가: add(element) 또는 offer(element)
* 요소 삭제: remove() 또는 poll()
* 다음에 제거될 요소 조회: peek()
* 큐가 비어있는지 확인: isEmpty()
* 큐 크기 확인: size()

 

• 배열을 Set으로 변환 후 다시 배열로 변환하기

1. 배열 -> Set: Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr)); (배열의 중복값 제거됨)
2. Set -> 배열: Integer[] arr = set.toArray(new Integer[0]); (배열의 크기를 0으로 설정 시 자동으로 배열 크기 지정됨

 

// Set으로 변환할 배열
Integer[] arr = { 1, 1, 2, 3, 4 };
 
// 배열 -> Set
Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr));
 
// Set 출력
System.out.println(set); // [1, 2, 3, 4]
         
// Set -> 배열
Integer[] arr = set.toArray(new Integer[0]);
 
// 배열 출력
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4]

 

• int 배열 <-> Integer 배열로 만들기

// int, Integer 배열 선언
int[] arr = {1, 2, 3, 4}
Integer[] arr2 = new Integer[arr.length];

// 방법1) for문을 이용 - 반대의 경우는 순서만 바꿔주면 됨
for (int i = 0; i < arr.length; i++) {
	arr2[i] = arr[i];
}

// 방법2) Stream을 이용한 방법
Integer[] arr3 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
// Integer 배열을 Int 배열로
int[] arr4 = Arrays.stream(arr3).mapToInt(i->i).toArray();

 

• List 를 내림차순으로 정렬하기: Collections.sort(list, Collections.reverseOrder());
• 배열을 내림차순으로 정렬하기: Integer[] intArr = new Integer[31]; Arrays.sort(intArr, Collections.reverseOrder());
• 비트 연산을 활용해 2의 제곱수인지 확인하기

public boolean isPowerOfTwo(int number) {
    return (number & (number - 1)) == 0;
}

 

• BigInteger 클래스: 임의의 정수 크기를 지원하기 위한 클래스, int 또는 long의 범위를 넘어서는 임의의 정수 표현 가능

[특징]
1. 임의의 정수 크기: BigInteger는 자바에서 제공하는 기본 정수 타입의 크기를 초과하는 임의의 정수를 표현 가능. 따라서 아주 큰 정수 값을 다룰 때 유용
2. 불변성(Immutable): BigInteger 객체는 변경할 수 없는(immutable) 객체. 즉, 한 번 생성된 BigInteger 객체는 그 값을 변경할 수 없음. 대신에 새로운 BigInteger 객체를 생성하여 연산 결과를 반환
3. 다양한 연산 지원: BigInteger 클래스는 다양한 수학적 연산을 지원합니다. 예를 들어, 덧셈, 뺄셈, 곱셈, 나눗셈, 나머지 연산, 거듭제곱 등의 연산을 수행 가능
4. 비트 연산 지원: BigInteger는 비트 단위 연산도 지원합니다. AND, OR, XOR, 비트 이동 연산 등을 사용 가능
5. 문자열 표현: BigInteger 객체는 문자열로 표현 가능. toString() 메서드를 사용하여 BigInteger 값을 문자열로 변환 가능

 

• Localdate의 주요 메소드

1. now(): 현재 날짜를 가져오기 시스템의 시계에 따라 결정
2. of(int year, int month, int dayOfMonth): 지정된 연도, 월, 일로 LocalDate 객체를 생성
3. getYear(), getMonth(), getDayOfMonth(): LocalDate 객체에서 연, 월, 일 값을 가져오기
4. plusDays(long daysToAdd), minusDays(long daysToSubtract): LocalDate 객체에 지정된 일 수를 더하거나 빼기
5. isBefore(LocalDate other), isAfter(LocalDate other): 현재 LocalDate 객체가 다른 LocalDate 객체보다 이전인지 또는 이후인지를 확인
6. isEqual(LocalDate other): 현재 LocalDate 객체와 다른 LocalDate 객체가 같은지 확인
7. format(DateTimeFormatter formatter): LocalDate 객체를 지정된 형식으로 문자열로 변환
8. parse(CharSequence text, DateTimeFormatter formatter): 문자열을 LocalDate 객체로 파싱

 

• String의 replace 메소드: 문자열 내에서 특정 문자 또는 문자열을 다른 문자 또는 문자열로 대체 -> 작성 시간은 빠르지만 테스트 통과 시간이 오래 걸림

String str = "Hello, World!";
String replacedStr = str.replace('o', 'x');
System.out.println(replacedStr); // 출력: Hellx, Wxrld!

String str2 = "Hello, Java!";
String replacedStr2 = str2.replace("Java", "Python");
System.out.println(replacedStr2); // 출력: Hello, Python!

 

• 2차원 배열을 출력하기

      [방법1] 이중 반복문을 사용하여 배열 요소를 하나씩 출력하기

int[][] array = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array[i].length; j++) {
        System.out.print(array[i][j] + " ");
    }
    System.out.println();
}

// 출력
1 2 3
4 5 6
7 8 9

      [방법2] Arrays.deepToString() 메서드를 사용하여 배열을 문자열로 변환한 후 출력하기

int[][] array = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

String arrayString = Arrays.deepToString(array);
System.out.println(arrayString);

// 출력
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

      [방법3] Arrays.stream() 및 Arrays.toString() 메서드를 사용하여 각 행을 문자열로 변환한 후 출력하기

int[][] array = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

for (int[] row : array) {
    String rowString = Arrays.toString(row);
    System.out.println(rowString);
}

// 출력
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

 

 

Next...

• 뉴스피드 프로젝트 회의 및 작성
• 알고리즘 그룹 스터디