출처 : 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비, 인프런

목차

1. 문자열
2. 배열
3. 투포인터 & 슬라이딩 윈도우
4. 해쉬맵 & 트리셋
5. 스택 & 큐
6. 정렬
7. 탐색알고리즘(재귀,그래프,트리,DFS,BFS)
8. 그리디 알고리즘
9. 동적계획법

1. 문자열

1-1. 조건 판단

대문자인지 소문자인지 확인

• 대문자인지 확인 : if(Character.isUpperCase(ch))
• 소문자인지 확인 : if(Character.isLowerCase(ch))

문자가 숫자인지 확인

• if(Character.isDigit(ch))

소문자 <-> 대문자 변환

• 소문자 -> 대문자 : bigChar = Character.toUpperCase(smallChar)
• 대문자 -> 소문자 : smallChar = Character.toLowerCase(bigChar)

대소문자 무시하고 두 문자열 비교

• string1.equalsIgnoreCase(string2)

1-2. 다른 자료형과 형변환

char -> int 변환

• int n = c - '0';

String -> int 변환

• int n = Integer.parseInt(str) 이때 맨앞 0은 사라진다.

String(n진수) -> int 변환

• int num = Integer.parseInt(str,n)

int -> String(n진수) 변환

• String str = Integer.toString(num, n)

  long타입의 경우 Long.toString(num, n)을 이용

char[] -> String 변환

• String str = String.valueOf(char[] charArr)

1-3. 알고리즘 구현 관련

문자열 for-each 문

• for(char c : str.toCharArray){ ... } for-each문에서 문자열을 사용할때는, CharArray로 바꿔서 반복한다.

숫자 비교

• 더 크거나 작은 값을 사용할때, 아래의 두 메소드를 활용한다.
• Math.max(a, b) 활용
• Math.min(a, b) 활용

split

• String[] strs = String.split("CH") 로 "CH"을 기준으로 쪼개진 문자열 배열을 얻는다.
• String[] strs = String.split("CH", -1) : limit parameter에 -1을 넣어서 공백을 제거한 부분문자열의 배열을 얻는다.

indexOf

• int pos = str.indexOf("CH") : "CH" 문자가 있는 인덱스를 pos에 반환받는다. 발견하지 못하면, pos에 -1를 리턴한다.

substring

• String temp = str.substring(index1, index2) : index1 ~ index1 의 부분 문자열을 temp에 담을 수 있다.
• String temp = str.substring(index1) : index1 부터 시작하는 부분 문자열을 temp에 담을 수 있다

문자열 뒤집기

• String result = new StringBuilder(str).reverse().toString()
  를 이용하여 뒤집힌 문자열을 얻을 수 있다.

replaceAll

• 문자열에 존재하는 모든 특정문자를 목표로 하는 문자로 변경 가능.

replace

• 문자열에 존재하는 특정 문자를 다른 문자로 변경 가능

대칭 비교

• 문자열의 중심을 기준으로 무언가 비교해야 한다면, lt,rt를 활용한 로직을 먼저 생각해본다.

/* lt, rt를 활용한 로직의 골격 */
public static String function(String str){
  int lt = 0;
  int rt = str.length()-1;
  while(lt < rt){
      if(...)
          lt++;
      else if(...)
          rt--;
      else{
          lt++;
          rt--;
      }    
  }
  return answer;
}

2. 배열

2-1. 정수 거꾸로 뒤집기

• 아래의 세가지 step으로 진행
• 1) t = temp를 10으로 나눈 나머지)
• 2) res = res*10 + t
• 3) temp를 10으로 나누기

int temp = nums[i];
int res =0; int t = 0;
while(temp > 0) {
	t = temp % 10;	// step1
	res = res*10 + t;	// step2
	temp = temp / 10;	// step3
}

2-2. 소수

소수의 갯수 판단

• 에라토스테네스의 체 이용

정수가 소수인지 판단

public static boolean isPrime(int num){
    if(num == 1)return false;
    for(int i=2; i<num; ++i){
        if(num%i==0) return false;
    }
    return true;
}

2-3. 2차원 배열

• int[] dx = {1,0,-1,0};
• int[] dy = {0,1,0,-1};
• dx, dy 두 배열을 이용하여, 양옆좌우를 손쉽게 탐색

2-4. 최대공약수

• N개 수의 최대공약수를 O(logN) 시간복잡도로 구해야 한다면, GCD 알고리즘을 사용해야 한다.
• 2개 수의 최대공약수를 구하려 한다면, getGCD(a,b) 함수를 한번 호출하면 되고, N개 수의 최대공약수를 구하려 한다면 아래와 같이 호출하여 구한다.

public static void main(String[] args) throws IOException {

    .... 대충 인덱스가 3이상인 배열을 세팅했음

    int GCD = getGCD(arr[0], arr[1]);
    
    for(int i=2; i<arr.length; ++i) {
        GCD = getGCD(GCD, arr[i]);
    }

}

public static int getGCD(int a, int b) {

    if(a%b == 0) {
        return b;
    } else {
        return getGCD(b, a%b);
    }

}

3. 투 포인터, 슬라이딩 윈도우

• O(n2)의 시간복잡도로 구현할 알고리즘을 O(n) 시간복잡도로 해결 가능.
• 로직을 구현할때, 아래의 두 포인트에 유념한다.
• 1. 제1 for문의 iterator를 rt로 지정.
• 2. target(기준점)이 있을 것이다. rt가 계속 증가하다가 무언가가 target을 넘어가는 임곗점이 오면, lt감소 while문에서 걸리도록 구현한다.

3-1. 투 포인터

• 투 포인터를 사용하기 위해서는 배열이 정렬되어 있어야만 한다.
• 결과값이 정렬된 배열로 출력되는 문제라면, 입력 배열을 정렬한 후 투포인터를 사용을 고려해 보아야 한다.

투 포인터 로직

public static ArrayList<Integer> twoPointers(int[] arr1, int[] arr2){
        ArrayList<Integer> answer = new ArrayList<>();
        int l1 = arr1.length;	// arr1 길이
        int l2 = arr2.length;	// arr2 길이		
        int p1=0, p2=0;			// 2개의 포인터

        Arrays.sort(arr1);		// arr1 정렬
        Arrays.sort(arr2);		// arr2 정렬

		// 하나의 포인터라도 끝까지 갔다면 종료
        while(p1<l1 && p2<l2){	
            // target과 같다면, p1,p2 모두 증가
            if(arr1[p1]==arr2[p2]){ 	
                answer.add(arr1[p1]);
                p1++;
                p2++;
            }		// 값이 작은 포인터를 증가
            else if(arr1[p1]<arr2[p2]){ 
                p1++;	
            }		
            else{
                p2++;	
            }
        }

        return answer;
    }

3-2. 슬라이딩 윈도우

• 투포인터와 달리 정렬되지 않은 배열에도 활용 가능하다.

슬라이딩 윈도우 로직

public static int slidingWindow(int k, int[] arr){
        /* 결과값, window, lt 초기화 */
        int answer = 0, sum=0, lt=0;

		/* 제1 for문의 iterator를 rt로, 
        * (rt는 반드시 끝까지 가야함) 
        */
        for(int rt=0; rt<arr.length; ++rt){	// rt 증가
            sum += arr[rt];	// window에 arr[rt] 추가
            /* window와 target이 같다면 
            * answer 증가 후 lt 증가 while문으로 이동
            */
            if(sum == k){	
                answer++;
            }
            /* lt 증가 while문 */
            while(sum >= k){
                sum -= arr[lt];
                lt++;
                if(sum == k)
                    answer++;
            }
        }
        return answer;
    }

4. 해쉬맵, 트리셋

4.1. HashMap을 이용한 배열,문자열 다루기

• 배열에 특정 값이 몇개 있는지 count하는 방법

// 배열 매핑
map.put(arr[i], map.getOrDefault(arr[i],0)+1);	//증가
map.put(arr[i], map.getOrDefault(arr[i],0)-1);	//감소
// 문자열 매핑
map.put(str.charAt(i), map.getOrDefault(str.charAt(i),0)+1);	//증가
map.put(str.charAt(i), map.getOrDefault(str.charAt(i),0)-1);	//감소

• 감소 후 value가 0일때, key를 remove() 해야 함을 유의해야 한다.

if(map.get(str.charAt(i)) == 0)
	map.remove(str.charAt(i));

4.2. HashMap 중요 메소드

• 크기 확인 : map.size()
• key 유무 : map.containsKey(key)
• value 유무 : map.containsValue(value)
• key 반환(key가 없다면 d 반환) : map.getOrDefault(key,d)
• key 삭제 : map.remove(key)

4.3. TreeSet (배열의 중복 제거) 중요 메소드

• 내림차순으로 트리셋 생성 : new TreeSet<(Collections.reverseOrder())>
• 추가 : tset.add()
• 특정값 삭제 : tset.remove()
• 크기 : tset.size()
• 첫번째 원소 : tset.first()
• 마지막 원소 : tset.last()

5. 스택, 큐

• 문제가 "괄호를 다룬다면" 10중 8,9는 Stack을 사용하는 문제이다.
• "맨 앞을 제거해서 뒤로 보내는" 형태의 로직을 다루는 문제는 10중 8,9는 Queue를 사용하는 문제이다.

5.1. Stack 중요 메소드

• 꼭대기에 삽입 : stack.push(object);
• 꼭대기 삭제 및 반환 : stack.pop();
• 꼭대기 반환 : stack.peek();
• index를 이용하여 반환 : stack.get(index);
• Stack의 크기 : stack.size();
• Stack이 비었는지 확인 : stack.isEmpty();

5.2. Queue 중요 메소드

• Queue 선언 : Queue<Integer> Q = new LinkedList<>();
• 맨 뒤에 삽입 : Q.offer(object);
• 맨 앞 삭제 및 반환 : Q.poll();
• 맨 앞 반환 : Q.peek();
• Queue의 크기 : Q.size();
• object가 있는지 확인 : Q.contains(object);

6. 정렬

6-1. 선택 정렬

• 앞에서부터 가장 작은 큰 혹은 작은 숫자를 채워나간다.
  

6-2. 버블 정렬

• 제2 for문에서 양 옆 숫자를 비교하며, 가장 큰 혹은 작은 숫자를 뒤로 밀어낸다.
  

6-3. 삽입 정렬

• 제1 for문에서 가리키는 숫자의 자리를 찾아 채워나간다.
  

6.4. 배열 문제를 정렬로 풀기위해 고려할 점

• 숫자의 "중복" 관련 문제를 풀땐 HashMap, HashSet을 먼저 고려해 본다.
• 배열을 한칸씩 미는 로직은 "삽입정렬"과 유사한 로직일 수 있다.
• 배열을 복사할때, "깊은복사"와 "얕은복사"에 유의하도록 한다.
• 정렬을 위한 객체를 직접 만들어야 할때는, Comparable interface를 implements하고, cpmpareTo method를 overriding한다.
• compareTo method의 반환값은
  1)오름차순 정렬시 return this - o
  2)내림차순 정렬시 return o - this

6.5. 이분검색

• 배열을 완전탐색하면 O(n) 시간복잡도이지만, 이분검색을 활용하면 O(logn)으로 줄일 수 있다.
• 이분검색은 정렬된 배열에만 활용 가능하다.

// 이분검색 로직
public static int binarySearch(int target, int[] arr){
        int lt = 0;
        int rt = arr.length-1;
        while(lt <= rt){
            int mid = (lt + rt) / 2;
            if(arr[mid] == target)
                return mid+1;
            else if(target < arr[mid])
                rt = mid - 1;
            else
                lt = mid + 1;
        }
        return 0;
    }

6.6. 결정 알고리즘

• 답에 될 수 있을법한 범위(lt ~ rt)를 정해놓고 갱신(mid = lt + rt)하면서 가장 적합한 답을 이분검색으로 찾아내는 알고리즘이다.

7. 탐색 알고리즘

7.1. 재귀함수(스택프레임)

• 피보나치 수열
• 팩토리얼
• 1 ~ n, n ~ 1 출력

7.2. 메모이제이션

• fibonacci 함수가 실행될때마다 결과값을 fibo[] 배열에 저장한 후 다음에는 그 값을 계산할 필요 없이 가져다 쓰게되면, 실행 시간을 대폭 줄일 수 있다.

public class Main {
	public static void main(String[] args) {
        int n = 45;
        fibo = new int[n+1];
        fibonacci(n);
        for(int i=1; i<=n; ++i)
            System.out.println(fibo[i]+" ");

    }
    static int[] fibo;
    public static int fibonacci(int n){
        if(fibo[n] > 0)
            return fibo[n];
        if(n==1)
            return fibo[n] = 1;
        else if(n==2)
            return fibo[n] = 1;
        else
            return fibo[n] = fibonacci(n-1)+fibonacci(n-2);
    }
}

• 조합수를 계산하는 공식 nCr 은 nCr = n-1Cr-1 + n-1Cr 로 계산할수도 있는데 이 공식 역시 피보나치 수열과 비슷한 방식으로 풀이가 가능하기 때문에, 메모이제이션을 활용할 수 있다.

7.3. DFS

• 일반적으로 재귀나 스택을 이용해서 구현한다.
• 최단거리 문제를 푸는데에는 적합하지 않다.

7.4. BFS

• Queue를 사용하여 구현한다.
• Element를 poll하면서 연결된 정점이나 노드를 Queue에 offer한다.

7.5. Graph

인접행렬로 무방향 그래프 구현

• a,b가 연결되어있음을 알려주는 (a,b) 가 입력되었을때, 2차원 배열의 a행b열 b행a열 모두에 1을 삽입한다.

graph[a][b] = 1;
graph[b][a] = 1;

인접행렬로 방향 그래프 구현

• a에서 b로 연결되어있음을 알려주는 (a,b) 가 입력되었을때, 2차원 배열의 a행b열에만 1을 삽입한다.

graph[a][b] = 1;

인접행렬로 가중치 그래프 구현

• a에서 b로 연결되어있는데, c의 가중치를 가지고 있음을 알려주는 (a,b,c) 가 입력되었을때, 2차원 배열의 a행b열에 c을 삽입한다.

graph[a][b] = c;

인접리스트로 방향 그래프 구현

• 인접리스트로 방향 그래프를 구현하기위해 아래의 자료구조를 사용한다.

graph = new ArrayList<ArrayList<T>>;

• 인접리스트 순회는 아래처럼 사용한다.

// x 노드와 연결된 정점을 탐색할때
for(int nx : graph.get(x)){
	...
}

7.6. 대표 유형

• 순회
• 레벨탐색 (BFS)
• 최소거리 (DFS or BFS)
• 경로탐색 (DFS, 인접행렬 or 인접리스트)
• 그래프 최단거리 (BFS or 최소거리배열)

8. 그리디 알고리즘

• 눈 앞에 있는 가장 최선을 선택해 나가여 문제를 해결하는 알고리즘.
• 문제가 지역적 최선의 선택 -> 전역적 최선의 선택 을 만족해야 한다.

8.1. 우선순위 큐

• 브루트포스로 배열의 최댓값, 최솟값을 탐색할때의 시간복잡도는 O(n)이다.
• 우선순위큐에서 최댓값, 최솟값을 poll 할때의 시간복잡도는 O(logn)이다.
• 오름차순 큐 생성(작은값 우선 poll) : PriorityQueue<Edge> pQ = new PriorityQueue<>();
• 내임차순 큐 생성(큰값 우선 poll) : PriorityQueue<Edge> pQ = new PriorityQueue<>(Collections.reverseOrder());

8.2. 다익스트라

• 한 정점에서 다른 각 정점까지의 최소거리를 구하는 대표적인 그래프 탐색 알고리즘이다.
• 매 순간 가장 작은 값을 찾아나가는 알고리즘이기에 그리디 알고리즘이며, 시간복잡도는 정점탐색(O(n)) x 우선순위큐(O(logn)). 따라서 O(nlog)으로 문제를 해결한다.

8.3. 유니온 & 파인드

• 재귀호출을 이용하여 연결된 정점을 하나의 그래프로 연결시키는 알고리즘.
• 메모이제이션을 사용하여 시간복잡도를 낮출 수 있다.

/* find 메소드 */
public static int Find(int v){
        if(v == unf[v])
            return v;
        else
            return unf[v] = Find(unf[v]);   // 메모이제이션
    }
/* union 메소드 */
public static void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        if(fa!=fb)
            unf[fa] = fb;
    }

8.4. 최소신장트리

• 회로(한 정점이 간선을 돌다가 자신 정점으로 돌아올 수 있는 경우)가 존재하면 그래프, 회로가 없다면 트리이다.
• 최소신장트리는 가중치 그래프에서 가중치가 큰 간선들을 제거하여 최소의 가중치 간선만을 남긴 트리이다.

8.5. 크루스칼

• 그래프를 최소신장트리로 만드는 알고리즘.
• 가중치를 기준으로 오름차순 정렬된 간선 정보를 유니온파인드를 적용해나가며 문제를 해결한다.
• 다른 유니온이라면 연결함.
• 같은 유니온이라면 연결하지 않음.(이미 가중치가 낮은 간선으로 연결되었기 때문에)

8.6. 프림

• 그래프를 최소신장트리로 만드는 알고리즘.
• 크루스칼 알고리즘과 다르게, 정렬이 필요하지 않은 대신 우선순위 큐을 활용하는 그리디 알고리즘이다.
• 그래프를 무방향 인접리스트로 저장.
• 방문하지 않은 노드만을 방문하며 우선순위 큐에 삽입

9. 동적계획법

9.1. 동적계획법(Dynamic Programming)이란?

• 복잡도가 큰 문제를 직관적으로 알 수 있는 작은 단위의 문제으로 쪼갠 후, 그 문제의 답을 기억해둔 후 조금씩 더 큰 문제로 확장해 나가는 문제해결방식.
• Dynamic table(dy[])을 이용.