순서가 같더라도 조합이 다르면 다르게 취급

조합이 같더라도 순서가 다르면 다르게 취급

중복조합

조합

중복 순열

백트래킹

순열

BFS

시작점이 2개일 때

시작점 2개를 먼저 큐에 넣고 시작합니다.

같은 파트의 크기 세기

같은 파트의 개수 세기

최단 거리 측정

BFS를 사용할 때 큐에 쌓이는 순서는 반드시 거리순입니다.

트리의 지름 구하기

임의의 정점 1개 구하기
정점 x에서 가장 먼 정점y 구하기
정점 y에서 가장 먼 정점 z 구하기 (=트리의 지름)

가장 먼 정점 구하기

dist 배열을 이용해 거리를 구하고 가장 긴 거리를 갖는 노드를 반환한다.

트리

DFS

트리의 판별하기

들어오는 간선이 없는 루트 노드가 정확히 1개 존재하는가
모든 노드는 반드시 단 하나의 들어오는 간선이 있다.
루트 노드에서 모든 노드를 방문할 수 있으며 이러한 경로는 유일하다.

단순히 값을 찾기


int binarySearch(int[] arr, int target){  
  
    int l = 0;  
    int h = arr.length;  
  
    while(h>l){  
        int mid = (l+h)/2;  
        if(arr[mid]==target){  
            return mid;  
        }else if(arr[mid]>target){  
            h = mid;  
        }else{  
            l = mid+1;  
        }  
    }  
    return -1;  
}

가장 오른쪽 인덱스 구하기

int upperIdx(int target, int[] arr){
	int l = 0;
	int h = arr.length;
	while(h>l){
		int mid = (l+h)/2;
		if(arr[mid]>target) h = mid;
		else l = mid+1;
	}
	
	return l;

}

가장 왼쪽 인덱스 구하기

int lowerIdx(int target, int[] arr){
	int l = 0;
	int h = arr.length;
	while(h>l){
		int mid = (l+h)/2;
		if(arr[mid]>=target) h = mid;
		else l = mid+1;
	}
	
	return l;

}

값의 등장 횟수 구하기

값의 등장 횟수 = 정렬이 유지되는 제일 왼쪽과 오른쪽 인덱스 차이

이진탐색

좌표 압축하기

각 배열의 값보다는 요소들의 대소 관계만 알고 싶을 때 크기순 인덱스로 붙여버린다.

중복값을 지운다.
이진탐색으로 해당값의 인덱스를 찾는다.

줄단위 배열 입력받기

private static int[] getArr() throws IOException{  
    return Arrays.stream(buffer.readLine().split("\\s+"))  
            .mapToInt(Integer::parseInt)  
            .toArray();  
}

배열 StringBuilder로 출력하기

// 스트림을 사용하여 결과를 StringBuilder에 추가  
String result = Arrays.stream(compressedPositions)  
        .mapToObj(String::valueOf)  
        .collect(Collectors.joining(" "));

필터 걸어서 새로운 배열 만들기

int[] compressedPositions = IntStream.range(0, n)  
        .map(i -> Collections.binarySearch(uniquePositions, positions[i]))  
        .toArray();

Parametric Search(최소값 구하는 경우)

private static long getAnswer(int[] costs, int limit){  
    long l = 0;  
    long h = Arrays.stream(costs).sum();  
  
    while(h>l){  
        long mid = (h+l)/2;  
  
        if(isValid(mid, costs, limit)){  
            h=mid;  
  
        }else{  
            l=mid+1;  
        }  
    }  
  
    return l;  
}

Parametric Search(최댓값 구하는 경우)

private static long get(long[] lengths, long maxLength, long numOfOrder){  
    long l = 0;  
    long h = maxLength;  
  
    while(h>l){  
        long mid= (l+h+1)/2;  
  
        if(isValid(mid, numOfOrder, lengths)){  
            l=mid;  
        }else{  
            h=mid-1;  
        }  
    }  
  
  
    return l;  
  
}

달팽이 모양으로 격자 이동하기

안에서 밖으로 이동하는 로직을 예시로 설명합니다.

Pasted image 20240803123705.png

방향의 사이클이 전부 완료 후 이동 횟수가 1씩 증가합니다.

⬆︎ ➡︎ 로 이동할 때는 1, 3, 5 ... 칸씩 이동하고,

⬇︎ ⬅︎ 로 이동할 때는 2, 4, 6 ... 칸씩 이동합니다.

밖에서 안으로 이동하는 경우 위와 반대로 생각하면 되므로 방향만 바꿔줍니다.



//상우하좌 순서대로 넣습니다. 
int[] dx = {-1,0,1,0};
int[] dy = {0,1,0,-1};

int currentX = n/2;
int currentY = n/2; 
int moveDir = 0;
int moveNum = 1; 

while(currentX>0||currentY>0){
	//하나의 방향 이동 
	for(int i=0; i<moveNum; i++){
		//안에서 밖으로 이동하는 달팽이의 경우 
		//이동하는 도중 0,0으로 오게 되면 움직이는 것을 종료한다. 
		if(currentX==0&&currentY==0)break; 	
	}
	//방향을 전환합니다. 
	moveDir = (moveDir+1)%4;

	//윗 방향 또는 아랫 방향이 될 때마다 움직여야할 횟수가 1증가합니다. 
	if(moveDir==0||moveDir==2) moveNum++;

}

반복문 시작 조정

isUsed 사용

dis[nx][ny] = dis[current.x][current.y]+1

큐에서 뺄때마다 세기

시작점 위치 세기