[Algorithm] 1주차 스터디 - 알고리즘 기초 및 배열

Group Study (2023-2024)/Algorithm

[Algorithm] 1주차 스터디 - 알고리즘 기초 및 배열

noname64 2023. 11. 6. 19:32

1. 복잡도

시간복잡도

: 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

- 주로 O 표기법(가장 큰 대표항으로 시간복잡도를 나타내는 방법)을 이용하여 표기한다.

- O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

공간복잡도

: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

- 배열의 차원과 관련되어있다.

2. 자료형

정수 자료형

: char(1 byte), short(2 byte), int(4 byte), long long(8 byte)

*1 byte = 8 bit

- 할당된 메모리 범위를 넘어서는 경우 overflow 및 underflow가 발생하는 경우 형변환을 이용하여 해결한다.

실수 자료형: float(4 byte), double(8 byte)

- (부호 + 지수부 + 가수부)의 형태로 수를 저장한다.

- 컴퓨터는 2진수로 계산하기 때문에 10진수 변환시 오차가 발생할 수 있다.

- 10의 N제곱을 le를 이용하여 나타낼 수 있다(ex: le-12 = 10^(-12), le9 = 10^9).

*유효숫자(float - 6자리, double - 15자리, long long - 19자리)의 범위가 다른 자료형으로 형변환시 오차가 발생할 수 있으므로 주의한다.

3. STL(Standard Template Library)

: C++ 기본 제공 라이브러리

- 다양한 알고리즘과 자료구조가 구현되어있다.

- 함수 인자로 사용할 시 값을 복사하므로 기존 인자에 영향을 주지않는다는 점을 주의해아한다.

*<vector> - 가변 배열(배열과 거의 동일한 기능을 수행하는 자료구조로, 크기를 자유자재로 늘이거나 줄일 수 있다.)

4. C++ 표준 입출력

기능 \ 언어	C	C++
입력	scanf	cin
출력	printf	cout

*주의할 점

- C에서는 C++ string을 처리할 수 없다.

- 두 입력 방법 모두 공백을 포함한 문자열을 입력받지 않으므로 getline 등을 이용하는 것을 추천한다.

- cin/cout 이용시 입출력으로 인한 시간 초과가 발생할 수 있으므로

ios::sync_with_stdio(0)	C++ stream과 C stream의 동기화를 끊는 역할(이후 scanf/printf 사용 불가하며, 0 대신 false를 사용할 수 있다.
cin.tie(0)	온라인 저지 사이트에서는 출력만을 필요로하므로 입력 버퍼를 비우지 않도록 한다. nullptr 대신 0을 사용하였다.

- endl(개행문자("\n") 출력(및 버퍼 비우기)용으로 사용하는 명령어)을 사용하지 말고 개행문자를 출력할 것을 권장한다.

- 디버거를 사용하는 것보다 직접 출력해서 확인하는 것을 추천한다.

4. 배열

: 메모리 상에 원소를 연속하게 배치한 자료구조

- 성질:

1. O(1)에 k번째 원소를 확인/변경할 수 있다(메모리 상에 원소를 연속하게 배치한 자료구조이기 때문이다.).
2. 추가적으로 소모되는 메모리의 양(=overhead)이 거의 없다.
3. cache hit가 높다(메모리 상에 데이터들이 붙어있기 때문이다.).
4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸린다.

- 시간복잡도:

1. 임의 위치 원소를 추가/제거 - O(N) (나머지 원소를 밀어야하기 때문이다.)
2. 임의 위치 원소 확인/변경 - O(1)
3. 배열의 끝에 원소 추가/제거 - O(1)

- C++에서의 배열

*전체를 특정 값으로 초기화시킬 때 - memset 함수, for문, algorithm 헤더의 fill 함수(추천) 이용한다.

5. 1주차 필수 문제 풀이

15552번 빠른 A+B (https://www.acmicpc.net/problem/15552)

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int num, a, b, sum;
    
    cin >> num;
    
    for (int i = 0; i < num; i++) {
        cin >> a >> b;
        sum = a + b;
        cout << sum << "\n";
    }
    
    return 0;
}

문제 요약

: 정수를 입력받고 해당 정수만큼의 테스트케이스에서 각각 두 수의 합을 출력하는 문제이다.

코드 요약

: 첫 줄에서 테스트케이스의 수 num을 입력받아 각각의 num번째 입력에서 두 수의 합을 출력하는 코드이다.

2445번 별 찍기 - 8 (https://www.acmicpc.net/problem/2445)

#include <iostream>
using namespace std;

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

    int num;
    cin >> num;

    for (int i = 1; i <= num; i++) {
        for(int j = 1; j <= i; j++) {
            cout << "*";
        }
        
        for(int j = 1; j <= num - i; j++) {
            cout << "  ";
        }
        
        for(int j = 1; j <= i; j++) {
            cout << "*";
        }
        
        cout << "\n";
    }

    for (int i = num - 1; i > 0; i--) {
        for(int j = i; j > 0; j--) {
            cout << "*";
        }
        
        for(int j = 1; j <= num - i; j++) {
            cout << "  ";
        }
        
        for(int j = i; j > 0; j--) {
            cout << "*";
        }
        
        cout << "\n";
    }

    return 0;
}

문제 요약: 정수 하나를 입력받아 *을 한 개부터 해당 정수개까지 늘리고, 또 다시 한 개까지 줄여가며 출력하는 문제이다. 이 때 해당 모양이 대칭이 되도록 한다.

코드 요약: 숫자 num을 입력받아 *이 한 개부터 num개가 될 때까지 하나씩 늘려가며 출력한 후, 다시 한 개가 될 때까지 하나씩 줄여가며 출력하는 코드이다.

2480번 주사위 세 개 (https://www.acmicpc.net/problem/2480)

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

int main() {
    int a, b, c, reward;
    cin >> a >> b >> c;
    
    if ((a == b) && (b == c)) {
        reward = 10000 + a * 1000;
    } else if (a == b || b == c || c == a) {
        int matching = (a == b) ? a : ((b == c) ? b : c);
        reward = 1000 + matching * 100;
    } else {
        reward = max(max(a, b), c) * 100;
    }
    
    cout << reward;
    
    return 0;
}

문제 요약: 세 수를 입력받아 모두 같으면 (해당 수 * 1,000) + 10,000, 두 개가 같으면 (같은 수 * 1,000) + 100, 모두 다르면 (가장 큰 수 * 100)를 출력하는 문제이다.

코드 요약: 세 수 a, b, c를 입력받아 if문을 통해 모두 같은 경우, 두 개가 같은 경우, 모두 다른 경우의 상금을 계산하였다. 두 개가 같은 경우에서 삼항연산자를 사용하여 같은 수의 값을 저장하였다.

2577번 숫자의 개수 (https://www.acmicpc.net/problem/2577)

#include <iostream>
using namespace std;

int main() {
    int a, b, c, mul;
    int result[10] = {0};
    
    cin >> a >> b >> c;
    mul = a * b * c;
    
    while (mul > 0) {
        result[mul % 10] += 1;
        mul /= 10;
    }
    
    for (int i = 0; i < 10; i++) {
        cout << result[i] << "\n";
    }
    
    return 0;
}

문제 요약: 입력받은 세 수를 모두 곱한 후 각 자리 숫자에 있는 0부터 9까지의 정수의 개수를 세는 문제이다.

코드 요약: 입력받은 세 수의 곱을 10으로 나눈 나머지를 인덱스로 활용하여 해당 숫자의 개수를 세는 코드이다.

28431번 양말 짝 맞추기 (https://www.acmicpc.net/problem/28431)

#include <iostream>
using namespace std;

int main() {
    int a, b, c, d, e;
    int arr[10] = {0};
    
    cin >> a >> b >> c >> d >> e;
    arr[a]++, arr[b]++, arr[c]++, arr[d]++, arr[e]++;
    
    for (int i = 0; i < 10; i++) {
        if (arr[i] != 0 && arr[i] % 2 == 1)
            cout << i;
    }
    
    return 0;
}

문제 요약: 정수 다섯 개를 입력받아 같은 값이 홀수 개일 경우 해당 수를 출력하는 문제이다.

코드 요약: 양말에 쓰인 숫자는 0에서 9 사이의 수이므로 크기가 10인 배열 arr를 이용하여 각 숫자를 인덱스로 하는 원소가 해당 숫자의 양말을 나타내도록 하였다. 이후 양말이 있는 배열의 원소가 홀수일 때 짝이 없는 양말이 발생하므로 해당 인덱스를 반환한다.

참고 자료: 강좌 "실전 알고리즘" 0 ~ 3강(바킹독)

저작자표시 비영리 변경금지

'Group Study (2023-2024) > Algorithm' 카테고리의 다른 글

[Algorithm] 5주차 스터디 - 수학 / 이분탐색, 투포인터 / 해시 (1)	2023.12.04
[Algorithm] 4주차 스터디 - 정렬, 다이나믹 프로그래밍, 그리디 (1)	2023.11.27
[Algorithm] 3주차 스터디 - 재귀, 백트래킹 (1)	2023.11.20
[Algorithm] 2주차 스터디 - 스택, 큐, 덱 / BFS, DFS (1)	2023.11.13

현재글[Algorithm] 1주차 스터디 - 알고리즘 기초 및 배열

GDG on Campus Sookmyung