Yong's Tech Story

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class part7_12 {

	static int[][] graph;
	static int[] visit;
	static int N;
	static int cnt;

	public static void main(String[] args) throws IOException {
		// 경로탐색(DFS)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer token = new StringTokenizer(br.readLine());
		N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());

		String[] str = new String[M];

		for (int i = 0; i < M; i++) {
			str[i] = br.readLine();
		}
		bw.write(Integer.toString(solution(str, N)));
		bw.flush();
		bw.close();
	}

	private static int solution(String[] array, int N) {
		graph = new int[N + 1][N + 1];
		visit = new int[N + 1];
		for (int i = 0; i < array.length; i++) {
			String[] str = array[i].split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			graph[a][b] = 1;
		}
		visit[1] = 1;
		dfs(1);
		return cnt;
	}

	private static void dfs(int n) {
		if (n == N) {
			cnt++;
		} else {
			for (int i = 1; i < graph.length; i++) {
				if (graph[n][i] == 1 && visit[i] == 0) {
					visit[i] = 1;
					dfs(i);
					visit[i] = 0;
				}
			}

		}
	}
}

주요 핵심 포인트

1. String으로 들어오는 경로 (x1, x2) 를 graph[x1][x2]에 저장한다.

2. 모든 경로를 graph에 저장하였을시 연결점을 행과 열로 구분하여 볼 수 있다.

3. 이미 방문한 경로는 다시 방문할수 없으므로, 방문하였을시 visit[n]을 1, 방문을 종료하였을시 0으로 변경함으로써 동일한 숫자 경로를 0으로 변경한다.

4. if문에서 방문하지 visit[n] == 0 조건을 걸어줌으로써 방문하지 않은 숫자에 대해서만 탐색하도록 하는 알고리즘이다.

5. 방문을 종료하고 나서는 해당 숫자를 다시 한번 방문 하는 케이스를 고려하기 위하여 vsit[n] = 0 으로 초기화한다.

6. 구하고자 하는 N, 즉  dfs(N)이 도달하였을때에 카운트를 증가하였다.

개선해야할 사항

1.  해당 문제를 풀려고 하였으나 중간에 막혀 다른 강의 소스를 참조하게 되었다. 스택으로 풀고자 하였으나, 스택 프레임을 제대로 구현하지 못하여 정상적인 데이터를 출력하지 못하였다. 모든 케이스를 탐색하기 위하여 해당 케이스를 방문하였는지, 방문하지 않았는지를 생각하고 트리를 그려 확인하는 연습이 필요할듯 하다. dfs는 많은 연습이 필요한 알고리즘이다.

문제 풀이 (JAVA)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class part7_8 {
	static int K; // 송아지 위치
	static int level; // 레벨(점프횟수)

	public static void main(String[] args) {
		// 송아지 찾기1(BFS)
		Scanner input = new Scanner(System.in);

		int N = input.nextInt(); // 철수의 위치
		K = input.nextInt(); // 송아지의 위치
		bfs(N);
	}

	private static void bfs(int N) {
		Queue<Integer> queue = new LinkedList<>();
		int min = Integer.MAX_VALUE; // 최소 거리 변수
		queue.offer(N); // 철수의 위치 N 삽입
		while (queue.peek() != K) { // 철수의 위치가 송아지의 위치가 아닐동안 반복
			int cur = queue.peek(); // 철수의 현재 위치 변수
			min = Integer.MAX_VALUE; // 최소 거리 변수 초기화
			queue.offer(cur + 1); // 점프 +1
			queue.offer(cur - 1); // 점프 -1
			queue.offer(cur + 5); // 점프 +5
			int len = queue.size(); // 큐의 경우 사이즈
			for (int i = 0; i < len; i++) {
				int num = Math.abs(K - queue.peek()); // 최소거리 변수(송아지의 위치-철수의 점프 후 위치)
				if (min > num) { // 최소 거리를 저장
					min = num;
				}
				queue.offer(queue.poll()); // 큐의 변수를 한바퀴 돌린다.
			}
			for (int i = 0; i < len; i++) {
				// 지정한 최소거리가 아니라면 큐에서 제거
				if (min != Math.abs(K - queue.peek())) {
					queue.poll();
				} else {
					// 지정한 최소거리라면 큐에 다시 넣는다.
					queue.offer(queue.poll());
				}
			}
			// 한번 다 돌았을시 점프후 최소거리 변수만 큐에 남음.
			level++; // 횟수 카운트 증가
		}
		System.out.print(level);
	}
}

주요 핵심 포인트

1.  점프 한번시 +1, -1 , +5 만큼 갈 수 있으므로 경우의수는 3가지가 된다. 그 중 목표값 K와 가장 가까운 값을 K- (이동한값) 중 가장 크기가 적은 값이 송아지의 위치와 가까워지므로 최소값을 Math.abs()로  구하였다.

2. 철수의 첫번째 값 N을 큐에 넣고, +1,-1,+5의 증가되는 값들을 뒤이어 차례로 넣는다.

ex) 철수의 처음 위치 = 5 라면 큐 (5 <- 6 <- 4 <- 10) , 송아지의 위치 = 14

3. 송아지의 위치와 큐에 적재되어 있는 값들 중 (송아지의 위치- 적재된 큐) 를 하여 가장 차이가 적은 값이 최적의 이동값으로 큐를 앞부터 비교하여 한번씩 재적재하여 최소값을 구한다.

ex) 14 - 5 = 9 , 14 - 6 = 8 , 14 - 4 =10 , 14 - 10 = 4   => 최소값 = 4

4.  재적재된 큐와 최소값이 일치하는지 다시 비교하여 일치하지 않는 경우 제거하고, 일치하는 경우 큐에 재적재하였다.

ex) 큐( 5 <- 6 <- 4 <-10) -> (6 <- 4 <- 10) -> (4<- 10) -> (10)

5. 최종적으로 하나의 값이 남으며 해당 값이 다음 점프 값이 되며, 점프횟수를 가리키는 level을 1 증가시킨다.

6. 1~5를 반복하여 점프한 최종 값이 송아지의 위치와 같아진다면 반복을 종료한다.

개선해야할 사항

1.  위처럼 생각하여 풀이하였을 때, 시간 효율성은 괜찮게 나왔다. 강의와 비교하였을때 강의에서의 시간 효율성보다 내가 풀었던 시간 효율성이 조금 더 괜찮지 않나 싶다. K의 값이 크더라도 5씩 증가하기 때문에 K/5 * 2n번을 반복하므로 모든 수를 비교하지는 않아 시간 효율성이 좋게 나온듯 하다. bfs는 최적의 경로 문제를 풀기에 적절한 문제임을 인지하자.

문제 풀이 (JAVA)

import java.util.*;
public class part6_8 {

	public static void main(String[] args) {
		// 이분검색
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int M = input.nextInt();
		int [] arr = new int[N];
		for(int i=0; i<N; i++) {
			arr[i]=input.nextInt();
		}
		int answer = solution(arr,N,M);
		
		System.out.print(answer);
	}
	private static int solution(int [] a, int N, int K) {
		Arrays.sort(a); // 숫자 오름차순 정렬
		int result=0;
		int idx=0; // 탐색할 인덱스 변수 선언
		int lt = 0, rt=N-1; // 배열 투포인터 선언
		while(a[idx] != K) { // K일때까지 이분검색 
			idx=(lt+rt)/2; // 이분검색을 통한 배열의 중앙값 인덱스
			if(a[idx]==K) { // K일시 종료
				result=idx+1; 
				break;
			}
			if(a[idx] < K) { // 중앙값이 K보다 작다면
				lt = idx+1; // 오른쪽을 탐색해야 하므로 lt 포인터 재선언
			}else if(a[idx] > K) { // 중앙값이 K보다 크다면
				rt = idx-1;  // 왼쪽을 탐색해야 하므로 rt 포인터 재선언
			}
		}		
		return result;
	}
}

주요 핵심 포인트

1.  이분검색은 검색의 효율성을 높이기 위한 것으로 숫자가 오름차순으로 정렬되어 있을 때 중앙값을 반복 탐색하여 값을 찾는 알고리즘이다.

2. 중앙값< 찾을값 이라면 중앙값을 기준으로 오른쪽에 있으므로 왼쪽 포인터 증가,

    중앙값> 찾을값 이라면 중앙값을 기준으로 왼쪽에 있으므로 오른쪽 포인터 감소

개선해야할 사항

1.  이분탐색시 lt와 rt의 인덱스 설정하는 부분을 헷갈리지 말자. lt는 idx+1, rt는 idx-1 이다.

문제 풀이 (JAVA)

import java.util.*;
public class part6_3 {

	public static void main(String[] args) {
		// 삽입 정렬
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		
		int [] a = new int[N];
		for(int i=0; i<N; i++) {
			a[i]=input.nextInt();
		}
		int [] answer=solution(a,N);
		for(int i=0; i<N; i++) {
			System.out.print(answer[i]+" ");
		}
	}
	private static int [] solution(int [] a, int n) {
		int tmp=0;
		for(int i=1; i<n; i++) { // 1~N까지 반복
			for(int j=i; j>0; j--) { // i번째부터 1번째까지 반복
				if(a[j-1] > a[j]) { // 앞의 숫자가 크다면 스왑
					tmp = a[j-1];
					a[j-1] = a[j];
					a[j] = tmp;
				}
			}
		}
		return a;
	}
}

주요 핵심 포인트

1.  삽입정렬은 인덱스 1번째부터 0번과 비교한후 교환, 2번째부터 1번, 0번과 순차적 비교하여 값 교환 등 순차적으로 끝자리부터 앞쪽으로 밀고나가는 형식이다.

2. 따라서 1번째부터 반복하여 j를 i번째로 두어 반복 횟수를 감소시켰다.

개선해야할 사항

1.  삽입정렬은 1번째 인덱스부터 앞쪽으로 비교하여 밀고나가는 형식이다. 버블정렬과 혼돈되지 않도록 주의하자.