Yong's Tech Story

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// 주식
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long max = 0;
		long sum = 0;
		int N = Integer.parseInt(st.nextToken()); // 테스트케이스 수
		long[] arr;
		List<Long> list = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			sum = 0;
			int idx = 0;
			max = 0;
			int n = Integer.parseInt(br.readLine());
			arr = new long[n];
			st = new StringTokenizer(br.readLine(), " ");
			while (st.hasMoreTokens()) {
				arr[idx++] = Integer.parseInt(st.nextToken());
			}
			for (int j = n - 1; j >= 0; j--) {
				long curMoney = arr[j];
				if (curMoney > max) {
					max = curMoney;
				} else {
					sum += (max - curMoney);
				}
			}
			list.add(sum);
		}
		for (Long n : list) {
			System.out.println(n);
		}
	}

}

문제 풀이

1. 해당 문제는 그리디 알고리즘 문제로 항상 최댓값에서 팔아야 하기 때문에 배열의 끝부터 탐색을 해야 한다.

2. 백준 문제 제출시 4%에서 오류가 발생한다면 변수를 Integer가 아닌 Long 타입으로 변환해주어야 한다. 숫자의 범위가 32bit를 넘기 때문이라고 한다.

3. for문을 배열의 끝부터 탐색하여 현재 값이 max 값일 경우, 값을 교체해주고 max가 아닐 경우 max값과 현재값의 차를 이익으로 누적하면 된다.

결론

: 그리디 알고리즘에는 다양한 문제 접근 방식이 필요한듯 하다. 필자는 문제 접근 방식이 생각나지 않아 다른 사람의 코드를 참고하였다.

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr; // 이차원 배열
	static int totalCnt; // 영역의 총 개수
	static boolean[][] visited; // 방문 여부 배열
	static int size = 0; // 영역의 넓이
	static int[] dx = { 1, 0, -1, 0 }; // 4방향 
	static int[] dy = { 0, 1, 0, -1 }; 
	static int M; // 행 개수
	static int N; // 열 개수

	public static void main(String[] args) throws IOException {
		// 영역 구하기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());// 행 개수
		N = Integer.parseInt(st.nextToken());// 열 개수
		int K = Integer.parseInt(st.nextToken());// 입력 줄

		arr = new int[M][N];
		visited = new boolean[M][N];

		List<Integer> list = new ArrayList<>(); // 영역 넓이 저장 리스트

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());

			int lx = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 X
			int ly = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 Y
			int rx = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 X
			int ry = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 Y
			
            for (int x = ly; x < ry; x++) { // 배열의 x는 꼭짓점 Y
				for (int y = lx; y < rx; y++) { // 배열의 y는 꼭짓점 X
					arr[x][y] = 1; // 색칠 된 도형의 경우 1로 선언
				}
			}
		}

		for (int x = 0; x < M; x++) {
			for (int y = 0; y < N; y++) {
  				// dfs에서 연결 되지 않은 0으로 x,y를 탐색한다.
				if (visited[x][y] == false && arr[x][y] == 0) {
					size = 1; // 현재 위치 사이즈 ==1 로 초기화
					visited[x][y] = true;
					totalCnt++; // if조건에 걸렸을때 하나의 영역의 시작이다.
					dfs(x, y);

					list.add(size); // dfs 종료 시 계산된 사이즈 추가
				}
			}
		}

		Collections.sort(list); // 오름차순 정렬

		System.out.println(totalCnt);
		for (Integer n : list) {
			System.out.print(n + " ");
		}
	}

	private static void dfs(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; // 다음 탐색할 X
			int ny = y + dy[i]; // 다음 탐색할 Y
			if (nx >= 0 && nx < M && ny >= 0 && ny < N && visited[nx][ny] == false && arr[nx][ny] == 0) {
				visited[nx][ny] = true;
				size++;
				dfs(nx, ny);
			}
		}
	}

}

문제 풀이

1. 해당 문제는 영역을 구하는 문제로 색칠된 도형의 넓이가 아닌 색칠하지 않은 도형의 넓이를 구하는 문제이다.

2. 문제에서 제시 되는 꼭짓점의 도형맵을 아래로 뒤집게 되면, 입력받은 꼭짓점과 이차원 배열의 (x,y)가 일치하게 된다.

3. 단, 오른쪽 꼭짓점의 경우, 입력 꼭짓점 rx-1, ry-1까지 반복문을 계산하여 도형의 넓이를 구해야 일치한다.

4. 나머지는 기존의 dfs 공식을 사용한다.(경계값 체크 필수)

결론

: 해당 문제는 dfs를 변형한 문제로, 꼭짓점의 위치를 이차원 배열의 위치와 매핑시켜 색칠 된 도형의 넓이를 구하는 것이 핵심이다. 입력 변수를 받아 arr를 잘 입력하였다면, 기존의 dfs 공식을 써서 풀 수 있다.

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

문제 풀이 (JAVA) 

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

public class Main {
	static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접 그래프 리스트
	static int[][] arr; // 이차열 배열 변수
	static boolean[] visited; // 방문 여부 배열 변수
	static int N;

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

		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		arr = new int[N + 1][N + 1];

		for (int i = 0; i <= N; i++) {
        	// 인접 그래프 리스트 생성자 추가
			graph.add(new ArrayList<>());
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if (num == 1) {
					graph.get(i).add(j); // 인접 그래프 리스트 요소 추가(a->b 간선)
				}
			}
		}
		
        // 1부터 N까지 경로 dfs 반복하여 탐색
		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			dfs(i, i);
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(arr[i][j] + " ");

			}
			System.out.println();
		}
	}

	private static void dfs(int n, int start) {
		for (Integer next : graph.get(n)) {
			if (visited[next] == false) {
				visited[next] = true;
				arr[start][next] = 1; // 1부터 ~ N까지 start를 저장하여 dfs 배열에 저장
				dfs(next, start);
			}
		}
	}

}

문제 풀이

1. 경로를 탐색하는 문제로 다양한 방법이 있지만 DFS를 사용

2. 처음에는 dfs함수의 visited=true -> dfs -> visited=false로 하였지만, 시간 초과 발생

3. visited를 false로 할 필요가 없는 이유는 start 노드에서 N까지 갈 수 있는지만 보면 되기 때문에 모든 경우의 N을 구할 필요가 없기 때문이다.

4. 따라서 1~N까지 start 노드를 넘겨 dfs가 돌면서 방문하였을때, 연결이 된 노드로 dfs가 끝나면 간선간의 연결 여부를 알 수 있다.

결론

: 문제의 접근을 모든 경우의 수 가 아닌 1~N까지의 숫자가 다른 숫자 노드와 연결 되는지 여부를 생각하여 접근한다면 쉬웠을 것이다. 다양한 경우의 경로 탐색 문제를 많이 풀어봐야겠다는 생각을 하였다.

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

문제 풀이 (JAVA)

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

public class baekjoon1806 {
	static int[] arr;
	static int N;
	static int S;

	public static void main(String[] args) throws IOException {
		// 부분합
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 수열 개수
		S = Integer.parseInt(st.nextToken()); // 구하고자 하는 부분합

		arr = new int[N];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int result = subTotal(); // 부분합 구하는 함수 호출

		System.out.println(result);
	}

	private static int subTotal() {
		int lt = 0, rt = 0; // 왼쪽 포인터 , 오른쪽 포인터 변수
		int sum = 0;
		int min = Integer.MAX_VALUE;
		int pnum = 0; // 포인터간 거리 변수

		while (rt < arr.length) {
			if (sum >= S) {
				pnum = rt - lt; // 포인터간 거리 = 부분합의 개수

				min = Math.min(min, pnum); // 최소 부분합 개수 비교

				sum -= arr[lt++]; // 왼쪽 포인터 증가
			} else if (sum < S) {
				sum += arr[rt++]; // 오른쪽 포인터 증가
			}
		}

		if (min == Integer.MAX_VALUE) { // 최솟값의 변화가 없다면 0을 반환
			return 0;
		}

		return min;
	}

}

주요 핵심 포인트

1. 투 포인터의 개념을 응용한 문제로 투 포인터  개념 공부가 필요하다.

2. while문에서 오른쪽 포인터의 값이 끝인지만 체크하는 이유는 sum이 구하고자 하는 부분합 S 보다 클 경우, 왼쪽 포인터를 1씩 증가시키고, 부분합 S보다 작을 경우에는 오른쪽 포인터를 증가시키기 때문에 동적으로 부분합의 개수를 구할 수 있게 된다.

3. min == MAX_VALUE라면 수열의 모든 부분합이 S를 넘기지 못하였을 때 0을 리턴해주고 함수가 종료 된다.  

개선해야할 사항

: 처음에는 lt의 값을 체크하는 while문을 넣어 총 2개의 while문을 사용하였다. 하지만 rt의 값만 체크하는 while문 만으로도 투포인터를 풀 수 있다는 것을 알게 되었다. 투 포인터에 대한 개념을 좀 더 자세히 가져 갈 수 있도록 해야겠다.