이진 탐색

시간 복잡도 O(log N)

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

투포인터 탐색

시간 복잡도 O(N)

연속 부분 수열의 합

int findExactSum(int[] arr, int target) {
	int start = 0;
    int end = 1;
    
    int currentSum = arr[0];
    int count = 0;
    
    while(start < arr.length) {
    	if(currentSum == target) {
        	count++;
            if(end < arr.length) {
            	currentSum += arr[end++];
            }else {
            	currentsum -= arr[start++];
            }
   		}else if(end < arr.length && currentSum < target) {
        	curretnSum += arr[end++];
        }else {
        	currentSum -= arr[start++];
        }
    }    
        return count;
}

두 수의 합이 특정값이 되는 쌍

boolean findTwoSum(int[] arr, int target) {
       int left = 0;
       int right = arr.length - 1;
      
       while (left < right) {
           int sum = arr[left] + arr[right];

           if (sum == target) {
               System.out.println("찾은 두 수: " + arr[left] + ", " + arr[right]);
               return true;
           }else if (sum < target) {
               left++;
           }else {
               right--;
           }
       }
       
       return false;
   }

정렬 알고리즘

계수 정렬

시간 복잡도 O(N + K)(K는 최대값)

void countingSort(int[] arr) {
	int max = arr[0];
    for(int i=0; i<arr.length; i++){
    	if(arr[i] > max){
        	max = arr[i];
        }
    }
    
    int[] counts = new int[max+1];
    
    for(int num : arr) {
    	counts[num]++;
    }
    
    int index = 0;
    for(int i=0; i<=max; i++){
    	while(counts[i] > 0) {
        	arr[index] = i;
            idex++;
            counts[i]--;
        }
    }
}

2차원 배열

폭탄 피하기 게임

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        for (int tc=0; tc<T; tc++) {
            int N = scanner.nextInt();
            int[][] board = new int[N][N];

            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    board[i][j] = scanner.nextInt();
                }
            }

            boolean[][] visited = new boolean[N][N];

            int[] dx = {0,0,-1,1}; 
            int[] dy = {-1,1,0,0};

            int safeCount = N*N;

            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {

                    if(board[i][j]==1) {
                        if(!visited[i][j]) {
                            visited[i][j] = true;
                            safeCount--;
                        }

                        for(int d=0; d<4; d++) {
                            int nx = j, ny = i;

                            while(true) {
                                nx += dx[d];
                                ny += dy[d];
                                
                                if(nx < 0 || nx >= N || ny < 0 || ny >=N) break;

                                if (!visited[ny][nx]) {
                                   
                                    visited[ny][nx] = true;
                                    safeCount--;
                                }
                            }
                        }
                    }
                }
            }
            System.out.println(safeCount);

        }
    }