안녕하세요


BlockDMask 입니다.


백준 알고리즘 사이트에서


단계별로 풀어보기를 하나하나 하고있습니다. ㅎㅎ




0. 제목


백준 9012 괄호

BOJ 9012 괄호





1. 문제설명


괄호 문자열 (Parenthesis String, PS)는 '(', ')' 만으로 구성되어 있는 문자열을 말합니다.

흔히 우리가 말하는 소괄호.!


그 중 괄호의 모양이 바르게 구성된 올바른 괄호 문자열을 Valid PS, VPS라고 부릅니다.


"()" 는 VPS 입니다.

"()()(())" 는 VPS 입니다.

"())" 는 VPS 가 아닙니다.


처음 Test할 문자열의 갯수 N이 들어오고 

그다음 문자열이 N개 만큼 들어옵니다.


입력된 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES"를 아니면 "NO"를 한줄에 하나씩 출력하시오.






2. 풀이과정


C++ STL 에서 지원해주는 stack 을 사용했습니다.


stack 을 사용하여 받은 문자열에서


[여는 괄호 일때] 

push



[닫는 괄호 일때]


1) 스택 내부에 여는 괄호가 있다. -> pop

2) 없다 -> false



[문자열을 다 확인했는데]

스택 내부에 여는 괄호가 있다 -> false


로 알고리즘을 구현했습니다.





3. 코드


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
//백준 9012번 괄호
 
#include<iostream>
#include<stack>
#include<string>
 
using namespace std;
 
bool Check(string str){
    int len = (int)str.length(); //문자열 길이
    stack<char> st;              //char 타입을 받는 stack 선언
 
    for(int i=0; i<len ; i++) { //문자열 길이만큼 반복문
        char c = str[i];        //문자 하나씩 받음
 
        if(c == '('){
            st.push(str[i]);    //여는 괄호면 push
        }else{
            if(!st.empty()){    //닫는 괄호면 stack 이 비어있는지 확인후
                st.pop();       //스택이 비어있지 않으면 pop
            }else{
                return false;   //비어있으면 false.
            }
        }
    }
 
    return st.empty();          //반복문이 끝나고 스택에 괄호가 남아있으면 false
}
 
int main(void){
 
    int n;
    cin >> n;
 
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
 
        if(Check(str)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
 
    return 0;
}
cs





4. 인증









<문제출처>

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



감사합니다.




하트 한번 꾹 부탁드립니다.!


저작자 표시 비영리 변경 금지
신고

'<문제풀이&연습> > [C++] BAEKJOON' 카테고리의 다른 글

[백준 9012] 괄호 (stack)  (0) 2017.09.20
[백준 1016] 제곱ㄴㄴ수  (0) 2017.09.19
[백준 11005] 진법 변환 2  (0) 2017.09.19
[백준 2908] 상수  (2) 2017.09.17
[백준 2675] 문자열 반복  (0) 2017.09.17
[백준 1912] 연속합 (수열)  (0) 2017.09.12

안녕하세요 


BlockDMask 입니다.


오늘자 문제


제곱 ㄴㄴㄴㄴㄴㄴㄴㄴ 수 


풀어보겠습니다.


이 문제 생각하는데 너무 오래걸렸어..






0. 제목


백준 1016 제곱ㄴㄴ수

BOJ 1016 제곱ㄴㄴ수





1. 문제설명


어떤 수가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ 수라고 합니다.


제곱수는 정수의 제곱.


min과 max의 범위가 주어지면 min, max를 포함한 사이에 제곱 ㄴㄴ 수가 몇 개 있는지 출력하는 문제.


min의 조건은.

1 <= min <= 1,000,000,000,000 사이의 자연수입니다.


max의 조건은.

max >= min 이고,

max <= min + 1,000,000 입니다.







2. 풀이과정



[대략적으로]


첫번째, 범위 내의 제곱근의 최대값(max의 제곱근)을 구합니다.

그것보다 작은 제곱근 들을 저장해놓습니다.


두번째, 저장한 제곱근 들의 배수중 최소값(min)보다 크거나 같은 배수를 구합니다.

그 배수들의 갯수를 count 합니다.

이때 중복이 발생하지 않도록 bool 배열을 통해 예외 처리 해줍니다.




[자세히]



우선. max와 min 사이 숫자의 갯수는 최대 1,000,000개 입니다.

bool 타입으로 result[1000001] 의 배열을 선언합니다.


그다음 제곱 들을 저장할 수의 배열을 선언합니다.

long long 타입으로 num[1000002]


<cmath> 헤더의 sqrt 함수를 통해서 min과 max 사이의 가장큰 제곱근(sq_max)을 구해줍니다.


구한 제곱근 보다 작고 2보다 큰 숫자들의 

제곱을 num 배열에 넣고 그것의 개수를 셉니다(cntNum)



제곱들의 갯수만큼 for문을 돌립니다.


for문 내부에서


min과 max사이에 제곱(num[i])으로 나누어 떨어지는 가장 작은 수를 div_min에 넣고


div_min + num[i] 의 갯수를 구해줍니다.


중복 체크는 result 배열을 이용합니다.

중복 되지 않은 true의 개수를 count 변수로 구합니다.




마지막 출력은 max-min + 1 갯수에서 result 배열에서의 true의 개수를 빼줍니다.






3. 코드


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
#include<iostream>
#include<cmath>
 
using namespace std;
 
bool result[1000001= {false};  //max - min 사이의 최대 갯수
long long num[1000001= {0};    //제곱들 저장
 
int main(void){
    long long min;
    long long max;
 
    cin >> min >> max;
 
    long long sq_max = (long long)sqrt(max);    //범위 내 제곱값이 될 수 있는 가장 큰수
    long long cntNum =0;                        //제곱들의 개수
    for(long long i=2; i<=sq_max; i++) {        //제곱들 저장
        num[i] = i*i;
        cntNum++;
    }
 
    int count =0// max와  min 사이에 제곱의 수로 나누어 떨어지는 수.
 
    for(int i=2; i<cntNum+2; i++){
 
        long long div_min = min;                 //div_min을 범위의 최소값 min으로 둔 후 
        if(div_min % num[i] != 0){               //div_min이 제곱수로 나누어 지지 않으면 
            div_min = (min/num[i] + 1* num[i]; //최소값을 제곱근으로 나눈 몫에 +1 후 다시 곱해서 범위 안의 값으로 바꾼다.
        }
 
        
        for(long long tmp = div_min; tmp <=max; tmp += num[i]){ //num[i]로 나누어지는 div_min을 count 한다.
            if(!result[tmp-min]){
                result[tmp-min] = true;
                count++;
            }
        }
 
    }
    cout << max-min-count+1 ;
 
    return 0;
}
cs







4. 인증










<문제출처>

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



감사합니다


도움이 되셨다면 하트 한번 부탁드립니다.

저작자 표시 비영리 변경 금지
신고

'<문제풀이&연습> > [C++] BAEKJOON' 카테고리의 다른 글

[백준 9012] 괄호 (stack)  (0) 2017.09.20
[백준 1016] 제곱ㄴㄴ수  (0) 2017.09.19
[백준 11005] 진법 변환 2  (0) 2017.09.19
[백준 2908] 상수  (2) 2017.09.17
[백준 2675] 문자열 반복  (0) 2017.09.17
[백준 1912] 연속합 (수열)  (0) 2017.09.12

안녕하세요


BlockDMask 입니다.


오늘은 11005번 진법 변환2 을 풀어보았습니다.


블로그 글을 늦게 올려서... 어제(9/18)일자 문제입니다.




0. 제목


백준 11005 진법 변환 2

BOJ 11005 진법 변환 2






1. 문제설명


10진수 수 n 이 주어지고


( n <= 1,000,000,000)


이 수를 b 진법으로 바꾸어 출력하는 프로그램을 작성하면됩니다.


( 2 <= b <= 26 )


10진법을 넘어가는 진법은 숫자로 표시할 수 없는 숫자가 존재 하므로, 이런 경우에는 알파벳 대문자를 사용합니다.


A : 10

B : 11

C : 12

D : 13

E : 14

F : 15

G : 16

.

.

.

X : 33

Y : 34
Z : 35


입니다.



ex1) 10진수 1000을 18진수로 표현하면 - 31A

ex2) 10진수 103을 2진수로 표현하면 - 1100111





2. 풀이과정



vector container를 이용하여 풀었습니다.


vector container의 자세한 설명은 [여기] 있습니다.



1) while 반복문을 통해서 10진수 N 을 진수 B로 나눈 나머지를 vector에 push_back()을 통해 넣어줍니다.

N 이 0 이 될때 까지, N을 B로 나누면서 나머지를 넣어줍니다.



2) vector container에 넣은 숫자를 뒤에서 부터 읽어줍니다.

vector<int>::reverse_iterator 를 이용하여 rbegin() 부터 rend() 까지 iterator를 돌리며 출력합니다.



3) 출력을 할때는 10보다 작은 숫자는 그대로 숫자로

10이상의 수는 A~Z 까지 출력해야 하므로 아스키 코드상에서의 문자로 바꾸어 줍니다.

10이상이므로 10을 빼준 후 'A' 만큼 더해줍니다.








3. 코드


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
#include<iostream>
#include<vector>
using namespace std;
 
int main(void){
    int n;  //변환할 10진수 숫자
    cin >> n;
 
    int b;  //반환할 베이스 진수
    cin >> b;
 
    vector<int> v;
 
    while(1){
        v.push_back(n%b);   //해당 진수로 나눈 나머지를 vector에 넣음
        n /= b;
        if(n==0break;
    }   
 
    vector<int>::reverse_iterator iter;
    for(iter = v.rbegin(); iter != v.rend(); iter++){
        if(*iter>=10){
            char c = *iter-10+'A';  //10 이상의 알파벳은 char 타입으로 출력
            cout << c;
        }else{
            cout << *iter;          //10 미만의 수는 int 타입으로 출력
        }
    }
 
    return 0;
}
cs







4. 인증










<문제 출처>

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




감사합니다.



도움이 되셨다면 하트 버튼 부탁드립니다.

저작자 표시 비영리 변경 금지
신고

'<문제풀이&연습> > [C++] BAEKJOON' 카테고리의 다른 글

[백준 9012] 괄호 (stack)  (0) 2017.09.20
[백준 1016] 제곱ㄴㄴ수  (0) 2017.09.19
[백준 11005] 진법 변환 2  (0) 2017.09.19
[백준 2908] 상수  (2) 2017.09.17
[백준 2675] 문자열 반복  (0) 2017.09.17
[백준 1912] 연속합 (수열)  (0) 2017.09.12

+ Recent posts