JArchive 프로그래밍 일기

이번 강의는 어려워도 꼭 필요한 기초 내용인 시간 복잡도와 자료형 내용이다.

목차 

0x00 시간, 공간 복잡도 

0x01 정수 자료형 

0x02 실수 자료형 

0x00 시간, 공간 복잡도

[중요]시간복잡도 

입력의 크기와 문제 해결에 걸리는 시간의 상관관계다. 

예를 들어, 반복문을 n번 실행하는 경우, n에 비례한다고 퉁쳐서 표현한다. 

다른 예시를 보자. 

사람들은 '정렬'되어 있음을 유의하자. 

만약 50명 사람이 정렬된 이름순으로 서있다면, 가운데 사람의 이름을 물어봐서 25명을 남기고, 

또 반을 쪼개서 12명, 6명, 3명.. 이런 식이면 '가나다'인 사람을 찾을 수 있다. 

만약 16명이 있다면,

반으로 나눠서 8명, 반으로 나눠서 4명, 또 반으로 나눠서 2명, 반으로 나눠서 마지막 1명을 찾을 수 있다. 

16명이 있을 때, 4번의 연산으로 타겟을 찾을 수 있다.  이 것을 lg N에 비례한다고 한다. 

빅오표기법 

주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법이다. 

O(1) : 상수시간 
O(lgN): 로그시간 
O(N): 선형시간 
O(lg N)부터 O(N²)  : 다항시간
O(2^N): 지수시간 
O(N!) : 팩토리얼 

공간 복잡도 

512MB 일때, 대강 1.2억개의 int를 사용할수 있음을 기억하자.  (int 1개가 4byte 임을 이용해 계산할 수 있다. )

0x01 정수 자료형

char 자료형은 1byte == 8bit 이다. 즉, 8개의 bit로 숫자를 표현한다. 

0000 0001 은 10진수로 1이다. 

0000 0010 은 10진수로 2를 표현한다. 

그런데, 맨 왼쪽은 -2의 7승이다. 맨 왼쪽 비트는 '부호비트'의 역할을 한다. 

왜그럴까?

음수를 표현하기 위함이다.

참고: 2의 보수(2's complement)

보수의 의미? 보충해주는 수를 의미한다. 

1에 대한 2의 보수는 1이다. 1에 1을 보충해줘야 2가 된다. 

1에 대한 10의 보수는 9이다. 1에 9를 보충해주면 10이 된다는 의미다.

비트는 0과 1밖에 없는 2진수임을 유의하자. 1에 대한 2의 보수는 1이다.

어떤 정수를 표현하는 N개 비트가 있다. 

이 비트를 전부 반전시키고, 1을 더하면 1의 보수가 나온다. 

예시는 아래와 같다.  1이 -1이 된다. 

어떤 수를 부호를 바꾸고자 한다면, 비트를 반전시킨 뒤 1을 더하면 된다. 

sign비트로 음수 표현하기 

부호를 표현하는 비트가 있냐 없냐에 따라서 표현할 수 있는 수의 범위가 2배 차이 난다. 

unsiged의 의미는 부호비트(sign)의 여부를 의미한다. 

Integer Overflow 문제 

정수의 표현 범위를 넘어서 sign비트가 바뀌면 overflow가 발생한다. 

맨 왼편이 -2의 7승, 즉 -128값을 가지기 때문이다. 따라서 각 자료형의 범위에 맞게 연산해야 함을 유의하자. 

큰 수를 다룰 때 8byte 정수 자료형 long long을 쓰자. 

만약 unsigned long long 을 넘어선다면 string으로 처리해야 하는데, Python을 쓰는게 C++ string을 쓰는 것 보다 편하다. 

0x02 실수 자료형 

실수 자료형은 float(4byte)와 double(8byte)가 있다. 

float는 1bit 32개다. 

double은 1bit 64개다. 

컴퓨터는 2진수를 기반으로 실수를 표현하기 때문에, 오차가 있음을 기억하자!

1을 3으로 나눠보자. 

10진수로 0.33333.... 무한소수로 길어진다.

2진수로 표현하면 ?  0.010101.. 로 역시 무한소수가 나온다. 

2진수의 과학적 표기법 IEEE 754 format 

실수를 표현하기 위해 32칸 혹은 64칸을 sign field, exponent field, fraction field 로 나눈다. 

sign field : 양수/음수 구분 
exponent field: 지수
fraction field : 유효숫자 

-6.75를 예로 들어보자. 

sign field :  음수니까 1로 표시 

exponent field:  여기서는 2승이니까 2

fraction field : 맨 앞의 1은 뺀, 1011이 적힌다. (맨 왼쪽부터 2의 -1승, 2의 -2승 ... 자리임)

[중요] 실수 자료형의 특징!

1. 실수 자료형은 필연적으로 오차가 있다. 

float는 유효숫자 6자리, double은 유효숫자 15자리 뿐이다.

여기서 유효숫자 15자리라는 의미는 
참 값이 1이라고 할 때, 1 - 10의 -15승에서 1 + 10의 +15승 사이의 값을 가진다는게 보장된다는 의미다. 

2. double에 long long 범위의 정수를 함부로 담지 말자. 

double은 유효숫자가 15자리인데, long long은 최대 19자리 이다. 

따라서 10의 18승과 10의 18승을 구분할 수 없고, 오차 섞인 값이 저장될 수 있다. 

3. 실수를 비교할 때는 등호를 사용하면 안 된다. 

실수 연산 시 오차가 발생할 수 밖에 없기 때문이다. 

아까 배운 것 처럼, 유효숫자가 float는 6자리, double은 15자리 뿐으로 표현에 제한이 있기 때문이다.

두 실수가 같은지 알고 싶을 때 ! 
두 실수의 차가 대략 10의 -12승 이하면 동일하다고 처리하는 것이 안전하다. 
 1e-12 는 10의 -12승을 의미하는 표기다. 

다음 강의에서는 표준 입출력과 코드 작성 팁에 대해 배운다. 

2의 보수 자료 출처: 2진수의 수와 음수 표현법

공부 자료 출처: 바킹독 실전 알고리즘 0x01강 

C++ 로 알고리즘 풀기 연습을 하기 위해 바킹독님 강의를 들었다.

복습을 위해 유용한 부분만 정리했다. 내용과 이미지는 바킹독님 강의에서 가져왔음을 밝힌다. 

목차

1. IDE 세팅 

2. 환경 세팅 

1. IDE 세팅 : C++ 컴파일 할 수 있는 환경 만들기 

Visual Studio 2017/2019 , Clion, Visual Studio Code, 또는 상대적으로 가벼운 DEV C++ 를 써도 된다. 

거의 모든 채점 서버는 gcc 컴파일러를 사용함. 

2. bits/stdc++.h 추가 

JetBrain IDE를 좋아해서 clion을 썼는데, bits/stdc++.h은 사용자정의 헤더파일이라 바로 include가 안됬다.

bits/stdc++.h를 추가하는 방법을 찾아보고 포스팅해뒀다.  

C++ 로 알고리즘 문제풀기에 필요한 내용이어서 메모해둔다. 

백준에서 문제풀때 bits/stdc++.h 만 추가하면 되니까 유용하다.

다른 온라인 저지 사이트에서는 사용 안되는 곳이 있으니깐 유의하자.  

stdc++.h는 c++ 대부분의 헤더파일명을 다 갖고 있다. 그래서 따로 #include "vector" 해 줄 필요가 없다.

환경은 mac M1이고, Clion으로 프로젝트를 만들었다. 아무 설정 없으면 file not found가 뜬다. 

헤더 파일을 못찾는다. 파일이 없으니까 못찾음. 

1.  터미널 열고  gcc 라이브러리 경로를 확인한다. 

/Library/Developer 어쩌구 경로가 보인다. 

Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.5 (clang-1205.0.22.9)
Target: arm64-apple-darwin21.1.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

2. 아래 명령으로 라이브러리 참조 경로로 이동하자. 

cd /Library/Developer/CommandLineTools/usr/include

3. 아래 명령으로 해당 경로에서 Finder를 열 수 있다. 

open ./

3. include 디렉토리 하위에 bits 라는 디렉토리를 만들자. 

4. bits 디렉토리 하위에 stdc++.h  파일을 하나 만든다. 

gcc-mirror 깃허브에서 코드를 받을 수 있다.

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/precompiled/stdc%2B%2B.h

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

5. include 해서 실행되는지 확인하자. 

문제

윷놀이 백준 2490 c++

"맞았습니다."코드 

#include "iostream"
using namespace std;

// 백준 2490 윷놀이
int a, result;
string str = "DCBAE";

void func(){

    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 4; j++){
            cin >> a;
            result += a;
        }
        cout << str[result] << '\n';
        a = result = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    func();
    return 0;
}

리뷰 

답으로 출력할 문자를 이어붙여서 문자열 "DCBAE" 로 만들었다. 

1의 개수를 인덱스로 썼다. 

문제 

홀수 백준 2576

"맞았습니다"코드 

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 백준 2576 홀수
int a;
vector<int> v;
int sumOfOdd;

void func(){

    for(int i = 0; i < 7; i++){
        cin >> a;
        if(a % 2 == 1){
            sumOfOdd += a;
            v.push_back(a);
        }
    }

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

    if(sumOfOdd == 0){
        cout << -1;
    }else{
        cout << sumOfOdd << '\n';
        cout << v[0];
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    func();
    return 0;
}

문제

주사위 세개

"맞았습니다." 코드 

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 백준 2480 주사위 세개

vector<int> v(3);
int result;

void func(){

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

    if(v[0] == v[2]) { // 셋 다 같은 수
        cout << 10000 + (1000 * v[0]);
    }
    else if((v[0] == v[1]) || (v[1] == v[2])) { // 2개가 같은 수. 항상 공통인 숫자는 2번째 숫자.
        cout << 1000 + (v[1] * 100) ;
    }
    else{ // 셋 다 서로 다른 수
        cout << v[2] * 100;
    }
}

void input(){
    cin >> v[0] >> v[1] >> v[2];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    func();

    return 0;
}

리뷰

조건식을 잘못써서 처음에 틀렸다. 

틀린 코드는 아래와 같다. 

if((v[0] == v[1]) == v[2]) { // 셋 다 같은 수
    result = 10000 + (1000 * v[0]);
}

틀린 이유는 숫자끼리 비교해야하는데, true와 숫자를 비교했기 때문이다. 

주사위 숫자가 1 1 3 일때, 1 과 1은 같으니까 참이 나온다. 

따라서 1과 3을 비교하게 되는게 아니라, 

true와 3을 비교하게 되므로 항상 true가 나온다. 그래서 틀렸다. 

고쳐서 맞은 코드는 아래와 같다.

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 백준 2480 주사위 세개

vector<int> v(3);
int result;

void func(){

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

    if((v[0] == v[1]) && (v[1] == v[2])) { // 셋 다 같은 수
        result = 10000 + (1000 * v[0]);
    }
    else if((v[0] == v[1]) && (v[1] != v[2])) { // 앞쪽 2개가 같은 수
        result = 1000 + (v[0] * 100) ;
    }
    else if((v[0] != v[1]) && (v[1] == v[2])) { // 뒤쪽 2개가 같은 수
        result = 1000 + (v[1] * 100) ;
    }
    else{ // 셋 다 서로 다른 수
        result = v[2] * 100;
    }
    cout << result;
}

void input(){
    cin >> v[0] >> v[1] >> v[2];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    func();

    return 0;
}

좀더 깔끔한 코드는 아래와 같다. 

일단 정렬을 한다. 

셋 다 같은 수라면, 첫번째 숫자와 세번째 숫자가 같을 것이다. 

    if(v[0] == v[2]) { // 셋 다 같은 수
        cout << 10000 + (1000 * v[0]);
    }

같은 수가 2개라면, 1번째 2번째가 같거나. 2번째와 3번째가 같을 것이다. 

두 조건 모두 가운데 숫자가 공통으로 들어간다. 

    else if((v[0] == v[1]) || (v[1] == v[2])) { // 2개가 같은 수. 항상 공통인 숫자는 2번째 숫자.
        cout << 1000 + (v[1] * 100) ;
    }

바킹독님 코드 참고 

바킹독님의 코드를 보고 나니깐 벡터를 안써도 됬겠구나 싶었다. 

정렬하지 않고, 숫자 두 개가 같은 경우는 3가지 다.

1째와 2째를 비교. 2째와 3째를 비교. 1째와 2째를 비교. 

셋 다 다른 수일 때는, max() 함수를 쓴 것이 좋았다.