[JAVA]알고리즘 풀 때 알고 있으면 좋은 지식들

1. 정렬

API - import java.util.*

사용법 - Arrays.sort(array);

2. 문자열 처리

String s = "abc";
 
//동일 판정
if(s.equals("abc")){
    System.out.println("equal");
}
 
//문자 하나 추출
char c = s.charAt(1); //'b'가 추출됨
 
//문자열 연결
s = "def" + s + "ghi"; //"defabcghi"
 
//문자열 잘라내기
s = s.Substring(3,3); //"abc"

3. 연관 배열

 - 순서대로 데이터를 관리할 때는 배열이 편리하다. 하지만 그렇지 않은 경우에는 연관 배열을 사용하는 것이 좋다

import java.util.*;
 
public class test {
    public static void main(String[] args){
        test test = new test();
        String[] s = {"abc","def"};
        test.countStrings(s);
    }
 
    void countStrings(String[] s) {
        Map<String, Integer> hm = new HashMap<String, Integer>();
        for (int i = 0; i < s.length; i++) {
            if (!hm.containsKey(s[i])) {
                hm.put(s[i], 0);
            }
            hm.put(s[i], hm.get(s[i]) + 1);
        }
 
            for (String key : hm.keySet()) {
                System.out.println(key + " " + hm.get(key));
            }
    }
}
 
 
---------------------------결과 값 ------------------------------
abc 1
def 1

 4. 깊이 우선 탐색(DFS)

 - 재귀 함수를 이용한 깊이 우선 탐색

 - 사용하면 좋은 경우

(1) 모든 경로를 탐색하고 결과를 확인해야 하는 경우

(2) 문자열 등을 탐색할 때 "사전 순서로 앞에 오는 것"처럼 앞부터 검색해서 찾는 것이 빠를 경우

int dfs(int now){
    if(현재 상태 now가 끝나는 조건) return 현재 상태 now의 값            
 
    int ret = -1;
    for(int i = 0; i < 다음 상태 개수; i++){
        int next = i번째 다음 상태;
        if(next가 조건을 만족하는 경우) ret = Math.max(dfs(next),ret);
    }
 
    return ret;
}

5. 너비 우선 탐색

 - 큐를 이용한 너비 우선 탐색

 - 사용하면 좋은 경우

(1) 시작 지점에서 가장 가까운 것을 구하고 싶은 경우

(2) 탐색 범위 자체는 넓지만 어느 정도 근처에서 구하고 싶은 해가 존재하는 것을 알고 있는 경우

(3) 탐색 범위가 굉장히 넓으며 깊이 우선 탐색을 사용할 때는 스택이 대량으로 사용되는 경우

queue<T> q;
q.push(초기 상태);
while(!q.empty()){
    T now = q.front(); q.pop()
    현재 상태를 처리합니다.
    for(int i = 0; i < 다음 상태 개수; i++){
        T next = i번째 다음 상태;
        if(next를 방문했었는지 판정)
            q.push(next);
    }
}