이코테 0713 - BFS, 정렬

HyeJi9908·2022년 7월 13일
0

[JAVA] ThisIsCodingTest

목록 보기
4/12
post-thumbnail

🔎 개념

선택정렬

: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복. *GIF

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i; // 가장 작은 데이터의 인덱스
        
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

삽입정렬

: 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬 *GIF

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

✨ 퀵 정렬

  1. 배열 중에 하나의 원소 고르기 : 피벗 선택
  2. 피벗 앞에는 피벗보다 값이 작은 원소들이, 피벗 뒤에는 피벗보다 큰 원소들이 오도록해서 배열을 둘로 나눈다 : 분할 하기
  3. 분할된 두 개의 배열에 대해 재귀적으로 위의 과정 반복하기
    *이코테 강의
    *GIF
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 원소가 1개인 경우 종료
        int pivot = start; // 피벗은 첫 번째 원소
        int left = start + 1;
        int right = end;
        while (left <= right) {
        
            // 왼족에서 부터 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) left++;
            
            // 오른쪽에서 부터 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            }
            
            // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }

    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        quickSort(arr, 0, n - 1);

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

계수 정렬

: 배열의 값과 동일한 인덱스에 갯수를 누적하여 오름차순 정렬

import java.util.*;

public class Main {
	
    // 0부터 9까지의 원소로 이뤄진 배열
    public static final int MAX_VALUE = 9;

    public static void main(String[] args) {
    	
        int n = 15;
        // 모든 원소의 값이 0보다 크거나 같다고 가정
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
        // 최대 인덱스가 정렬하려는 배열의 최댓값과 동일하도록 배열 선언(모든 값은 0으로 초기화)
        int[] cnt = new int[MAX_VALUE + 1];

        for (int i = 0; i < n; i++) {
            cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
        }
        for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
            for (int j = 0; j < cnt[i]; j++) {
                System.out.print(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
            }
        }
    }

}

특정 key값을 기준으로 정렬

: 'implements Comparable' 함으로써 Collections.sort(클래스 객체)했을 때 원하는 기준으로 정렬됨

import java.util.*;

class Fruit implements Comparable<Fruit>{
	
		
	private String name;
	private int score;
	
	public Fruit(String name, int score) {
		this.name = name;
		this.score = score;
	}

	public String getName() {
		return this.name;
	}

	public int getScore() {
		return this.score;
	}
	

	// 정렬 기준 : 오름차순
	@Override
	public int compareTo(Fruit o) {
		if(this.score < o.score) return -1;
		return 1;
	}

}

public class Java0713_4 {
	
	public static void main(String[] args) {
		List<Fruit> fruits = new ArrayList<>();
		
		fruits.add(new Fruit("바나나",2));
		fruits.add(new Fruit("사과",5));
		fruits.add(new Fruit("당근",3));
		
		Collections.sort(fruits); // Fruit에서 오버라이드한 내둉대로 정렬
		
		for(int i=0; i<fruits.size();i++) {
			System.out.print("(" + fruits.get(i).getName() + "," + fruits.get(i).getScore()+ ") ");
		}
	}
}

// 결과 : [('바나나',2),('당근',3),('사과',5)]

📚 미로탈출 - BFS

import java.util.*;

// 큐에 좌표를 쉽게 저장하고, 접근하기 위해 클래스 생성!
class Node{
	
	private int y;
	private int x;
	
	public Node(int y,int x) {
		this.y= y;
		this.x= x;
	}

	public int getX() {
		return this.x;
	}

	public int getY() {
		return this.y;
	}
}


public class Java0713_3 {
	
	public static int n,m;
	public static int[][] arr;
	public static int[][] d= {{-1,0},{1,0},{0,-1},{0,1}};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		m=sc.nextInt();
		sc.nextLine();
		
		for(int i=0;i<n;i++) {
			String str = sc.nextLine();
			for(int j=0;j<m;j++) {
				arr[i][j]=str.charAt(j) - '0';
			}
		}
		
		System.out.print(bfs(0,0));
		
	}

	public static int bfs(int y, int x) {
		
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(y,x));
		
		while(!q.isEmpty()) {
			
			Node node = q.poll();
			y = node.getY();
			x = node.getX();
			
			// 현재 위치에서 상하좌우 좌표 확인
			for(int[] dir:d) {
				
				int ny = y+ dir[0];
				int nx = x+dir[1];
				
				if(ny<0||ny>=n||nx<0||nx>=m) continue;
				if(arr[ny][nx] == 0) continue;
				
				// 해당좌표를 처음 방문하는 경우에만 
				if(arr[ny][nx]==1) {
					arr[ny][nx] = arr[y][x]+1;
					// 현재좌표에 이전좌표까지의 최단거리+1 저장
					
					q.offer(new Node(ny,nx));
				}
			}
		}
		
		// 가장 오른쪽 아래까지의 최단거리 반환
		return arr[n-1][m-1];
		
	}
}

0개의 댓글