[알고리즘] 1. 기초 코드 작성 요령

Wonder_Land🛕·2022년 12월 3일

[알고리즘]

목록 보기

1/11

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

전반적 내용
: '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I'
: '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 II'
: 'Jinhan's Note' 중 'Theme 01. 입출력 _ cin, cout'
: 'Jinhan's Note' 중 'Theme 01. 입출력 _ stringstream'
: 'Jinhan's Note' 중 'Theme 01. 입출력 _ FastIO'

시간, 공간복잡도

정수 자료형

실수 자료형

STL과 함수 인자

표준 입출력

FastIO

Q&A

마치며

1. 시간∙공간복잡도

1) 시간복잡도

시간복잡도(Time Complexity)
: 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

빅오표기법(Big-O Notation)
: 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

컴퓨터는 1초에 대략 3~5억개의 연산 처리 가능

(출처: '바킹독'님의 블로그 중 '[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I')

O(1) : 상수 시간
O(lg N) : 로그 시간
O(N) : 선형 시간
lgN이나 N의 거듭제곱끼리의 곱 : 다항 시간
O(2ⁿ) : 지수 시간
지수 시간은 N이 25이하 정도로 굉장히 작은게 아니면 시간 제한을 통과하기 힘듦
팩토리얼은 지수 시간보다 훨씬 가파르기 때문에, 11이하 정도로 굉장히 작은게 아니면 시간 제한을 통과하기 힘듦
N의 크기 허용 시간복잡도
N ≤ 11 O(N!)
N ≤ 25 O(2ⁿ)
N ≤ 100 O(N⁴)
N ≤ 500 O(N³)
N ≤ 3,000 O(N²lgN)
N ≤ 5,000 O(N²)
N ≤ 1,000,000 O(NlgN)
N ≤ 10,000,000 O(lgN), O(1)

N의 크기	허용 시간복잡도
N ≤ 11	O(N!)
N ≤ 25	O(2ⁿ)
N ≤ 100	O(N⁴)
N ≤ 500	O(N³)
N ≤ 3,000	O(N²lgN)
N ≤ 5,000	O(N²)
N ≤ 1,000,000	O(NlgN)
N ≤ 10,000,000	O(lgN), O(1)

문제 1.
N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 5만 이하의 자연수이다.

int func1(int N){
    int sum = 3*(N/3 * (N/3 + 1))/2 +
              5*(N/5 * (N/5 + 1))/2 -
              15*(N/15 * (N/15 + 1))/2;
    return sum;
}

원래는 1부터 N까지 순회하는 O(N)으로 코드를 작성.
그런데 본문에 O(1)로 할 수 있다는 내용을 참고하여 위 코드로 작성함.
(3의 배수의 합) + (5의 배수의 합) - (15의 배수의 합)을 이용

문제 2.
주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성하라. arr의 각 수는 0이상 100 이하이고 N은 100이하이다.

int func2(int n){
    for(int i = 0; i < N; i++){
    	for(int j = i+1; j < N; j++){
        	if(arr[i] + arr[j] == 100){
            	return i;
             }
         }
     }
    return sum;
}

문제 3.
N이 제곱수이면 1을 반환하고, 제곱수가 아니면 0을 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.

int func3(int N){
    for(int i = 0; i<= N; i++){
        if(i*i == N) return 1;
    }
    return 0;
}

문제 4.
N이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.

int func4(int N){
    int i = 1;
    while(2 * i <= N) { i *= 2;}
    return i;
}

2) 공간복잡도

공간복잡도(Space Complexity)
: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

512MB = 1.2억개의 int
보통 코딩테스트의 경우, 공간복잡도의 문제보다는, 시간복잡도 떄문에 문제를 많이 틀림.

2. 정수 자료형

자료형 범위
unsigned char 0~2^8-1 (255)
char -2^7 ~ 2^7-1 (-128~127)
short 2^15-1(32,767)
int -2^31 ~ 2^31-1 (-21억 ~ 21억 사이)
long long -2^63 ~ 2^63-1
Integer Overflow
: 정수형의 자료형으로 표현할 수 있는 수의 범위를 넘어갈 때 발생하는 오류

자료형	범위
unsigned char	0~2^8-1 (255)
char	-2^7 ~ 2^7-1 (-128~127)
short	2^15-1(32,767)
int	-2^31 ~ 2^31-1 (-21억 ~ 21억 사이)
long long	-2^63 ~ 2^63-1

3. 실수 자료형

실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.
(float는 상대 오차 10^(-6)까지, double은 10^(-15)까지 안전. 즉, 참값이 1인 경우, 1 - 10^(-15)부터 1+10^(-15)사이의 값을 가짐)
: 실수자료형은 오차가 필연적으로 발생하므로, 문제에서 절대/상대 오차를 허용한다는 단서를 줌. 없으면 정수에서 해결할 수 있는 문제.
두 자료형의 차이가 크기 떄문에, 실수 자료형을 사용해야할 경우 float 대신, double형을 써야함!
double에 long long 범위의 정수를 함부로 담으면 안된다.(int는 상관 없음)
: double은 유효 숫자가 15자리인데, long long은 최대 19자리니까 1과 1 + 10^18을 구분할 수 없어, 같은 값으로 저장.
실수를 비교할 때는 등호를 사용하면 안된다.
: 0.1 + 0.1 + 0.1 != 0.3

4. STL과 함수 인자

함수인자로 숫자/구조체/STL은 값의 복사가 일어나고, 배열은 주소값을 이용

bool cmp1(vector<int> v1, vector<int> v2, int idx){
    return v1[idx] > v2[idx];
}

: 해당 코드의 시간복잡도는 O(1)이 아닌, O(N). v1과 v2를 인자로 이용하여 복사본을 만드는 비용이 추가되어야 함.

bool cmp2(vector<int>& v1, vector<int>& v2, int idx){
    return v1[idx] > v2[idx];
}

: 해당 코드는 인자를 reference로 사용. 따라서 호출될 때 복사본을 만들지 않고, 참조 대상의 주소 정보만 넘기므로 시간복잡도는 O(1).

5. 표준 입출력

C++에는 cin, cout함수가 있음.
cout은 공백을 포함한 문자열을 받을 때 사용하기 힘듦
: 줄바꿈(\n)이 나오기 전까지 입력을 받는다고 명시하기
: gets함수 사용하기. 그러나 보안상의 이유로 제거됨
: getline을 사용. 대신 type이 C++ string이어야 함.
ios::sync_with_stdio(0), cin.tie(0)을 입력해야만, 시간초과를 막을 수 있음.
ios::sync_with_stdio(0)
: 기본적으로 C stream(scanf, printf)와 C++ stream(cin, cout)은 분리되어 있음. 하지만 코드의 출력을 위해 두 stream은 동기화되어 있음.
그러나 만약 두 stream을 동시에 쓰지 않고 하나의 stream만을 사용한다면 굳이 동기화가 필요 없음.
(참고로, VS 2017/2019에서는 해당 명령어를 무시하고 무조건 동기화 유지. 하지만 채점 서버는 gcc이므로 차이가 있음)
cin.tie(0)
: cin명령어를 수행하기 전에 cout 버퍼를 비우지 않도록 하는 명령어
endl 사용하지 않기
: endl은 개행문자(\n)를 출력하고 출력 버퍼를 비우는 명령
: 어차피 judge는 프로그램이 종료될 때 출력이 어떻게 생겼는지로 채점하기 때문에 중간에 버퍼를 비울 필요가 없음
string stream(istringstream + ostringstream)을 이용하면, 문자열로부터 입력을 받아올 수 있음. 또한 출력값을 문자열로 저장할 수 있음
: istringstream형 변수를 선언한 후, 생성자 또는 str 함수를 이용해 스트림으로 이용할 문자열 이용

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
	fastio;
	istringstream in_1("123 456 789");
	int n;
	while (in_1 >> n) cout << n << '\n';

	istringstream in_2;
	string s = "hi my name is jinhan", t;
	in_2.str(s);
	cout << in_2.str() << '\n';
	while (in_2 >> t) cout << t << '\n';
}

: ostringstream형 변수를 선언한 뒤 cout처럼 사용

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int main(){
	fastio;
	ostringstream out;
	out << "Hello World!" << "\n";
	out << setw(5) << setfill('0') << 123 << "\n";
	out << fixed << setprecision(10) << 123.456789 << "\n";
	string s = out.str();
	cout << s << "\n";
}

6. FastIO

cin, cout은 scanf, printf보다 빠르지만 그래도 느림
: 1) 입력, 출력 외에 다른 기능을 제공하기 위해 추가적 연산 수행. 2) 일반적인 경우의 입력을 위해 작성되었기 때문에 모든 case를 고려함(ex 0 이상의 정수가 입력될 때 -를 확인). 3) 입출력 버퍼의 크기가 작음
: 1, 2번은 어쩔 수 없지만, 3번은 개선할 수 있음
3번은 방법은, 더 큰 char[] 버퍼에 입∙출력값을 한 번에 많이 읽고 보내면 됨.
: 이 때 char 배열에 보내고 읽을 떄 read, write와 같은 Low-Level I/O 함수가 사용됨
: 하지만, cin, cout과 같이 다양한 자료형을 처리하는 기능은 결여. 따라서 직접 파싱하면서 자료형을 변환해야 함(밑의 코드는 이 과정을 구현한 코드. 따라서 코드 최상단에 복붙하여 사용하면, cin, cout이 mmap, wrtie로 구현된 빠른 입출력 함수로 대체)

#include <bits/stdc++.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
using namespace std;

/////////////////////////////////////////////////////////////////////////////////////////////
/*
 * Author : jinhan814
 * Date : 2021-05-06
 * Source : https://blog.naver.com/jinhan814/222266396476
 * Description : FastIO implementation for cin, cout. (mmap ver.)
 */
constexpr int SZ = 1 << 20;

class INPUT {
private:
	char* p;
	bool __END_FLAG__, __GETLINE_FLAG__;
public:
	explicit operator bool() { return !__END_FLAG__; }
    INPUT() {
        struct stat st; fstat(0, &st);
        p = (char*)mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);
    }
	bool IsBlank(char c) { return c == ' ' || c == '\n'; }
	bool IsEnd(char c) { return c == '\0'; }
	char _ReadChar() { return *p++; }
	char ReadChar() {
		char ret = _ReadChar();
		for (; IsBlank(ret); ret = _ReadChar());
		return ret;
	}
	template<typename T> T ReadInt() {
		T ret = 0; char cur = _ReadChar(); bool flag = 0;
		for (; IsBlank(cur); cur = _ReadChar());
		if (cur == '-') flag = 1, cur = _ReadChar();
		for (; !IsBlank(cur) && !IsEnd(cur); cur = _ReadChar()) ret = 10 * ret + (cur & 15);
		if (IsEnd(cur)) __END_FLAG__ = 1;
		return flag ? -ret : ret;
	}
	string ReadString() {
		string ret; char cur = _ReadChar();
		for (; IsBlank(cur); cur = _ReadChar());
		for (; !IsBlank(cur) && !IsEnd(cur); cur = _ReadChar()) ret.push_back(cur);
		if (IsEnd(cur)) __END_FLAG__ = 1;
		return ret;
	}
	double ReadDouble() {
		string ret = ReadString();
		return stod(ret);
	}
	string getline() {
		string ret; char cur = _ReadChar();
		for (; cur != '\n' && !IsEnd(cur); cur = _ReadChar()) ret.push_back(cur);
		if (__GETLINE_FLAG__) __END_FLAG__ = 1;
		if (IsEnd(cur)) __GETLINE_FLAG__ = 1;
		return ret;
	}
	friend INPUT& getline(INPUT& in, string& s) { s = in.getline(); return in; }
} _in;

class OUTPUT {
private:
	char write_buf[SZ];
	int write_idx;
public:
	~OUTPUT() { Flush(); }
	explicit operator bool() { return 1; }
	void Flush() {
        write(1, write_buf, write_idx);
		write_idx = 0;
	}
	void WriteChar(char c) {
		if (write_idx == SZ) Flush();
		write_buf[write_idx++] = c;
	}
	template<typename T> int GetSize(T n) {
		int ret = 1;
		for (n = n >= 0 ? n : -n; n >= 10; n /= 10) ret++;
		return ret;
	}
	template<typename T> void WriteInt(T n) {
		int sz = GetSize(n);
		if (write_idx + sz >= SZ) Flush();
		if (n < 0) write_buf[write_idx++] = '-', n = -n;
		for (int i = sz; i --> 0; n /= 10) write_buf[write_idx + i] = n % 10 | 48;
		write_idx += sz;
	}
	void WriteString(string s) { for (auto& c : s) WriteChar(c); }
	void WriteDouble(double d) { WriteString(to_string(d)); }
} _out;

/* operators */
INPUT& operator>> (INPUT& in, char& i) { i = in.ReadChar(); return in; }
INPUT& operator>> (INPUT& in, string& i) { i = in.ReadString(); return in; }
template<typename T, typename std::enable_if_t<is_arithmetic_v<T>>* = nullptr>
INPUT& operator>> (INPUT& in, T& i) {
	if constexpr (is_floating_point_v<T>) i = in.ReadDouble();
	else if constexpr (is_integral_v<T>) i = in.ReadInt<T>(); return in; }

OUTPUT& operator<< (OUTPUT& out, char i) { out.WriteChar(i); return out; }
OUTPUT& operator<< (OUTPUT& out, string i) { out.WriteString(i); return out; }
template<typename T, typename std::enable_if_t<is_arithmetic_v<T>>* = nullptr>
OUTPUT& operator<< (OUTPUT& out, T i) {
	if constexpr (is_floating_point_v<T>) out.WriteDouble(i);
	else if constexpr (is_integral_v<T>) out.WriteInt<T>(i); return out; }

/* macros */
#define fastio 1
#define cin _in
#define cout _out
#define istream INPUT
#define ostream OUTPUT
/////////////////////////////////////////////////////////////////////////////////////////////

7. Q&A

8. 마치며

이번에는 자료구조&알고리즘 입니다.

사실 책을 사야하나 아님 온라인 강의를 사서 들어봐야 하나 고민하고 있었는데...

정말 좋은 블로그를 발견했습니다.

입니다.

이 두 분의 글들을 참고하며 알고리즘 공부를 해보려고 합니다.

두 분의 강의는 정말 자세하고 저같은 초보자가 이해하기 큰 무리 없이 정말 섬세하게 구성되어 있습니다. (감동ㅠㅠ)
그리고 각 강의마다 백준 연습문제들도 직접 선정해서 제공해주고 있습니다.
그리고 다 무료!!!!!!!!!!!!!!!!!!!!!!!!!!
진짜 들숨에 무한한 건강과 날숨에 엄청난 재력을 얻으시길...(매일 밤마다 기도할게용😉)

두 분의 커리큘럼(?)도 비슷하고 워낙 유명하신 분들이라 신뢰감이 뿜뿜하네요😎

또 열심히 해보겠습니다!!