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



내가 쓴 방법


또 다른 방법


주의사항

90번째 피보나치 수의 크기?

double 써도 안됨


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
package n2193;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        long[] o; // count of one
        long[] z; // count of zero
 
        int n = sc.nextInt();
        o = new long[n+1];
        z = new long[n+1];
 
        long result = 1;
 
        o[1] = 1;
        z[1] = 0;
        for(int i = 2; i< n+1; i++){
            z[i] = z[i-1] + o[i-1];
            o[i] = z[i-1];
        }
        result = z[n] + o[n];
 
        System.out.println(result);
    }
}
 
cs


저작자표시 비영리

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 11057  (0) 2019.01.25
[code.plus 알고리즘 기초] no. 10844  (0) 2019.01.23
[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17

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



좋지 못한 접근 방법

dp(dynamic programming)문제는 이전의 있는 값을 활용해서 풀어야한다.

무턱대고 직관적인 방식으로 풀다가는 꼬이기도 쉽고 런타임 시간과 푸는 시간도 오래 걸릴 것이다.



올바른 접근 방법



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
package n11052;
 
import java.util.Scanner;
 
public class Main {
    public static int result = 0;
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1]; // price 배열
 
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
 
        int[] d = new int[n+1]; // 최대값 저장
 
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {//dp[n]을 max값 비교하기 위해 총 n번 검사
                if (d[i] < d[i-j] + a[j]) { // max 값 비교
                    d[i] = d[i-j] + a[j];// 사는 경우의 수( 카드를 1개 살때부터 n개 살때까지
                }
            }
        }
        System.out.println(d[n]);
    }
}
 
cs


저작자표시 비영리

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 10844  (0) 2019.01.23
[code.plus 알고리즘 기초] no. 2193  (0) 2019.01.22
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16

출처: http://www.newthinktank.com/2018/03/setup-visual-studio-code-macos/

1. Xcode 설치( g++ )


2. VS Code의 extensions에서 C/C++ 설치/Reroad


3. VS Code의 extensions에서 Code Runner 설치/Reroad


4. FlatformIO IDE 설치/Reroad


5. project 생성



6. 업로드/시리얼 모니터 출력


저작자표시 비영리

'개발 tip > Arduino' 카테고리의 다른 글

[아두이노] 아두이노 M0( SAMD21G )에서 새로운 serial 만들기  (0) 2019.02.11

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



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
package n9095;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] dp;
        int T = sc.nextInt();
        while(T-- > 0){
            int n = sc.nextInt();
            dp = new int[n+1];
            dp[0] = 0;
            if( n == 1 || n == 2){
                dp[n] = n;
            }else if(n == 3){
                dp[n] = 4;
            }else if( n > 3){
                dp[1] = 1;
                dp[2] = 2;
                dp[3] = 4;
                for(int i = 4; i<=n; i++){
                    dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
                }
            }
            System.out.println(dp[n]);
        }
    }
}
 
cs


저작자표시 비영리

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 2193  (0) 2019.01.22
[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package n11727;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i =2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-2];
            dp[i] %= 10007;
        }
        System.out.println(dp[n]);
 
    }
}
 
cs


저작자표시 비영리

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 11052  (0) 2019.01.21
[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14



좋지 못한 예

문제 푸는 도중 규칙을 찾고서 빠르게 푸려고 하는 방식은 좋다. 

그러나 규칙만 찾고 그 원리에 대해서 이 규칙을 100% 적용해도 되는 걸까? 라고 다시한번 생각해보길 바란다.


제대로 된 풀이



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package n11726;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] dp;
 
        int n = sc.nextInt();
        dp = new int[n+1];
 
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] %= 10007;
        }
 
        System.out.println(dp[n]);
    }
}
 
cs




저작자표시 비영리

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 9095  (0) 2019.01.19
[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14
[code.plus 알고리즘 기초]no. 10799  (0) 2019.01.13


top-down 방식

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
32
33
34
35
36
37
38
39
40
41
42
43
package n1463;
 
import java.util.Scanner;
 
public class Main {
    public static int[] dp;//dp[n]은 n을 1로 만드는데 필요한 연산의 최소값
 
    public static int procCnt(int n){
//        System.out.println(n);
//        for(int i = 0; i< dp.length; i++){
//            System.out.print(dp[i]+",");
//        }
        if(n == 1){ // 1이 들어올 때는 연산이 필요없음
            return 0;
        }
        if(dp[n] > 0){ // memorization 어차피 같은 연산이면 연산하지 않도록 하게
            return dp[n];
        }
        dp[n] = procCnt(n-1)+1;
        if(n%2 == 0){
            int temp = procCnt(n/2)+1; // n/2로 해서 리턴 받은 값을 temp에 저장
            if(dp[n] > temp){ //  temp가 dp[n]보다 작다면 dp[n]을 temp로 바꿔준다.
                dp[n] = temp;
            }
        }
        if(n%3 == 0){
            int temp = procCnt(n/3)+1;
            if(dp[n] > temp){
                dp[n] = temp;
            }
        }
 
        return dp[n];
 
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        dp = new int[X+1];
        System.out.print(procCnt(X));
    }
}
 
cs


bottom-up방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n+1];
        d[1] = 0;
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + 1;
            if (i%2 == 0 && d[i] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }
            if (i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}
cs


저작자표시 비영리

'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14
[code.plus 알고리즘 기초]no. 10799  (0) 2019.01.13
[code.plus 알고리즘 기초]no. 9012  (0) 2019.01.13

개인적으로 프로그래밍 기초를 공부한다고 했을 때 그 순서와 읽을 책을 추천 해본다.


공부순서를 이야기하기 전에 공부방식에 대해 짤막하게 설명한다.


이 말은 나의 멘토님께 들은 이야기다.

공부를 하면서 얻을 수 있는 지식의 양이 100이라고 했을 때

프로그래밍 공부에서는


10은 책읽기 및 강의 듣기

20은 예제 코드 따라 써보기

70은 직접 큰 프로젝트든 작은 프로그램이든 100% 내 머리속에서 나온것을 만들어 보기


라고 한다.

백날 책읽고 강의만 듣는다고 해서 나아지는 건 별로 없다는 것이다. 직접 해봐야 한다.


다음으로 이야기할 기초공부를 모두 끝마치고 나면 새로운 기술을 배우는데에 준비가 되었다고 생각한다.


1. 첫 프로그래밍 언어는 C언어를 추천한다.

문법 책은 [윤성우] 님이 쓰신 [열혈강의 C] 또는 [서현우]님의 [뇌를 자극하는 C프로그래밍] 이다.

C가 어렵다고 하는 대부분의 이유중 하나가 포인터 때문인데 포인터를 공부하는 부분부터는 이 책을 추천한다.

[리처드 리스]의 [C포인터의 이해와 활용]


문법을 다 공부 했다면 이 책은 선택이다. 앞으로 많은 것을 공부하게 될텐데 맛보기로 뭐가 있는지를 전반적으로 한번 훑어보기에 좋은 책이다.

[양태환]님의 [컴퓨터 사이언스 부트캠프 with 파이썬]


2. 언어를 배웠으니 이를 써먹어 봐야한다. 코드는 알고리즘의 집합체이며, 알고리즘은 생각의 순서이다.

code.plus 강의 중에 알고리즘 기초라는 동영상 강의가 있다.

강의를 듣다가 문제풀이 부분이 나오면 잠깐 멈추고 https://www.acmicpc.net/ 으로 들어가 먼저 한번 [풀어보거나] [최대 4시간정도 풀어보고 안풀리는] 경우 

다시 강의를 이어 듣는 것을 추천한다. 


3. 자료구조는 선택이 아닌 필수다.

책은 [윤성우]님이 쓰신 [열혈강의 자료구조]이다.


4. OOP 언어를 배울 차례가 된 것 같다. 언어를 배웠으니 말을 효율적으로 하는 방법을 배워야 한다.

그리고 OOP언어의 문법만 배울 것이 아니라 디자인패턴도 같이 배우는 것을 추천한다.

문법 책은 [윤성우]님이 쓰신 [열혈강의 C++]또는 [남궁성]님의 [자바의 정석]이고

디자인 패턴 책은 [에릭 프리먼 , 엘리자베스 프리먼 , 케이시 시에라 , 버트 베이츠]의 [Head First Design Patterns: 스토리가 있는 패턴 학습법]를 추천한다.


5. 이제 언어도 배웠고 말하는 법도 배웠고 말을 잘하는 방법도 배웠다. 그나라의 문화를 제대로 알려면 이제 역사를 배울 차례다.

이론서적은 컴퓨터 구조, OS, 컴퓨터 네트워크 3가지 파트를 추천한다.


컴퓨터 구조:

[David A. Patterson, John L. Hennessy]의 [컴퓨터 구조 및 설계]


운영체제:

[아브라함 실버스카츠]의 [Operating System Concepts] 또는 


시간이 많다면 OS를 직접 만들어 보는 것도 추천한다. 컴퓨터 구조와 OS이론의 실기책이라고 할 수 있다.

[한승훈]님의 [IT EXPERT, 64비트 멀티코어 OS 원리와 구조 1권: OS 개발 60일 프로젝트] 1권 2권으로 나눠져있다.


컴퓨터 네트워크:

[진강훈]님의 [후니의 쉽게 쓴 시스코 네트워킹], [미즈구치 카츠야]의 [모두의 네트워크: 10일 만에 배우는 네트워크 기초]


6. 알고리즘은 개발자라면 시간 날때마다 틈틈이 해야할 기본소양이므로 항상 공부하도록 한다.


화이팅.


책을 고를 때는 이분의 블로그를 많이 참고를 했다.

https://www.sangkon.com/2016/02/10/good_books_for_dev/


----------------------------------------------------------------------------------------------------------------------------

독학의 단점은 혼자만의 생각에 갇혀있을 위험이 매우 크다는 것이다.

본 블로그의 목적은 나의 생각을 모두에게 공개하고 그에 대한 다른 사람들의 생각을 듣고 공부의 질을 높이는 것에 있다.

따라서 어떠한 의견이든 환영이다.

----------------------------------------------------------------------------------------------------------------------------







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
32
33
package n1158;
 
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        int n = 0;
        int m = 0;
 
        n = sc.nextInt();
        m = sc.nextInt();
 
        Queue<Integer> q = new LinkedList<Integer>();
 
        for(int i = 1; i<=n; i++){
            q.offer(i);
        }
 
        System.out.print("<");
        for(int i = 0; i < n - 1; i++){
            for(int j = 0; j < m - 1; j++){
                q.offer(q.poll());
            }
            System.out.print(Integer.toString(q.poll()) + ", ");
        }
        System.out.print(Integer.toString(q.poll()) + ">");
    }
}
 
cs


'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 10799  (0) 2019.01.13
[code.plus 알고리즘 기초]no. 9012  (0) 2019.01.13

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





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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.Scanner;
 
class Stack{
    private int[] stack;
    private int top;
    private int defaultData = -999;
 
    Stack(int lenght){
        this.stack = new int[lenght];
        for(int i = 0; i<this.stack.length; i++){
            this.stack[i] = defaultData;
        }
        this.top = 0;
    }
 
    void push(int data){
        this.stack[this.top] = data;
        this.top++;
//        System.out.println("push: "+top);
    }
 
    int pop(){
        this.top--;
        int data = this.stack[top];
        this.stack[top] = defaultData;
//        System.out.println("pop: "+top);
 
        return data;
    }
 
    int getSize(){
        return this.top;
    }
 
}
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        String str = sc.nextLine();
        char[] c = str.toCharArray();
 
        Stack st = new Stack(c.length);
        int result = 0;
 
        for(int i = 0; i<c.length; i++){
            if(c[i] == '('){
                st.push(i); // 여는 괄호의 index값을 stack에 넣는다.
            }else{ //닫는 괄호에서
                if(i - st.pop() == 1) { // 현재 i의 값(닫는 괄호의 index)와 마지막으로 넣은 여는 괄호의 index의 차이가 1이라면
//                    System.out.println("i-x = 1");
                    result += st.getSize(); // 현재 stack의 사이즈를 result에 더해준다.
                }
                else{ // 이 부분 조심. 위의 if중에 함수 실행하는 명령어가 포함되어 있으면 else문에서도 함수가 실행됨. (현재: st.pop()이 실행됬음.)
//                    System.out.println("i-x != 1");
//                    st.pop();
                    result+=1;
                }
            }
        }
        System.out.println(result);
    }
}
 
cs


'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[code.plus 알고리즘 기초] no. 11727  (0) 2019.01.17
[code.plus 알고리즘 기초] no. 11726  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1463  (0) 2019.01.16
[code.plus 알고리즘 기초]no. 1158  (0) 2019.01.14
[code.plus 알고리즘 기초]no. 9012  (0) 2019.01.13

+ Recent posts

티스토리툴바