[SCCC] #1 과제

수 정렬하기 2_2751번

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int n, tmp;
    vector<int> vec;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        vec.push_back(tmp);
    }

    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i++)
        cout << vec[i] << "\n";

    return 0;
}

C++ 개념

• #include <iostream> : 표준 입출력
• using namespace std; : std::cout, std::cin 등과 같이 std:: 가 필요한 곳에 이를 생략하고 쓸 수 있게 함
  -#include <algorithm> : sort() 사용
  • sort(시작값 주소, 끝값 주소) 형태일 경우 오름차순으로 정렬함
  • vector의 경우 sort(vec.begin(), vec.end()) 으로 나타냄
• #include <vector> : 배열 대신에 vector 사용
  • vector<int> vec : 1차원 vector 선언
  • stack 형태로 vec.push_back(x), vec.pop_back(x) 함
  • vec.begin(),vec.end(), vec.size() 등 다양한 함수 지원

---

좌표 정렬하기_11650번

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int x, y;
    vector<pair<int, int>> vec;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        vec.push_back({x, y});
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i++)
    {
        cout << vec[i].first << " " << vec[i].second << "\n";
    }

    return 0;
}

C++ 개념

• 2차원 vector
  • 선언 : vector<pair<int, int>> vec
    • <int, int> 모양이 짝을 이룸
  • vec[i].first 은 <int(1), int(2)> 에서 int(1) 을 말함
  • vec[i].second 은 <int(1), int(2)> 에서 int(2) 을 말함

---

수 찾기_1920번

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vecN;
vector<int> vecM;

//존재하면 1을, 존재하지 않으면 0을 return
int binarySearch(int target, int low, int high)
{
    if (low > high)
        return 0;
    else
    {
        int mid = (low + high) / 2;
        if (vecN[mid] == target)
            return 1;
        else if (target < vecN[mid])
            return binarySearch(target, low, mid - 1);
        else
            return binarySearch(target, mid + 1, high);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); // cin 속도 향상 위해

    int n, m, tmp;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        vecN.push_back(tmp);
    }
    sort(vecN.begin(), vecN.end());

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> tmp;
        vecM.push_back(tmp);
    }

    for (int i = 0; i < m; i++)
        cout << binarySearch(vecM[i], 0, n - 1) << "\n";

    return 0;
}

C++ 개념

• main 함수 밖에서 전역 변수 선언 가능
• C++ 성능 향상 방법
  • ios_base::sync_with_stdio(0); cin.tie(0); : 입출력 속도 향상
  • endl -> "\n" : 개행을 의미. endl 이 비교적 매우 느림
• 이진탐색(BinarySearch)
  • if (low > high) : 존재하지 않아서 low 가 더 커지는 경우
  • low, high, mid 값은 index 값이 들어감
  • 이진탐색에 이용되는 배열(또는 벡터)는 정렬된 상태여야 함
  • target 을 찾을 때까지 계속 재귀

---

정수 제곱근_2417번

코드

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long long n;
    long long q;
    cin >> n;
    answer = (long long)sqrt(n);
    if (q * q >= n)
        cout << q;
    else
        cout << q + 1;
    return 0;
}

C++ 개념

• int -> long -> long long
• float -> float
• 제곱/제곱근 연산 : pow(a, b)(a^b), sqrt(n)(제곱근)
• 소수점 연산 : floor(n)(내림), ceil(n)(올림), round(n)(반올림)

풀이노트

• 입력받는 수가 매우 큰 경우 제곱근 연산에서 부동 소수점에서 오차가 생길 수 있음. q = sqrt(n) 에서 그치지 않고, q^2 >= n 를 만족시키는지 한 번 더 검증함
• 이진탐색(BinarySearch) 로도 해결할 수 있음

소요시간 : 90분 (검증로직에서 오래걸림)