내일은 알고리즘

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

LCS 2번을 풀어보겠습니다.

혹시 LCS에 대한 이해가 부족하시거나, LCS 1번 문제를 아직 풀지 않은 분은

https://nodingco.tistory.com/9

이 글을 확인해주시면 감사하겠습니다.

문제는 LCS 1번과 아주 유사합니다. 하지만 단순히 LCS의 길이를 구하는 것 뿐 아니라 LCS의 내용까지 구해야합니다.

쉽게 생각하면 그저 LCS를 구하는 기존의 과정에 더해 여태까지의 String을 저장해도 될 것 같지만, String이 메모리나 연산시간을 많이 잡아먹는걸 감안하면 살짝 위험해 보입니다.

그래서 LCS를 구했던 과정을 역산해서 LCS를 알아내 보겠습니다.

예제의 풀이과정이 기록되는 DP 배열을 실제 표로 나타내어 봅시다. (실제로는 계산의 편의를 위해 좌측과 상단에 0이 들어간 배열이 더 존재합니다.)

정답 LCS인 ACAK는 위와같은 과정을 통해 구해졌다는걸 알 수 있고

최종 정답이 위치한 DP[L2][L1]의 값부터 역순으로 찾아 가는 방법도 알 수 있습니다.

위, 좌측, 대각선 좌상방향 세개의 값을 비교하여

나와 같은 값이 있으면 그 쪽으로, 나와 값이 전부 다를땐 좌상방향으로 이동하면서

그때의 Character를 역순으로 담으면 자연스럽게 답이 찾아집니다.

Stack을 이용해 역순으로 저장하는 방법을 구현하면, 코드는 아래와 같아집니다.

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		Stack<Character> stack = new Stack<Character>();

		char[] str1 = br.readLine().toCharArray();
		int l1 = str1.length;
		char[] str2 = br.readLine().toCharArray();
		int l2 = str2.length;

		int[][] dp = new int[l2 + 1][l1 + 1];

		for (int i = 1; i <= l2; i++) {
			char C = str2[i - 1];
			for (int j = 1; j <= l1; j++) {
				if (C == str1[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}
		sb.append(dp[l2][l1]).append("\n");

		int now = dp[l2][l1];
		int x = l2;
		int y = l1;

		while (isIn(x, y) && now > 0) {
			if (dp[x - 1][y] == now) {
				x--;
			} else if (dp[x][y - 1] == now) {
				y--;
			} else {
				x--;
				y--;
				now--;
				stack.push(str1[y]);
			}

		}

		while (!stack.isEmpty()) {
			sb.append(stack.pop());
		}

		System.out.println(sb);
	}

	static boolean isIn(int x, int y) {
		if (0 < x && 0 < y) {
			return true;
		}
		return false;
	}
}

주의)

LCS가 0일때 아무것도 출력하지 않아야합니다.

탐색 도중 x와 y가 ArrayIndex를 벗어나는걸 주의해주세요.

안녕하세요!

드디어 SSAFY 1년 과정이 거의 마무리 되었고, 시간이 꽤 생길것 같기 때문에!

본격적으로 블로그에 포스팅을 작성하게 되었습니다.

제가 알고리즘 문제풀이 (Problem Solving)에 주로 사용하는 언어는 JAVA이지만

C++. Python 등으로도 종종 풀이가 올라갈 것 같습니다.

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

아주 간단한 문제입니다.

백준에서 가장 많은 제출이 이루어진 문제기도 하고, 브론즈~실버 등급 대표 문제들의 정답률이 50%는 가뿐히 넘기는걸 생각하면 생각보다 정답률이 낮은 문제기도 합니다.

1000번 문제를 틀리는 이유는 여러개가 있습니다.

1. 진짜 프로그래밍 언어에 대해 하나도 모른다. 

2. 테스트케이스의 존재를 모르고 3을 출력하는 프로그램을 작성한다.

3. 자신이 작성한 언어가 아닌 다른 언어로 제출한다.

4. Main 함수, 또는 클래스의 이름을 잘못 설정한다.

5. 코드를 붙여넣는 과정에서 package, import등을 누락한다.

아무튼..

문제는 아주 간단합니다. 두개의 숫자를 입력받고, 덧셈연산의 결과값을 출력하면 됩니다.

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		System.out.println(a+b);
	}
}

이렇게요.

java 라이브러리 util 패키지의 Scanner 클래스를 import해주고

시스템의 입력인 System.in을 parameter로 새로운 Scanner 객체를 생성해주면 됩니다.

Scanner의 이름은 어떻게 정하셔도 상관없지만, 가독성과 다른 사람에게 코드를 공유할 때를 대비해 많이 사용하는 이름으로 선언해주시는게 좋습니다.

보통 기능적인 요소에서 따온 input, in 을 쓰기도 하고 Scanner 객체는 한 번 선언하고 계속 재사용하기 때문에 간단하게 scan, sc로 선언하기도 합니다. 

Scanner 클래스 안에는 여러가지 메소드가 들어있는데요.

간단한 문제이므로 입력으로 들어오는 다음 숫자를 반환하는 nextInt()를 통해 A와 B값을 받고

JAVA의 기본적인 출력함수인 System.out.println()을 통해 A+B를 출력했습니다.

조금 더 효율적인 입출력을 하고싶다! 하시는 분은

https://nodingco.tistory.com/7

이 글을 참고해주시면 감사하겠습니다!