최솟값과 최댓값

PS(Problem Solving)/Segment Tree
posted by 귀염둥이채원 2019. 3. 14. 19:50

# 문제링크

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


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64


# 풀이

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
66
public class BOJ2357 {
    static int N, M;
    static int a, b;
    static int arr[], segMinArr[], segMaxArr[];
 
    static void init(int N) {
        segMinArr = new int[N*4];
        segMaxArr = new int[N*4];
        Arrays.fill(segMinArr, Integer.MAX_VALUE);
        Arrays.fill(segMaxArr, Integer.MIN_VALUE);
    }
    
    static int createMinTree(int arr[], int left, int right, int node) {
        if (left == right) return segMinArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMinArr[node] = Math.min(createMinTree(arr, left, mid, node*2), createMinTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMinQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MAX_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMinArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.min(getMinQuery(left, right, node*2, nodeLeft, mid), getMinQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    static int createMaxTree(int arr[], int left, int right, int node) {
        if (left == right) return segMaxArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMaxArr[node] = Math.max(createMaxTree(arr, left, mid, node*2), createMaxTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMaxQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MIN_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMaxArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.max(getMaxQuery(left, right, node*2, nodeLeft, mid), getMaxQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        init(N);
        createMinTree(arr, 0, N-1, 1);
        createMaxTree(arr, 0, N-1, 1);
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;
            
            sb.append(getMinQuery(a, b, 1, 0, N-1) + " " +getMaxQuery(a, b, 1, 0, N-1) + "\n");
        }
        System.out.println(sb.toString());
    }
}
cs


'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

[BOJ]10868. 최솟값  (0) 2019.03.13
[BOJ]2042. 구간 합 구하기  (0) 2019.03.13

[BOJ]10868. 최솟값

PS(Problem Solving)/Segment Tree
posted by 귀염둥이채원 2019. 3. 13. 21:28

# 문제링크

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


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64


# 풀이

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
66
67
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ10868 {
    static int arr[];
    static int N, M;
    static int a, b;
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder("");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree segObj = new SegmentTree(arr, N);
        //segObj.print();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            sb.append(segObj.query(a-1, b-1, 1, 0, N-1) + "\n");
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long segmentArr[];
    
    SegmentTree(int arr[], int N){
        segmentArr = new long[N*4];
        Arrays.fill(segmentArr, Integer.MAX_VALUE);
        init(arr, 0, N-1, 1);
    }
    
    long init(int arr[], int left, int right, int node) {
        if (left == right) return segmentArr[node] = arr[left];
        int mid = (left+right)/2;
        return segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));
    }
 
    long query(int sIdx, int eIdx, int node, int nodeLeft, int nodeRight) {
        if (sIdx > nodeRight || eIdx < nodeLeft) return Integer.MAX_VALUE;
        if (sIdx <= nodeLeft && eIdx >= nodeRight) return segmentArr[node];
        int mid = (nodeLeft + nodeRight)/2;
        return Math.min(query(sIdx, eIdx, node*2, nodeLeft, mid), query(sIdx, eIdx, node*2+1, mid+1, nodeRight)); 
    }
    
    void print() {
        for (int i=0; i<segmentArr.length; i++) {
            System.out.printf("%d, ", segmentArr[i]);
        }
        System.out.println();
    }
}
cs


# 회고

- segment tree 생성시 segmentArr에 초기값을 MAX로 설정해야한다.

  - Arrays.fill(segmentArr, Integer.MAX_VALUE);


- 자식이 있는 "부모노드"는 자식 노드들의 최솟값을 가지고 있어야 한다.

  - segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));

'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

최솟값과 최댓값  (0) 2019.03.14
[BOJ]2042. 구간 합 구하기  (0) 2019.03.13

[BOJ]2042. 구간 합 구하기

PS(Problem Solving)/Segment Tree
posted by 귀염둥이채원 2019. 3. 13. 16:55

# 문제링크

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


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64


# 풀이

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package segment;
 
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, K;
    static int arr[];
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        int a=0, b=0, c=0;
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree seg = new SegmentTree(arr, N);
        //seg.print();
        
        for (int i=0; i<M+K; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            
            // segment tree 업데이트
            if (a == 1) {
                seg.update(b-1, c, 1, 0, N-1);
            }
            // segment tree에서 구간의 합 
            else if (a == 2) {
                sb.append(seg.query(b-1, c-1, 1, 0, N-1)+"\n");
            }
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long SegmentTreeArr[];    // segment tree node 데이터
    
    SegmentTree(int arr[], int N) {
        SegmentTreeArr = new long[N*4];
        init(arr, 0, N-1, 1);
    }
    
    // Leaf Node가 N개인 Segment Tree 생성
    // node 의 왼쪽 자식은 node*2, 오른쪽 자식은 node*2+1
    long init(int arr[], int left, int right, int node) {
        // node가 리프 노드인 경우
        if (left == right) return SegmentTreeArr[node] = arr[left];
        int mid = (left+right)/2;
        return SegmentTreeArr[node] = init(arr, left, mid, node*2) + init(arr, mid+1, right, node*2+1);
    }
    
    // Segment Tree를 갱신하고 노드 구간의 합을 구한다.
    long update(int index, int value, int node, int nodeLeft, int nodeRight) {
        // index가 Node 구간에 포함되지 않는 경우
        if (index < nodeLeft || index > nodeRight) return SegmentTreeArr[node];
        
        // node가 리프 노드인 경우
        if (nodeLeft == nodeRight)  return SegmentTreeArr[node] = value; 
        
        int mid = (nodeLeft + nodeRight)/2;
        return SegmentTreeArr[node] = update(index, value, node*2, nodeLeft, mid) + update(index, value, node*2+1, mid+1, nodeRight); 
    }
    
    // Segment Tree의 구간 합을 구한다.
    long query(int left, int right, int node, int nodeLeft, int nodeRight) {
        // 두 구간이 겹치지 않는 경우
        if (left > nodeRight || right < nodeLeft) return 0;
        
        // [left, right]가 [nodeLeft, nodeRight]를 포함하는 경우
        if (left <= nodeLeft && right >= nodeRight) return SegmentTreeArr[node];
        
        int mid = (nodeLeft + nodeRight)/2;
        return query(left, right, node*2, nodeLeft, mid) + query(left, right, node*2+1, mid+1, nodeRight); 
    }
    
    void print() {
        for (int i=0; i<SegmentTreeArr.length; i++) {
            System.out.printf("%d, ", SegmentTreeArr[i]);
        }
        System.out.println();
    }
}
cs


'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

최솟값과 최댓값  (0) 2019.03.14
[BOJ]10868. 최솟값  (0) 2019.03.13

[BOJ]10828. 스택

PS(Problem Solving)/Stack
posted by 귀염둥이채원 2019. 3. 3. 22:10

# 문제링크

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


# 문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.


명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.

pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

size: 스택에 들어있는 정수의 개수를 출력한다.

empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.


# 풀이1

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
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    static int N;
    static Stack <Integer> stk;
    
    static void func(String inputStr) {
        String strCommand[];
        if (inputStr.contains("push")) {
            strCommand = inputStr.split(" ");
            int number = Integer.parseInt(strCommand[1]);
            stk.push(number);
        }
        else if (inputStr.equals("pop")) {
            if (stk.size() > 0) {
                System.out.println(stk.pop());
            }
            else {
                System.out.println(-1);
            }
        }
        else if (inputStr.equals("size")) {
            System.out.println(stk.size());
        }
        else if (inputStr.equals("empty")) {
            if (stk.isEmpty()) {
                System.out.println(1);
            }
            else {
                System.out.println(0);
            }
        }
        else if (inputStr.equals("top")) {
            if (stk.isEmpty()) {
                System.out.println(-1);
            }
            else {
                System.out.println(stk.peek());
            }
        }
    }
    
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
 
        stk = new Stack <Integer>();
        stk.clear();
        
        N = sc.nextInt();
 
        for (int i=0; i<=N; i++) {
            func(sc.nextLine());
        }
        sc.close();
    }
}
cs


# 풀이2

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static Stack <Integer> stk;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        stk = new Stack <Integer>();
        stk.clear();
        
        N = Integer.parseInt(br.readLine());
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            switch (st.nextToken()) {
                case "push":
                    stk.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    if (stk.size() > 0) {
                        sb.append(stk.pop() + "\n");
                    }
                    else {
                        sb.append("-1" + "\n");
                    }
                    break;
                case "size":
                    sb.append(stk.size() + "\n");
                    break;
                case "empty":
                    if (stk.isEmpty()) {
                        sb.append(1 + "\n");
                    }
                    else {
                        sb.append(0 + "\n");
                    }
                    break;
                case "top":
                    if (stk.isEmpty()) {
                        sb.append(-1 + "\n");
                    }
                    else {
                        sb.append(stk.peek() + "\n");
                    }
                    break;
            }
        }
        
        System.out.println(sb);
    }
}
cs


# 회고

풀이 2에서 BufferedReader, StringBuilder를 사용해서 성능을 개선하였다.

(풀이1: 140ms, 풀이2: 436ms)


split 대신 StringTokenizer를 사용하여 문자열을 파싱함


# 풀이 참고

https://www.acmicpc.net/source/10582053

https://www.acmicpc.net/source/7385991

https://www.acmicpc.net/source/8726490

자바 알고리즘 문제풀때 참고하기 (정리중,,,)

PS(Problem Solving)/공통
posted by 귀염둥이채원 2019. 3. 3. 21:58

# 자바(java) 프로그램 코드의 시간 측정 방법

https://palyoung.tistory.com/41


long beforeTime = System.currentTimeMillis();

****** 소스 코드 ******

System.out.println("count= " + count);

long afterTime = System.currentTimeMillis();

long secDiffTime = (afterTime - beforeTime);

System.out.println("시간차이(msec) : " + secDiffTime);


# 시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?

https://palyoung.tistory.com/37


# String to int, int to String 변환

https://palyoung.tistory.com/52


# String값을 int형의 값으로 바꾸는 방법

int numInt = Integer.parseInt(numStr);


# int형의 값을 String으로 바꾸는 방법

String numStr2 = String.valueOf(numInt);


# ArrayList 사용법

https://palyoung.tistory.com/50


# StringTokenizer 사용법 정리

https://palyoung.tistory.com/54


# String vs StringBuffer vs StringBuiler

https://palyoung.tistory.com/53

StringBuilder가 성능이 좋다.


# Scanner vs BufferedReader 차이

https://palyoung.tistory.com/55

BufferedReader가 성능이 좋다.



'PS(Problem Solving) > 공통' 카테고리의 다른 글

백준 사이트 정리  (0) 2019.03.01
알고리즘 소스 템플릿  (0) 2019.02.27
알고리즘 문제 풀이 템플릿  (0) 2019.02.27
알고리즘 학습 관련 자료 모음  (0) 2019.02.27

[백준/BOJ] 1152번 단어의 개수 풀이

PS(Problem Solving)/문자열
posted by 귀염둥이채원 2019. 3. 3. 17:19

문제링크: https://www.acmicpc.net/problem/1152


# 문제

영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.


# 입력

첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다.


# 출력

첫째 줄에 단어의 개수를 출력한다.


# 예제 입력 1 

The Curious Case of Benjamin Button


# 예제 출력 1 

6


###########################################################

풀이1

1. 문자열을 입력받아서 split(" ")한다.

2. split 결과의 배열을 체크해서 공백이 아닌 경우만 카운팅한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        
        int strCount=0;
        String inputStr = sc.nextLine();
        String strArr[] = inputStr.split(" ");;
    
        for (int i=0; i<strArr.length; i++) {
            if (strArr[i].equals("") != true) {
                strCount++;
            }
        }
        System.out.println(strCount);
        
        sc.close();
    }
}
cs


풀이2

1. 문자열을 입력받아서 문자들을 모두 체크한다.

2. 문자의 아스키코드 범위값을 체크해서 연속된 문자열이면 카운팅하지 않는다.

   (즉 초기 한번만 카운팅)

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
public class Main {
    static int getStringCount(String inputStr) {
        int count=0;
        int wordFlag=0;
        
        for (int i=0; i<inputStr.length(); i++) {
            char temp = inputStr.charAt(i);
            if (wordFlag == 0) {
                if ((temp >= 'A' && temp <='Z') || (temp >= 'a' && temp <='z')) {
                    count++;
                    wordFlag = 1;
                }
            }
            if (temp == ' ') {
                wordFlag = 0;
            }
        }
        return count;
    }
    
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        
        String inputStr = sc.nextLine();
        System.out.println(getStringCount(inputStr));
        sc.close();
    }
}
cs


# 회고

split, trim, isEmpty 사용법을 학습하자


# 다른 정답 참고

https://rightbellboy.tistory.com/40

https://zoonvivor.tistory.com/126

백준 사이트 정리

PS(Problem Solving)/공통
posted by 귀염둥이채원 2019. 3. 1. 20:44

# 채점결과

기다리는 중: 채점이 밀려서 아직 채점이 되지 않은 경우.

재채점을 기다리는 중: 재채점을 기다리는 중인 경우.

컴파일 하는 중: 컴파일 하는 중인 경우.

채점중: 채점을 하는 중인 경우.

맞았습니다!!: 제출한 프로그램이 모든 테스트 케이스를 통과했을 경우. 즉, 정답이다.

출력 형식이 잘못되었습니다: 출력 결과는 정답과 유사하나, 공백, 빈 줄과 같은 문제로 인해서 출력 결과가 일치하지 않은 경우.

틀렸습니다: 출력 결과가 정답과 다른 경우.

시간 초과: 프로그램이 제한된 시간 이내에 끝나지 않은 경우. 이런 경우에는 채점을 중간에 중단하므로 정답이 맞는지 아닌지는 알 수 없다.

메모리 초과: 프로그램이 허용된 메모리보다 많은 메모리를 사용했을 경우.

출력 초과: 너무 많은 출력이 발생하는 경우. 주로 프로그램이 무한 루프에 빠졌을 때 발생한다. 출력 제한은 1MB.

런타임 에러: 실행 도중에 'segmentation fault', 'floating point exception', 'used forbidden functions', 'tried to access forbidden memories' 등의 에러가 발생하여 프로그램이 종료된 경우.

컴파일 에러: 컴파일 하지 못한 경우. Warning Message는 에러 메시지가 아니다. 채점 결과를 클릭하면 컴파일 에러 메시지를 볼 수 있다..


맞았습니다!!(내지는 부분 점수)를 제외한 어떤 최종 채점 결과도 정답 처리가 되지 않는다. 


# 문제선택

정답자 수, 제출 수, 정답률: 

- 정답자 수가 많고, 정답률이 높을수록 쉬운 문제이다.


- 정답률이 낮지만 문제가 쉬운 경우

  - 한두 번 문제의 함정에 걸리거나 예외 처리를 잘못하는 등 구현 문제


- 정답률이 높지만 어려운 문제

  - 문제 자체가 어려워서 손을 댄 사람이 적은 경우

  - 실제로 이런 경우엔 제출자 수부터 현저히 떨어진다.


문제집

- 유저들이 자유롭게 생성할 수 있는 문제집 중에서 초심자 전용 문제집이 많이 존재한다. 

  좋은 문제들을 많이 모아놓은 문제집이 많으므로 애용하면 좋다.

  문제 수가 아주 적지도 않으면서 문제집 클리어 수가 많으면 대체로 쉽다고 판단할 수 있다.

  클리어 수가 적더라도 대부분의 문제가 쉬운 경우가 있으므로 꼭 들어가보자.


내가 못 푼 문제들: 

- 전체 문제들 중에서 내가 아직 풀지 않은 문제를 정답자 수 등의 기준으로 정렬하여 보여준다.

- 상단에 위치할수록 대체로 쉬운 문제이다.


# 단계별로 문제 풀어보기

https://www.acmicpc.net/step


# [문제집] 단계별로 풀어보기 jh05013 Edition pt.1

https://www.acmicpc.net/workbook/view/1946


# [문제집] 백준에서 가장 많이 풀린 문제 TOP 100 (입문자 추천)

https://www.acmicpc.net/workbook/view/2435


# 참고사이트

https://namu.wiki/w/Baekjoon%20OJ

'PS(Problem Solving) > 공통' 카테고리의 다른 글

자바 알고리즘 문제풀때 참고하기 (정리중,,,)  (0) 2019.03.03
알고리즘 소스 템플릿  (0) 2019.02.27
알고리즘 문제 풀이 템플릿  (0) 2019.02.27
알고리즘 학습 관련 자료 모음  (0) 2019.02.27

알고리즘 소스 템플릿

PS(Problem Solving)/공통
posted by 귀염둥이채원 2019. 2. 27. 19:25

# sample.txt

2

5

5


# Template Code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.io.FileInputStream;
import java.util.Scanner;
 
public class TEST {
    static int N;
    static int Answer;
 
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("C:\\java\\SW\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            Answer = N = sc.nextInt();
            System.out.println("#" + test_case + " " + Answer);
        }
    }
}
cs


# Result

#1 5

#2 5

'PS(Problem Solving) > 공통' 카테고리의 다른 글

자바 알고리즘 문제풀때 참고하기 (정리중,,,)  (0) 2019.03.03
백준 사이트 정리  (0) 2019.03.01
알고리즘 문제 풀이 템플릿  (0) 2019.02.27
알고리즘 학습 관련 자료 모음  (0) 2019.02.27

알고리즘 문제 풀이 템플릿

PS(Problem Solving)/공통
posted by 귀염둥이채원 2019. 2. 27. 18:34

# 문제 링크


# 문제 요약


# 문제 풀이


# 소스 코드


# 회고

'PS(Problem Solving) > 공통' 카테고리의 다른 글

자바 알고리즘 문제풀때 참고하기 (정리중,,,)  (0) 2019.03.03
백준 사이트 정리  (0) 2019.03.01
알고리즘 소스 템플릿  (0) 2019.02.27
알고리즘 학습 관련 자료 모음  (0) 2019.02.27

알고리즘 학습 관련 자료 모음

PS(Problem Solving)/공통
posted by 귀염둥이채원 2019. 2. 27. 18:33

# SWEA Reference Code

https://www.swexpertacademy.com/main/code/referenceCode/referenceCodeList.do


# Data Structure

- Stack

- Queue

- Priority Queue

- Hash

- Tree

- Graph

- Linked List


# Algorithm

- Recursion

- Insertion Sort

- Quick Sort

- Quick Sort

- Counting Sort

- Binary Search -- https://palyoung.tistory.com/35

- DFS Searching

- BFS Searching

- Parametric Search

- Dynamic Programming

- Permutation & Combination

- Dijkstra



# 백준 알고리즘 기초

https://code.plus/course/4


1. 알고리즘과 입/출력

- Hello World

- A+B

- A+B - 2

- A+B - 3

- A+B - 4

- A+B - 5

- A+B - 6

- A+B - 7

- A+B - 8

- 그대로 출력하기

- 그대로 출력하기 2

- 숫자의 합

- 열 개씩 끊어 출력하기


2. 자료구조 1

- 스택

- 괄호

- 쇠막대기

- 에디터

- 큐

- 조세퍼스 문제

- 덱

- 알파벳 개수

- 알파벳 찾기

- 문자열 분석

- 단어 길이 재기

- ROT13

- 네 수

- 접미사 배열


3. 다이나믹 프로그래밍 1

- 1로 만들기

- 2×n 타일링

- 2×n 타일링 2

- 1, 2, 3 더하기

- 붕어빵 판매하기

- 쉬운 계단 수

- 오르막 수

- 이친수

- 스티커

- 포도주 시식

- 가장 긴 증가하는 부분 수열

- 가장 큰 증가 부분 수열

- 가장 긴 감소하는 부분 수열

- 가장 긴 바이토닉 부분 수열

- 연속합

- 계단 오르기

- 제곱수의 합

- 타일 채우기

- 파도반 수열

- 합분해

- 암호코드


4. 수학 1

- 나머지

- 최대공약수와 최소공배수

- 최소공배수

- GCD 합

- 진법 변환 2

- 진법 변환

- 2진수 8진수

- 8진수 2진수

- 2진수

- Base Conversion

- 소수 찾기

- 소수 구하기

- 골드바흐의 추측

- 소인수분해

- 팩토리얼

- 팩토리얼 0의 개수

- 조합 0의 개수


5. 정렬

- 수 정렬하기 2

- 좌표 정렬하기

- 좌표 정렬하기 2

- 나이순 정렬

- 국영수

- 수 정렬하기 3

- 카드

- K번째 수

- 버블 소트


6. 그래프 1

- DFS와 BFS

- 연결 요소의 개수

- 이분 그래프

- 순열 사이클

- 반복수열

- 텀 프로젝트

- 단지번호붙이기

- 섬의 개수

- 미로 탐색

- 토마토

- 다리 만들기


7. 트리 1

- 트리 순회

- 트리의 부모 찾기

- 트리의 지름

- 트리의 지름


# 삼성 SW 역량 테스트 기출 문제

https://www.acmicpc.net/workbook/view/1152



# geeksforgeeks

https://www.geeksforgeeks.org/


# 알고리즘 문제 해결 전략 세트 도서


# 동빈나 알고리즘

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz


# T 아카데미

https://www.youtube.com/watch?v=vQv7PTKM2LI&list=PL9mhQYIlKEhdvKFh-wVpDuihNQv6C1gSy&index=1


# 권호흠 교수: 자바 알고리즘

https://www.youtube.com/playlist?list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l

http://alg.pknu.ac.kr/


# 생활코딩: 자료구조

https://www.youtube.com/playlist?list=PLuHgQVnccGMDsWOOn_P0EmAWB8DArS3Fk


# 알고리즘 투게더 with 거니

https://www.youtube.com/channel/UCO7g158NWgLyn98z8v3zduA/videos


# 인프런: 영리한 프로그래밍을 위한 알고리즘 강좌

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/


# 인프런: Java로 배우는 자료구조

https://www.inflearn.com/course/java-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/

'PS(Problem Solving) > 공통' 카테고리의 다른 글

자바 알고리즘 문제풀때 참고하기 (정리중,,,)  (0) 2019.03.03
백준 사이트 정리  (0) 2019.03.01
알고리즘 소스 템플릿  (0) 2019.02.27
알고리즘 문제 풀이 템플릿  (0) 2019.02.27

티스토리툴바