codejcd 기술 블로그

문제

https://www.acmicpc.net/problem/1463

분석/설계

입력 숫자의 범위가 2~10의 6제곱이기때문에 입력 범위가 크고

이렇게 입력 범위가 큰 경우 완전 탐색 알고리즘을 쓰면 항상 효율성에서 걸리는 문제들이 많았습니다.

다이나믹 프로그래밍을 적용하면 복잡도 면에서 걸리지 않을 수있다고 판단했고 이를 적용했습니다.

보통 다이나믹 프로그래밍은 점화식을 이용하면 쉽게 풀리는 경향이 있습니다.

dp[i] = min(d[i-1], d[i//2], d[i//3]) + 1 

구현 코드

import java.util.Scanner;

public class Main {
	
	static int dp[] = new int[10000001]; // 1을 만들기 위한 최소 연산 사용 횟수
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int X = scanner.nextInt();
		
		for(int i=2; i<X+1; i++) {
			dp[i] = dp[i-1] + 1;
			
			if(i % 2 == 0) {
				dp[i] = Math.min(dp[i], dp[i/2] + 1);
			}
			
			if(i % 3 == 0) {
				dp[i] = Math.min(dp[i], dp[i/3] + 1);
			}	
		}
		
		System.out.println(dp[X]);
		scanner.close();
	}
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고

탑다운로도 풀이한 분들이 많이 있습니다.

편한 풀이 방식을 적용하면 될 것 같습니다.

참고

https://www.acmicpc.net/problem/1463

문제

https://www.acmicpc.net/problem/2606

분석/설계

전형적인 그래프를 탐색하는 DFS/BFS 유형의 문제이고

그래프 상 노드(컴퓨터)가 100대 이하이므로 완전 탐색으로 접근 가능한 문제로 파악했고

DFS로 구현했습니다.

구현 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;

		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 컴퓨터 수
		int M = scanner.nextInt(); // 연결된 컴퓨터 쌍의 수
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		dfs(1);
		
		int cnt = 0;
		for(int i=0; i<visted.length; i++) {
			if(visted[i]) cnt++;
		}
		System.out.println(cnt-1);
		scanner.close();
	}
}

정리

문제를 읽어보면 1번 컴퓨터부터 시작한다는 조건이 있고 

1번 컴퓨터를 통해 바이러스에 걸리는 컴퓨터 수를 구해야하므로

1번 컴퓨터까지 카운트된 숫자는 제외해줍니다.

참고

https://www.acmicpc.net/problem/2606

문제

https://www.acmicpc.net/problem/2667

분석/설계

DFS와 BFS로 완전 탐색하여 접근하는 방향으로 가닥을 잡고

인접한 상하좌우를 탐색하는 것이므로 BFS가 구현이 쉬울 것 같아 선택했다.

다른 문제들과 달리 한칸씩 띄워서 입력 받지 않기때문에 이런 부분이 조금 달랐던 것 같고

결국 입력 값을 받아 초기화하고 BFS로 어떻게 기준을 잡고 탐색하는지가 중요했던 문제입니다.

구현 코드

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

class Dot{ // X,Y 좌표를 저장하는 클래스
	int x;
	int y;
	
	public Dot(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}				
}

public class Main {
	static ArrayList<Integer> count = new ArrayList<>();
	 // 상, 하, 좌, 우를 탐색하기 위한 배열
	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
	
	public static void bfs(int arr[][], boolean visited[][], Dot dot) {
		Queue<Dot> q = new LinkedList<Dot>();
		q.offer(dot);
		visited[dot.getX()][dot.getY()] = true;
		int cnt = 0; // 주변에 존재하는 집의 수를 저장
		
		while(!q.isEmpty()) {
			Dot temp = q.poll();
			int x = temp.getX();
			int y = temp.getY();
			cnt++;
			
			for(int i=0; i<4; i++) { // 상하좌우 탐색
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				// 맵의 범위를 벗어나는 좌표는 무시
				if(nx>=arr.length || nx<0 || ny>=arr[nx].length || ny < 0) continue;
				
				// 이미 방문한 경우도 무시
				if(visited[nx][ny]) continue;
				
				if(arr[nx][ny] == 1) {
					visited[nx][ny] = true;
					q.offer(new Dot(nx, ny));
				}
			}
		}
		count.add(cnt);
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt(); // 맵의 크기 N
		int arr[][] = new int[N][N]; // N x N map
		boolean visited[][] = new boolean[N][N]; // N x N 크기의 방문여부 배열
		
		scanner.nextLine();
		for(int i=0; i<arr.length; i++) { // 맵 입력 받은 값으로 초기화
			String[] temp = scanner.nextLine().split("");
			for(int j=0; j<arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(temp[j]);
			}
		}
		Dot dot;
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				if(arr[i][j] == 1 && visited[i][j] == false) { // 맵을 탐색하면서 아파트이면서 방문하지 않은경우
					dot = new Dot(i, j);
					bfs(arr, visited, dot);
				}
			}
		}
			
		System.out.println(count.size());
		Collections.sort(count);
		for(int i=0; i<count.size(); i++) {
			System.out.println(count.get(i));
		}
		
		
		scanner.close();
	}
}

정리

좌표에 대해서 어떻게 코드로 구현할지

BFS를 구현할 때 큐에 넣고 큐에서 꺼내는 기준을 무엇으로 할지가 핵심이고

답을 구하기 위해서 어떤 값이 필요할지 처음에 잘 정의한다면 그렇게 어려운 문제는 아닙니다.

FS나 DFS를 어떻게 응용할지 많이 문제를 접해봐야할 것 같습니다.

참고

https://www.acmicpc.net/problem/2667

이번 문제는 백준 알고리즘 사이트에 문제입니다.

DFS와 BFS 관련 문제로 기본/핵심 적인 문제입니다.

문제

https://www.acmicpc.net/problem/1260

분석/설계

제목 부터과 DFS/BFS 이여서 당연히 DFS/BFS로 접근하였습니다.

기본적인 DFS/BFS 구현과 유사하지만 두 정점 사이에 여러개의 간선과 양방향 이라는 점에서 주의해야합니다.

처음에 양방향을 생각하지 않고 풀이 했을대, 예제 1번은 답이 나왔지만 2,3 번은 모두 오답이 었습니다. 

구현 코드

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

public class DFSBFS {

	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;
		System.out.print(V + " ");
		
		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void bfs(int V) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(V);
		
		visted[V] = true;
		
		while(!queue.isEmpty()) {
			int x = queue.poll();
			System.out.print(x + " ");
			for(int i=0; i<graph.get(x).size(); i++) {
				int W = graph.get(x).get(i);
				if(!visted[W]) {
					queue.offer(W);
					visted[W] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 정점의 개수
		int M = scanner.nextInt(); // 간선 열결하는 두 정점의5 번호
		int V = scanner.nextInt(); // 시작할 정점 번호
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		for(int i=1;i<=N;i++) { // 이동 간선의 이동 경우가 다수 존재할 경우 작은 정점부터 이동해야하므로 오름차순 정렬
			Collections.sort(graph.get(i));
		}
		
		dfs(V);
		visted = new boolean[N+1]; // dfs 수행 후 방문 여부 판단할 배열 초기화
		System.out.println();
		bfs(V);
		scanner.close();
	}
}

정리

DFS 재귀 함수로 BFS는 Queue를 이용해서 구현했다.

기본적인 그래프에 대한 DFS/BFS 를 구현하는 문제였고 사소한 구현 사항을 놓치지 않으면

쉽게 풀수 있는 문제입니다. 

참고

https://www.acmicpc.net/problem/1260

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/12913

분석/설계

땅따먹기 특수 규칙에 의해 주어진 land 2차 배열을 나올수 있는 경우의 수를 전부 탐색해서

최대값을 얻어야겠다고 생각했고, 바로 DFS를 떠올렸습니다.

하지만 DFS 사용 시 행의 개수가 100,000 이기 때문에 효율성 걸려서 코드 제출을 통과할수 없습니다.

구현 코드

// DFS 버전
public class Solution {

  static boolean[][] visited;
  static int res = 0;

    static int solution(int[][] land) {
        int answer = 0;
        visited = new boolean[land.length][4];
        pick(0,0,land);	
        answer = res;
        return answer;
    }
    
    static void pick(int row, int sum, int[][] land ) {
    	if(row == land.length) {
    		res = Math.max(res, sum);
    		return;
    	}
    	
    	for(int i=0; i<4; i++) {
    		if(!visited[row][i]) {
    			sum += land[row][i];
    			if(row < land.length-1) visited[row+1][i] = true;
    			pick(row+1, sum, land);
    			if(row < land.length-1) visited[row+1][i] = false;
    			sum -= land[row][i];
    			
    		}
    	}
    }
}

정답 코드(다른 사람의 코드와 비교)

class Solution {
    int solution(int[][] land) {
        int answer = 0;
     
        for(int i=1; i< land.length; i++) {
        	land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
        	land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
        	land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
        	land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
        }
        
        for(int i=0; i<4; i++) {
        	answer = Math.max(answer, land[land.length-1][i]);
        }
        
        return answer;
    }
}

비교/정리

DFS 사용 시 모든 경우의 수를 반복해서 계산하기 때문에 효율성이 떨어져 코드 제출 시 시간 초과가 발생합니다.

다이나믹 프로그래밍을 사용하면 효율성을 개선하고 비교적 쉽게 풀수 있는 문제입니다.

참고

https://programmers.co.kr/learn/courses/30/lessons/12913

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/12945

분석/설계

피보나치는 작은 범위라면 재귀 호출도 가능하고, 범위가 크다면 다이나믹 프로그래밍이 효율이 좋습니다.

10,000까지의 n의 범위를 보고 다이나믹 프로그래밍을 적용했습니다.

구현 코드

    public BigInteger solution(int n) {
        BigInteger[] d = new BigInteger[n+1];
        d[1] = BigInteger.ONE;
        d[2] = BigInteger.ONE;
  
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1].add(d[i - 2]);
        }
        BigInteger T = new BigInteger("1234567");
        BigInteger answer = d[n].remainder(T);
        
        return answer;
    }

정답 코드(다른 사람의 코드와 비교)

    public static int solution(int n) {
        int answer = 0;
        //n이 3일때
        //f(3) = f(1)+f(2) = 1+1 = 2이므로 숫자 초기화
        int num1 = 1;
        int num2 = 1;
        
        if(n==1 || n==2) return 1;
        else {
            for(int i=3; i<=n; i++) {
                answer = (num1+num2)%1234567;
                num1 = num2;//전전수
                num2 = answer;//전수
                
            }
            return answer;
        }
    }

비교

n의 범위만 보고 결과값이 크다는 생각에 BigInteger를 적용하여 처리하였으나

1234567로 나눈 나머지를 리턴하기때문에 굳이 BigInteger를 사용하지

않아도 됩니다. 어쨌든 BigInteger로 코드 제출하여도 만점으로 채점은 됩니다.

정리

아는 문제이고 쉬운 문제라도 끝까지 문제의 조건을 잘 눈여겨봐야 

필요하지 않는 코드 작성을 줄일수 있습니다.

참고

https://programmers.co.kr/learn/courses/30/lessons/12945