[Algorithm] 알고리즘과 입출력

시간복잡도

O(1) : 단순 계산 (a+b와 같은 연산, 배열에 접근하는 연산)

O(logN) : N개를 절반으로 계속해서 나눔

O(N) : 1중 for문

O(N logN) : 

O(N²) : 2중 for문

O(N³) : 3중 for문

O(2ᴺ) : 크기가 N인 집합의 부분 집합

O(N!) : 크기가 N인 수열

테스트케이스가 주어지지 않은 경우의 입출력

두 정수를 입력받아 합을 출력하는 문제이지만, 입력받을 정수쌍(테스트케이스)의 개수와 종료 조건이 없다

따라서 정상적인 프로그램 종료를 위해 데이터 소스로부터 더 이상 읽을 수 있는 데이터가 없음을 나타내야하는 문제가 발생한다

이런 경우를 EOF(End of File) 이라고 한다

// 1
#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    int a,b;
    
    while(scanf("%d %d",&a,&b) != EOF){
        cout << a+b << endl;
    }
}
 
// 2
#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    int a,b;
    
    while(cin >> a >> b){
        cout << a+b << endl;
    }
}

한 줄 입력 받기

=> Getline 활용하기

# C 스타일 cin.getline(str, 20);

getline : cin객체의 멤버 문자열 입력 함수

str : 문자열을 입력 받을 메모리의 주소

# C++ 스타일 getline(cin, str, ' ');

getline : cin의 객체가 아닌 보통 함수

str : 문자열 입력받을 string 객체

' ' : 구분자(종결문자) - Default로 Enter키를 취함

#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    string str;
    while(getline(cin,str)){
        cout << str << endl;
    }
}
 

#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    string str;
    while(getline(cin,str,'\n')){
        cout << str << endl;
    }
}
 

한글자만 입력받기

=> scanf("%1d", &n); 을 활용하여 1개씩 문자입력

#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    int n;
    int sum = 0;
    cin >> n;
    
    while(n--){
        int s;
        scanf("%1d",&s);
        sum += s;
    }
    cout << sum << endl;
}
 

10개씩 끊어 출력하기

=> char 배열을 이용하여 cin을 통해 입력받은뒤, strlen을 활용하여 반복문으로 10개씩 잘라서 출력

#include <iostream>
#include <cstring>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    char str[100];
    
    cin >> str;
    
    for(int i=0; i<strlen(str); i++){
        cout << str[i];
        if((i+1)%10 == 0)
            cout << endl;
    }
    cout << endl;
}