[코딩테스트] 내가 까먹는 것만 정리한 코딩 테스트 문제 유형(java)

제가 보기 위해 까먹지 않기 위해 글로써 구현 방법을 적어 놓았습니다.

문제 유형별로 적용되는 알고리즘 및 구현법 정리

 

 

 

java priorityqueue 사용

 

현재 조건에 위배되지 않는 원소들 중 최댓값(최솟값) 을 빨리 찾아야 할 때.

이동 수, 행동 수 와 같이 무조건 bfs의 한 iteration당 1씩 증가하는 상황이 아닐 때의

bfs 종료조건을 만족했을 때의 값이 최대(or최소)임을 보장하기 위해

예를 들면 다익스트라 알고리즘으로 최단거리를 계산할때 시간복잡도를 줄이는 트릭으로 사용된다.

 

근데 자꾸 동적할당하는 부분부터 기억이 안난다.

1. Queue에 넣을 클래스 생성
2. 클래스는 Comparable<T>의 구현체이며
3. compareTo 메서드를 오버라이드한다.

 

 

등수 계산하기

 

알고리즘 : None

등수를 파악해야하는 원소(ex : 이름, 점수)들을 리스트로 생성

조건에 맞게 정렬,

이전 원소의 점수를 temporal 하게 들고있으면서 현재 원소와 비교, **동점자 여부에 주의하여 등수 계산

 

 

모든 노드에서 모든 노드와의 최단거리가 필요한 경우

 

알고리즘 : 플로이드 와샬

구현방법 : 모든 k에 대하여, i to j 의 거리와 i to k + k to j 의 거리를 비교하면서

dp방식으로 최단거리를 계산

 

시간복잡도가 $O(n^3)$ 이므로, 노드의 수가 1000가 넘어가면 99% 이렇게 푸는게 아니다.

 

 

최소 비용으로 노드를 전부 연결

 

알고리즘 : 최소 신장 트리(Minimum Spanning Tree)

구현 방법 : 비용과 연결되는 노드의 정보 (ex : {cost , n1, n2}) 들을 비용 오름차순 정렬

스패닝 트리 구현을 위해 유니온파인드(아래에 있음) 활용,

남은 방문 노드 중에 비용이 작으며, cycle이 생기지 않는 노드를 방문(추가) → 연결의 수가 노드-1 개가 되면 모두 연결!

 

 

연결되거나 연결되지 않은 노드 파악하는 법

 

알고리즘 : 유니온파인드

parents[] 자식(인덱스)이 연결된 부모(값) 의 정보 배열을 생성,

부모찾는함수 구현,

연결하는 함수 구현

 

 

삼단논법 && 비교할 수 없는 원소 수 찾기

 

A→B, B→C 와 같은 조건이 주어지면 A→ C 관계도 파악하기,

등수를 알 수 없는 원소 수 찾기

알고리즘 : 플로이드 와샬

 

구현 방법 : 나보다 아래로( 문제에서 대소비교 할테니) 닿을 수 있으면 true 아니면 false,

나보다 위로 닿을 수 있으면 true 아니면 false,

이렇게 하면, 두 개의 배열에 대하여,

i 노드와 j 노드는 서로간에 대소비교가 가능한지에 대한 여부를 알 수 있게 된다.

 

 

 

프로세싱 유형

알고리즘 : 우선순위 큐 + 스택

구현 방법 :

1. 대기 큐에 놓이는 각각의 프로세스가 어떤 우선순위를 가지고 진행되는가
2. 1st while문, 해결한 프로세스의 개수가 전체 프로세스 수보다 작을 때 까지
3. 2nd while문, 현재 대기 큐에 들어가야하는 프로세스들을 발견하는 단계, index를 1씩 증가시키며 대기 큐에 들어가야 한다면 add,
4. 현재 조건과 다음 프로세스 실행 조건 사이에 공백이 생기는 경우, 적절히 guard절을 통해 2nd while문으로 들어갈 수 있도록 하기

 

코드 요약

pq or q 정의
while(모든 프로세스 처리할때 까지){
	while(정렬된 프로세스를 탐색하며 현재 조건을 만족할때 까지 q.add)
	if(q가 비여있다면 프로세스를 다 탐색하진 않았지만 q가 비어있다면, 현재 조건이 lock 걸림, 조건을 변경)
	else{프로세스 실행 처리}
}

 

좋은 예시 ->

2023.10.08 - [알고리즘] - [프로그래머스] PCCP 모의고사 1회 4번 운영체제 java

[프로그래머스] PCCP 모의고사 1회 4번 운영체제 java

 

 

 

누적 최대 탐색 dp

 

문제의 조건( 예를 들면 가방의 최대 무게 k, 사용 가능한 동전의 개수 l 등)을 자체적으로 줄여서,

만약 문제의 조건이 k라면,

조건이 1일때의 최댓값, 조건이 2일때의 최댓값, 조건이 3일때의 최댓값 ….

이렇게 누적하여 탐색할 때 정답을 찾기 쉬운 유형으로, 대표적으로는 타일링, knapsack, 거스름돈 유형이 있는데, 상대적으로 이해하기 쉬운 타일링에 비해 2차원적으로 생각할 수 있어야하는 knapsack, 거스름돈 유형이 어려워 정리한다.

(Wi, Vi) = (6, 13), (4, 8), (3, 6), (5, 12)

의 경우를 예로 들어,

dp[i][k] (i는 물건의 index) (k 는 가방의 수용 가능 무게) 의 값을 물건을 담을 수 있는 경우로 누적하여 계산하여 최신화한다.

dp[][0]~dp[][2] 까지는 0의 값을 가질 것이고,

 

 

가방의 허용 무게가 3인 경우 index=2 (3번째 물건) 번째 탐색 때 (3,6)의 물건을 담을 수 있으므로,

dp[0][3] = 0, dp[1][3] = 0, dp[2][3]의 값은 6이 되며,

여기서 중요한 점은 dp[3][3]의 값이 현재 인덱스 3인 (5,12) 물건을 담을 수 없으므로 0이 아니라 여태까지 계산한 dp[3][3]의 최댓값인 6이 된다는 것 (내 멋대로 누적 최대 탐색 dp유형이라고 붙여놓은 이유가 이것)

계산 과정은 index가 3일 때 물건을 담을 수 없으므로 → dp[3-1][3] 의 무게를 가져온다.

 

 

dp[*][4]에 대하여, 배낭의 허용 무게가 4가 되었으므로, 이따가 (4,8) 물건이 들어가리라 짐작할 수 있다.

하지만 dp[0][4]의 경우 현재 탐색 중인 물건(6, 13) 의 경우는 8도, 6도 적혀서는 안된다.

현재 내 가방 무게보다 적을 적에, 현재 물건을 담았었는가를 생각해야한다. (사람처럼 생각하면 안된다.)

 

index = 1 인 경우, 현재 물건은 (4,8) 로 현재 배낭에 담을 수 있게 된다.

 

index = 2인 경우에,

사람의 아이디어로는 그냥 (3,6) 물건을 빼버리고 (4,8) 물건을 넣으면 되겠다! 라고 생각할 텐데

배열과 물건을 반복적으로 탐색중인 컴퓨터의 입장에서 생각해야한다.

먼저 현재 index = 2 즉 (3,6)물건을 담을 수 있으므로, 이전 물건을 그대로 두는 것이 좋은지,

 

 

 

슬라이딩 윈도우와 구간합 구별하기

 

2023.09.20 - [알고리즘] - [구간합] [프로그래머스 광고삽입] 구간합 알고리즘의 활용과 사전 작업의 이해

구간합 문제를 슬라이딩 윈도우라고 착각해서 삽질함

 

 

 

 

 

 

배낭 문제 - 배낭에 물건 한개만

 

알고리즘 : 그리디 + 우선순위 큐

구현 : 가방에 물건을 한 개만 담을 수 있는 상황에서는 가치 / 무게 의 비율을 생각하면 돌이킬수 없게 된다.. 컴퓨터적 사고가 필요한데, 막상 떠올리고나서는 간단하다.

중요한 점은 현재 가방에 넣을 수 있는(무게 제한을 넘지 않는) 보석들 중에 최대 가치를 가진 보석을 담는다는 것.

넣을 수 있는 보석들 중 최대 가치 빨리 찾기 → 우선순위 큐가 생각이 나야한다.

 

 

작업의 순서(선행 조건)이 정해져있는 경우

 

위상 정렬!

1. 모든 노드의 진입차수들을 파악

2. 진입차수가 0인 (선행 조건이 없는) 노드부터 출발시키며, 해당 노드가 선행 조건이 되는 후행 노드들의 진입차수들을 -1

 

 

 

 

dfs를 잘 모르고있었다니…

 

[1. 노드에서 다음 depth의 결과 바로 리턴] 아래 코드와 같이 dfs 함수 내에서 다음 depth의 리턴 값을 그대로 리턴하는 방식으로는 통과를 못하는데

static boolean dfs( int nowr, int nowc){
    board[nowr][nowc] = 'x';
    
    if(nowc == c-1)
        return true;

    for(int nextr = nowr-1; nextr<=nowr+1; nextr++)
        if(nextr >=0 && nextr < r && board[nextr][nowc+1] == '.')
            return dfs( nextr, nowc+1);
    
    return false;
}

 

[2. 노드에서 다음 depth의 결과가 true인 경우에만 바로 리턴] 아래 코드와 같이 dfs함수내에서 다음 depth함수의 리턴값이 나왔을 때 return true를 해야

현재 depth의 여러 노드들의 모든 다음 depth들의 결과를 계산 한 뒤에 모든 노드에대해서 false의 결과가 나온 경우에만 false가 나오게 된다.

 

static boolean dfs( int nowr, int nowc){
    board[nowr][nowc] = 'x';
    
    if(nowc == c-1)
        return true;

    for(int nextr = nowr-1; nextr<=nowr+1; nextr++)
        if(nextr >=0 && nextr < r && board[nextr][nowc+1] == '.')
            if(dfs( nextr, nowc+1))
                return true;
    
    return false;
}

기억을위해 몇자 적자면, 1번의 경우에는 다음 depth 진입의 조건을 뭐 엄청 특별하게 하는 경우가 아니고서는 무조건 틀린 구현이다.

 

 

 

LIS를 nlogn의 복잡도로 풀어야 하는 경우의 구현

 

이분탐색 : 내가 넣고싶은 값이 들어갈 수 있는 자리를 찾을 때 마다 res에 저장, while문 탈출 후 return

최장증가수열 유망성까지 평가하는 배열 K의 마지막 원소보다 array가 큰 값인 경우 그냥 추가 (길이 +1)

중간에

 

import java.util.*;
import java.util.stream.*;

public class Main {
    static int K[];
    static int binarySearch(int s, int e, int value){
        int res=-1;
        while(s <= e){
            int mid = (s+e) / 2;
            if(K[mid] >= value){
                e = mid-1;
                res = mid;
            }
            else{
                s = mid+1;
            }
            if(s == K.length)
                return -1;
        }
        return res;
    }
    
    static void input() throws Exception{
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i = 0 ; i < n ; i++)
            array[i] = scan.nextInt();
        
        K = new int[n];

        
        K[0] = array[0];
        int index = 1;
        for(int i = 1 ; i <n; i++){
            if(K[index-1] < array[i]){
                K[index++] = array[i];
            }
            else{
                K[binarySearch(0, index, array[i])] = array[i];
            }
        }
        System.out.println(index);
    }
    
    
}

 

 

 

도로 가장 길게 연결하기 

101110101011110111011에서 k개의 0을 1로 바꾸어 연속된 1의 길이가 가장 길 때의 그 길이를 구하라.

슬라이딩 윈도우 : window 안의 0의 개수를 일정하게 가져가며 0의 개수 조건이 충족될경우 최대 길이를 갱신