문제


boj.kr/1463



풀이 & 코드

 

- 우선 어떤 유형의 문제인지 파악이 필요합니다

여기서는 동적 프로그래밍 (dynamic programming)의 문제입니다. 즉, 큰 문제를 작은 문제로 나누어 푸는 것 입니다.

작은 문제들이 반복되고, 작은 문제들의 값이 같을때 이를 동적 프로그래밍이라고 하는데 메모제이션 이라는 기법으로 문제를 접근합니다.


작은 문제들의 결과값은 항상 같기에 이 결과를 어떤 곳에 저장하여 놓는 것입니다.


- 이쯤 1463번 문제의 유형을 알았으니 동적프로그래밍의 해결방법을 찾습니다.

Bottom-up, Top-Down 방식이 있습니다. 어떤 것이 무조건 좋다는 답은 없고, 그때 그때 상황에 맞춰 적용하면 됩니다.


- 여기서는 Bottom-up 방식으로 풀었습니다.




/**
* dp
* bottom-up 방식
* 점화식 solve
*/

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] dp = new int[n + 1];

dp[1] = 0;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;

    if (i % 3 == 0) { dp[i] = Math.min(dp[i], dp[i / 3] + 1); }

    if (i % 2 == 0) { dp[i] = Math.min(dp[i], dp[i / 2] + 1); }
}
System.out.println(dp[n]);

- 1) 3으로 나누어 떨어질 경우 : D[N] = D[N/3] + 1

- 2) 2로 나누어 떨어질 경우 : D[N] = D[N/2] + 1

- 3) 1 뺀다 : D[N] = D[N-1] + 1


다음 규칙의 최솟값을 메모제이션하여 결과값을 출력하여 줍니다.


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제


boj.kr/10818



풀이 & 코드

 

값을 입력 받을때마다 최소/최대값과 비교하여 줍니다

int max = -1000001;
int min = 1000001;
for (int i = 0; i < cnt; i++) {
int num = scanner.nextInt();
if (max < num) {
max = num;
}
if (min > num) {
min = num;
}
}

System.out.println(min + " " + max);


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제


boj.kr/10951



풀이 & 코드

 

입력이 없을때까지 체크하여 준다

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input;
while ((input = br.readLine()) != null) {
String[] nums = input.split(" ");
System.out.println(Integer.parseInt(nums[0]) + Integer.parseInt(nums[1]));
}
}


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

링크


문제링크



풀이 & 코드



먼저, 첫번째 테스트 케이스를 분석해보자


입력 값으로


7과 3 1 3 7 3 4 6 숫자들이 들어 왔다.


이 숫자를 배열로 생각하여 나열해 보면

1 2 3 4 5 6 7  번째 사람


3 1 3 7 3 4 6  지목한 사람



2 -> 1 -> 3 -> 3


5 -> 3 -> 3


4 -> 7 -> 6 -> 4 


가리키는 방향으로 부터 사이클이 생성 되고, 팀이 생성되는 것일 확인 할 수 있다.


1번째 (3), 2번째 (4, 7, 6) 팀 X ( 2, 1, 5 )



이렇게 사이클이 생성될 경우 팀이 생성 된다는 것을 알 수 있고


우리가 많이 풀었던 그래프 문제라는 것을 인지 할 수 있다.



package hwang;

import java.util.*;
import java.io.*;

public class Hwang9466 {

private static int[] graph;
private static int count = 0;
private static boolean[] visited;
private static boolean[] finished;

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;

int T = Integer.parseInt(br.readLine());

while(T-- > 0) {

int N = Integer.parseInt(br.readLine());
graph = new int[N + 1];
visited = new boolean[N + 1];
finished = new boolean[N + 1];
count = 0;

st = new StringTokenizer(br.readLine());
for (int i = 1; i<= N; i++) {
graph[i] = Integer.parseInt(st.nextToken());
}

for (int i = 1; i<= N; i++) {
dfs(i);
}

System.out.println(N - count);
}
}

private static void dfs(int now) {

if (visited[now]) {
return;
}

visited[now] = true;
int next = graph[now];

if (!visited[next]) {
dfs(next);
} else {
if (!finished[next]) {
count++;
for (int i = next; i != now; i = graph[i]) {
count++;
}
}
}

finished[now] = true;
}
}


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제 링크


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



코드 & 풀이


입력된 간선을 보고 연결 요소 (Connected Component)를 구해야 합니다.


연결요소란?


그래프 G에서 노드와 엣지가 서로 겹치지 않는(independent) 부그래프를 G 요소(component)라고 합니다. 

이들 요소 가운데 요소 모든 노드쌍에 대해 경로가 존재하는 부그래프 S G 연결요소(connected component)라고 합니다.


예제1)


1-2-5 / 3-4-6 // 2개의 연결요소


예제2)

1-2-3-4-5-6  // 1개의 연결요소




만약 연결요소가 잘 이해되지 않는 다면 정점과 간선을 직접 그려보는 것이 좋습니다.



package hwang;

import java.io.*;
import java.util.StringTokenizer;

public class Hwang11724 {

private static int visit[];
private static int [][]graph;
private static int N, M;

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());
M = Integer.parseInt(st.nextToken());

visit = new int[N+1];
graph = new int[N+1][N+1];

for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());

// 무방향 간선
graph[x][y] = graph[y][x] = 1;
}

// cc 갯수
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (visit[i] == 0) {
cnt++;
dfs(i);
}
}
System.out.println(cnt);
}

private static void dfs(int node) {
visit[node] = 1;

for (int i = 1; i <= N; i++) {
if (graph[node][i] == 1 && visit[i] == 0) {
dfs(i);
}
}
}
}

dfs로 탐색을 하며, 연결요소가 생성될 때마다 갯수를 증가시켜 주면 됩니다.




블로그 이미지

사용자 yhmane

댓글을 달아 주세요


문제


[링크]

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


풀이 & 코드


우선 아래와 같이 예제 입력이 들어 왔다.


()(((()())(())()))(())


여기서는 3가지 경우만 체크하면 풀수가 있다.


1) '(' 여는 괄호 -> 스택에 넣어주면 된다.


*  ')' 닫는 괄호

닫는 괄호는 두가지 경우로 나뉜다.

2) 레이저 절단  

- 스택의 사이즈를 구한다.  

3) 막대의 끝

-  막대 갯수를 더한다. (+1)

() 레이저 절단 .. 하지만 막대의 시작과 끝이 없기 때문에 조각이 생기지 않는다

( ) ( ( ( ( ) 레이저 절단이 이루어 진다. 3단으로 쌓아 올렸기 때문에 스택에 남아 있는 '(((' 3조각이 생긴다              

( ) ( ( (   ( ) ( ) 또다시 레이저 절단이 이루어 진다. 마찬가지로 스택엔 3조각이 남아 있기에  3조각이 더 생긴다 

( ) ( ( (   ( ) ( ) ) 3층의 막대기 끝나는 지점이다. 1조각이 생긴다

( ) ( (    ( ( ) ( ) ) ( ( )  다시 1개의 층을 쌓고 레이저로 절단하였다. 3조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) )  3층의 막대기 끝나는 지점이다. 1조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) ) ( ) 2층의 막대기를 레이저로 절단하였다. 2조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) ) ( ) ) ) 2층과 1층의 막대기가 끝나는 지점이다. 1조각씩  총 2조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) ) ( ) ) ) ( ( ) ) 마지막 막대기를 레이저로 잘라 2조각이 더 생긴다

이렇게 해서 예제는 총 17 조각이 생긴다.


스택으로 풀면 쉬운 문제이지만,

처음엔 이해가 잘 안될 수도 있다.

그런 경우에는 위의 방법 처럼 직접 써보면서 갯수를 구해보는 것이 좋다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String input  = br.readLine();
        int    len    = input.length();
        int    result = 0;
 
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < len; i++) {
            char value = input.charAt(i);
            if (value == '(') stack.push(value);
            else {
                stack.pop();
                // 레이저
                if (input.charAt(i-1== '(') result += stack.size();
                // 파이프 끝
                else result++;
            }
        }
 
        System.out.println(result);
    }
}
cs


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

링크


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


BOJ 10844 문제 링크입니다



풀이


먼저, 문제를 풀 때 어떠한 문제인지 알면 50프로는 알고 들어가는 것 입니다.


마찬가지로, 이 문제는 n자리의 계단수를 구하면 되는 것인데



1자리, 2자리, 3자리 까지는 직접 구할 수 있지만 4자리, 5자리, 6자리 ... 로 가게 되면 직접 구할 수 없습니다.

이렬 경우에는 규칙성을 찾아서 점화식을 찾아야 하는데요, 이러한 계산을 bottom-up 또는 top-down 방식으로 풀게 된다면

다이나믹 프로그래밍의 분류라 생각 하시면 됩니다.




서론이 길었는데 저만의 문제 풀이를 해보겠습니다.

(문제에선 0으로 시작하는 수는 없다고 하였습니다!!)



먼저 1자리의 경우

1, 2, 3, 4, 5 ,6 , 7, 8, 9  가 각 1로         1자리 수의 경우 9


2자리

10,11/ 21,23 / 32,34 / 43, 45/ 54, 56 / 65,67 / 76,78 / 87,89/ 98        2자리 수의 경우 17


3자리

101, 121, 123 / 210,212, 232, 234/ 321, 323, 343, 345/ 432, 434, 454, 456 / 543, 545, 565, 567 / 

654, 656, 676, 678 / 765, 767,  787, 789 / 876, 878, 898 / 987, 989            3자리 수의 경우 32가지가 나옵니다



 

 1로 시작

 2로 시작

 3으로 시작

 4로 시작

 5로 시작

 6으로 시작

 7로 시작

 8로 시작

9로 시작

 1자리의 수

 1

 1

 1

 1

 1

 1

 1

 1

 1

 2자리의 수

 2

 2

 2

 2

 2

 2

 2

 2

 1

 3자리의 수

 3

 4

 4

 4

 4

 4

 4

 3

 2


자 위의 숫자들을 표로 정리하여 보았습니다. 여기서 규칙성을 찾아야 합니다 ..

규칙성이 보이시나여? 

규칙성을 보려고 하면 4자리 수까지 보아야 잘 보이지만,, dp 문제를 많이 풀다 보면 '아 이건 이거겠넹 ㅋㅋ' 라는게 머리속을 스쳐 지나가실 겁니다 .,..하하


1의 경우 dp[i-1][j+1] + dp[i-2][j]                     dp[3][1] = dp[2][2] + dp[1][1]  = 2+ 1

9의 경우 dp[i-1][j-1]                                        dp[3][9] = dp[2][8] = 2

그 이외의 경우 dp[i-1][j-1] + dp[i-1][j+1]          dp[3][2] = dp[2][1] + dp[2][3] = 2 + 2 , dp[3][8] = dp[2][7] + dp[2][9] = 2 + 1


코드

import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine());
int[][] dp = new int[101][10];
Long result = 0l;

for (int i=1; i<10; i++) {
dp[1][i] = 1;

if (i==9) {
dp[2][i] = 1;
} else {
dp[2][i] = 2;
}
}

for (int i=3; i<=n; i++) {
for (int j=1; j<10; j++) {
if (j==1) {
dp[i][j] = (dp[i-1][j+1] + dp[i-2][j])%1000000000;
} else if (j==9) {
dp[i][j] = (dp[i-1][j-1])%1000000000;
} else {
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000;
}
}
}

for (int i=1; i<10; i++) {
result += dp[n][i];
}

System.out.println(result%1000000000);
}

}


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

풀이


문자열을 더해 최소 글자의 팰린드롬을 만들어야 함


* 팰린드롬 문자열인지 확인 -> 아니라면 문자열을 추가 (반복)


ex) abab


1. abab 가 팰린드롬 문자열인지 확인 -> x

2.abab + a -> 팰린드롬 o -> 5 출력


ex) abcd


1. abcd             -> x

2. abcd + a      -> x

3. abcd + ba    -> x

4. abcd + cba  -> o -> 7 출력



맨 처음에 이 방법으로 접근 했지만,,, 뭔가 비효율적


곰곰히 생각해 보니,


(abab) -> check  :  x

(bab) -> check    :  o



(abcd) -> check :  x

(bcd)   -> check : x

(cd)     -> check : x

(d)       -> check : x


이런식으로 substring하여  남은 문자열이 팰린드롬 문자열인지 체크하는 방법인지 확인하는 것이 효율적!!


문자열을 더해서 확인하는 것 보다, 남은 문자열을 체크하는 것이 빠른 방법



코드



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

public class Main {
public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();

System.out.println(solution(input));
}

static int solution(String input) {

int len = input.length();
for (int i = 0; i < len; i++) {
if (isPalindrome(input.substring(i))) {
return len+i;
}
}
return len;
}

static boolean isPalindrome(String input) {

int len = input.length();
for (int i = 0; i < len/2; i++) {
if (input.charAt(i) != input.charAt(len-i-1)) {
return false;
}
}
return true;
}
}




[문제보기]


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


블로그 이미지

사용자 yhmane

댓글을 달아 주세요