-
[Algorithm] 1주차 스터디 - 알고리즘 기초 및 배열GDSC 23-24 2023. 11. 6. 19:28
* GDSC 23-24 1분기 스터디의 1주차 게시물
목차
1. 복잡도
2. 자료형
3. C++ 표준 입출력
4. 배열
5. 1주차 필수 문제 풀이
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강(바킹독)