BOJ : https://www.acmicpc.net/problem/2089

GitHub : https://github.com/junho0956/Algorithm/blob/master/2089/2089/%EC%86%8C%EC%8A%A4.cpp

 

-2진수에 대한 변환법은 2진수 변환법과 똑같다

다른 부분은 나눗셈을 할 때 몫과 나머지를 잘 건드려줘야되는 것

13을 2로 나누면 몫은 6, 나머지는 1이다.

하지만 -13 을 2로 나누면 몫을 -6, 나머지는 -1이 되는데

이 문제를 풀기 위해서는 -13 -> -7, 1 을 만들어야하는 과정을 이해해야한다.

 

다른분들 블로그를 읽어봤는데 개념을 제대로 파악하지 않고 외우기식 문제풀이만 하는 분들이 많았다.

그렇게하면 문제를 안푼거랑 똑같지않나 라는 생각이 든다.

 

2진수라는 것은 1과 0으로만 표현할 수 있다. -1은 표현이 안되는 수이다

이 개념을 이용해보자면 ==> -1을 1로 만들수 없을까? 가 되고

-1을 1로 만들려면 몫을 -1 만큼 더 주는 대신 나머지는 2를 더해주는 것이다.

===> -13 을 2로 나누면 몫은 -7, 나머지는 1 이 된다.

이 방법을 이용하면 나머지가 1,0으로만 떨어지면서 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
#include <cstdio>
#include <stack>
using namespace std;
#pragma warning(disable:4996)
stack<int> s;
int main() {
    int N;
    scanf("%d", &N);
    if (!N) s.push(0);
    while (N) {
        if (N > 0) {
            s.push(N % 2);
            N = N / 2 * -1;
        }
        else {
            if ((N * -1) % 2 == 0) {
                s.push(0);
                N = N * -1 / 2;
            }
            else {
                s.push(1);
                N = ((N * -1) + 1) / 2;
            }
        }
    }
    while (!s.empty()) printf("%d", s.top()), s.pop();
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1929번 소수 구하기  (0) 2020.01.13
BOJ 1978번 소수 찾기  (0) 2020.01.13
BOJ 1212번 8진수 2진수  (0) 2020.01.13
BOJ 1373번 2진수 8진수  (0) 2020.01.13
BOJ 2745번 진법 변환  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/1212

 

1212번: 8진수 2진수

첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.

www.acmicpc.net

1373번의 2진수 8진수의 문제를 반대로 생각해보면 된다.

2진수를 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
#include <cstdio>
#include <string.h>
#include <stack>
#pragma warning(disable:4996)
using namespace std;
 
char str[333337];
stack<int> s;
 
int main() {
    scanf("%s", str);
    int len = strlen(str) - 1;
 
    for (int i = len; i >= 0; i--) {
        int temp = str[i]-'0';
        int cnt = 3;
        if (!temp) s.push(0), cnt--;
        while (temp) {
            cnt--;
            s.push(temp % 2);
            temp /= 2;
        }
        if (cnt) while (cnt--) s.push(0);
    }
 
    while (1) {
        if (s.top() || s.size() == 1) break;
        s.pop();
    }
    while (!s.empty()) {
        printf("%d", s.top());
        s.pop();
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1978번 소수 찾기  (0) 2020.01.13
BOJ 2089번 -2진수  (0) 2020.01.13
BOJ 1373번 2진수 8진수  (0) 2020.01.13
BOJ 2745번 진법 변환  (0) 2020.01.13
BOJ 11005번 진법 변환2  (0) 2020.01.13

BOJ : https://www.acmicpc.net/problem/1373

 

1373번: 2진수 8진수

첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다.

www.acmicpc.net

 

2진수를 8진수로 변환하는 문제

8진수가 0~7의 범위를 표현할 수 있다는 점을 이용하면

0~7 은 2진수로 3자리 000~111 로 표현할 수 있다.

그러므로 2진수를 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
#include <iostream>
#include <string>
#include <stack>
using namespace std;
 
stack<int> s;
 
int main() {
    ios::sync_with_stdio(0);
    int cnt = 0, total = 0;
    bool check = true;
    string str;
    cin >> str;
    for (int i = str.size() - 1; i >= 0; i--) {
        if (cnt == 3) {
            check = false;
            s.push(total);
            cnt = 0;
            total = 0;
        }
        if (str[i] == '1') {
            check = true;
            int temp = 1;
            for (int k = 0; k < cnt; k++) {
                temp *= 2;
            }
            total += temp;
        }
        cnt++;
    }
    if (check) s.push(total);
    while (!s.empty()) {
        cout << s.top(), s.pop();
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2089번 -2진수  (0) 2020.01.13
BOJ 1212번 8진수 2진수  (0) 2020.01.13
BOJ 2745번 진법 변환  (0) 2020.01.13
BOJ 11005번 진법 변환2  (0) 2020.01.13
BOJ 9613번 GCD 합  (0) 2020.01.12

BOJ : https://www.acmicpc.net/problem/2745

 

2745번: 진법 변환

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

www.acmicpc.net

진법변환2 와는 반대로 임의의 값과 쓰인 진법이 주어지면 10진법으로 변환하는 문제이다.

자리수당 쓰인 진법만큼 제곱하여 현재값과 곱한 값을 더해가면 쉽게 유추해낼수있다.

 

 

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
#include <iostream>
#include <string>
using namespace std;
 
int arr[26];
 
int main() {
    string str;
    int X, cnt = 0, total = 0;
    cin >> str >> X;
 
    for (int i = 0; i < 26; i++) arr[i] = 10 + i;
 
    for (int i = str.size() - 1; i >= 0; i--) {
        int temp = 1;
        int cntt = cnt++;
        while (cntt--) temp *= X;
        if (str[i] >= 'A')
            temp *= arr[str[i] - 'A'];
        else
            temp *= str[i] - '0';
        total += temp;
    }
 
    cout << total;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1212번 8진수 2진수  (0) 2020.01.13
BOJ 1373번 2진수 8진수  (0) 2020.01.13
BOJ 11005번 진법 변환2  (0) 2020.01.13
BOJ 9613번 GCD 합  (0) 2020.01.12
BOJ 1850번 최대공약수  (0) 2020.01.12

+ Recent posts

티스토리툴바