취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10815번 문제인 숫자 카드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10815

이 문제는 binary search 구현을 연습할 수 있던 문제이다.

가지고 있는 카드를 크기순으로 정렬해두고, 들어오는 숫자마다 binary search를 이용하면 쉽게 풀 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int card[500000]; //카드배열
int target; //배열에 들어있는지 확인할 대상
int mid; //binary search에서 이용
bool chk; // 카드배열에서 target을 찾았는지 확인
int a, b; //binary search에서 이용

int main()
{
    std::ios::sync_with_stdio(0); 
    cin.tie(0); // input이 많다
    int n; //카드의 배열을 받아 정렬
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        card[i] = x;
    }
    sort(card, card + n);
    int y; // 하나씩 숫자를 받아서 binary search로 배열에 있는지 확인
    cin >> y;
    for (int i = 0;i < y;i++) {
        a = 0, b = n - 1;
        cin >> target;
        chk = true;
        while (a <= b) {
            mid = (a + b) / 2;
            if (card[mid] == target) {
                cout << 1 << ' ';
                chk = false;
                break;
            }
            else if (card[mid] < target) {
                a = mid + 1;
            }
            else {
                b = mid - 1;
            }
        }
        if (chk) {
            cout << 0 << ' ';
        }
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1026번 문제인 보물이다.
문제는 아래 링크를 확인하자.
www.acmicpc.net/problem/1026

네 수의 a1<a2, b1<b2가 있을 때, a1*b2+a2*b1<a1*b1+a2*b2이 항상 성립하므로, 이 문제는 주어진 A와 B를 정렬한 뒤 역순으로 서로 곱한 합을 구하는 것으로 풀 수 있다.

문제에서 B의 순서를 건드리지 말라고 했으나, B의 순서를 건드려도 안 건드려도 출력해야하는 값은 같으므로 B의 순서를 바꿔도 상관이 없다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int main()
{
    int arrA[50], arrB[50]; //A와 B를 받아 정렬하기
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        arrA[i] = x;
    }
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        arrB[i] = x;
    }
    sort(arrA, arrA + n);
    sort(arrB, arrB + n);
    int ans = 0;
    for (int i = 0;i < n;i++) { // 큰 수와 작은 수를 순서대로 곱해 더한다
        ans += arrA[i] * arrB[n-1-i]; 
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1977번 완전제곱수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1977

글쓴이는 정해진 범위의 제곱수 배열을 먼저 만들어서 문제를 해결했다.

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int main()
{
    int sqr[101]; // 0부터 10000까지의 제곱수 array 만들기
    for (int i = 0;i < 101;i++) {
        sqr[i] = i * i;
    }
    int x, y;
    cin >> x >> y;
    int ans = 0;
    int minimum = 0;
    bool chk = true;
    for (int i = 0;i < 101;i++) { // x 이상 y 이하 제곱수를 찾아 연산
        int n = sqr[i];
        if (x <= n and n<=y) {
            ans += n;
            if (chk) { // 범위 내 가장 작은 제곱수는 최초 한번만
                minimum = n;
                chk = false;
            }
        }
    }
    if (ans == 0) { // 0은 아무 제곱수도 더하지 않았을 때만 나올 수 있다
        cout << -1;
    }
    else { // 제곱수가 하나라도 더해졌을 때
        cout << ans << "\n" << minimum;
    }
    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14470번 방 번호이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1475

이 문제를 풀기 위해서, 먼저 주어진 자연수를 10진수로 표기할 때 0~9가 각각 몇 개씩 필요한지 조사한다.

그리고, 6과 9의 개수는 같이 조사한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <set>
using std::cin;
using std::cout;
using std::string;
using std::multiset;

int main()
{
    string n; // 자연수 n을 문자열로 읽어온다
    cin >> n;
    int nlen = n.length();
    multiset<int> ms;
    for (int i = 0;i < nlen;i++) {
        ms.insert(n[i]); // n의 각 자릿수를 multiset에 넣는다.
    }
    int mx = 0;
    for (int i = 48;i < 57;i++) { //48~57: 0~9의 ASCII 코드 번호, 9는 6에서 같이 세니 제외
        int cnt = ms.count(i);
        if (i == 54) { //6의 개수를 셀 때
            cnt += ms.count(57) + 1; //9의 개수를 같이 센다.
            cnt /= 2; //1을 더해 2로 나누면 필요한 세트의 개수를 알 수 있다.
        }
        if (cnt > mx) {//필요한 가장 많은 세트수를 구한다
            mx = cnt;
        }
    }
    cout << mx;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10988번 문제인 팰린드롬인지 확인하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10988

palindrome(팰린드롬; 회문) 문자열이란 앞에서부터 읽어도 뒤에서부터 읽어도 같은 문자열을 의미한다.

예를 들어, level 이나 madam 등의 영단어는 palindrome 문자열이다.

이번 문제는 문자열 s의 길이를 slen이라 할 때 n번째 글자와 slen-(n-1)번째 문자가 같은지 반복문으로 확인해보았다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

int main()
{
    string s;
    cin >> s;
    int slen = s.length();
    int ans = 1;
    for (int i = 0;i < slen / 2;i++) { // 절반만 확인해도 나머지 반은 자동으로 확인
        if (s[i] != s[slen - i-1]) { // 앞에서 (i+1)번째 글자와 뒤에서 (i+1)번째 글자 비교
            ans = 0;
            break;
        }
    }
    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10808번 문제인 알파벳 개수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10808

이 문제는 주어진 문자열에 들어있는 각 알파벳의 개수를 출력하는 문제이다.

ASCII 코드와 반복문을 이용해 문제를 풀어보자.

문자열 s에서의 'a'의 개수는 문자열 s를 살펴보면서 'a'의 개수를 직접 세어 구할 수 있다.

마찬가지로 문자열 s에서의 'b'의 개수는 문자열 s를 살펴보면서 'b'의 개수를 직접 세어 구할 수 있다.

'a' 이상 'z' 이하의 각 문자에 대하여 위와 같이 문자열 s를 한번씩 살펴보면서 각 알파벳의 개수를 세는 코드를 작성해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

int main() {
    string s;
    cin >> s;
    for (int i = 97;i < 123;i++) { // ASCII 코드: char(97)~char(122)는 a~z이다
        int cnt = 0;
        char alphabet = char(i);
        int slen = s.length();
        for (int j = 0;j < slen;j++) { // string s의 각 글자가 현재 알파벳인지 확인
            if (s[j] == alphabet) {
                cnt += 1;
            }
        }
        cout << cnt << ' ';
    }
}