- C 언어 기본 세션 & 알고리즘 문제 풀이
- 줌을 통한 C 언어 출력과 입력 변수 학습
- 코딩 테스트 대비 알고리즘 문제 풀이
- C 언어 기본 세션
- 줌을 통해 라이브 세션으로 C 언어의 출력(Helloe World) 입력 scanf 변수 int, char 등을 학습
- 이미 해봤던 단계지만 실습 도중 %d, %c 와같이 변수의 자료형에 따른 형식 지정자가 기억이 잘안나 조금 버벅 거림
- 몇번 실습과정을 통해 문제 해결
- 실버4 11399번 ATM문제(그리디, 정렬)
- 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하기 위해서는 단순하게 오름차순으로 배열한다음 각 사람이 필요한 시간을 수하는 것이 가장 최소이기에 sort()함수로 정렬한 다음 구하면 해결
- sort()함수 비교연산자에 관한 정리
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> p;
for (int i = 0; i < N; i++)
{
int temp = 0;
cin >> temp;
p.push_back(temp);
}
sort(p.begin(), p.end());
int sum = 0;
int answer = 0;
for (int i = 0; i < p.size(); i++)
{
sum += p[i];
answer += sum;
}
cout << answer << "\n";
return 0;
}
// sort()의 비교함수 사용법
// 방법 1: 함수 포인터
bool compare(int a, int b)
{
return a > b; // 내림차순
}
sort(p.begin(), p.end(), compare);
// 방법 2: 람다 함수 (권장)
sort(p.begin(), p.end(), [](int a, int b) {
return a > b; // 내림차순
});
// 방법 3: greater<int> (표준 라이브러리)
sort(p.begin(), p.end(), greater<int>()); // 내림차순
- 실버3 11659번 구간 합 구하기4(누적 합) - 시간 초과
- 처음 에는 단순하게 vector로 배열을 만든 다음 for문을 통해 i부터 j까지의 구간을 매번 더하는 식으로 진행하였으나 시간복잡도가 커져 시간 초과가 남
- 이 과정에서 단순 for문으로 더하는게 아닌 acculmulatr함수를 통해 구하는 방법을 배움
- 시간 초과를 해결하기 위한 방법으로 입력과 동시에 각 인덱스에는 인덱스 까지의 합을 저장
- 각 인덱스 까지의 누적합이 이미 저장 되어있기 때문에 i부터 j 구간의 합은 인덱스j(1부터 j까지의 합) - 인덱스i - 1(0부터 i -1 까지의 합) 으로 바로 구해짐
// 첫 풀이 - 시간 초과
// 실버 3 11659번 구간 합 구하기 4 (누적 합)
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
vector<int> v(N + 1);
for (int i = 1; i <= N; i++)
{
cin >> v[i];
}
vector<int> sum(M);
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
sum[i] = accumulate(v.begin() + a, v.begin() + b + 1, 0); // 처음에는 v[a], v[b]처럼 int값을 넘겨줬으나 accumulate는 반복자(v.begin(), v.end() 와 같은) v.begin()에서 a와 b 값을 각각 더해서 인덱스를 맞춰 해결
}
for (int i = 0; i < M; i++)
{
cout << sum[i] << '\n';
}
return 0;
}
// 실버 3 11659번 구간 합 구하기 4 (누적 합)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
vector<long long> v(N + 1, 0); // long long으로 오버플로우 방지, 인덱스는 숫자값 그대로 쓰기위해 0을 비우기때문에 N + 1, 그리고 0으로 초기화
//각 N의 값들의 입력과 동시에 각 인덱스 까지의 누적 합으로 저장
for (int i = 1; i <= N; i++)
{
int x;
cin >> x;
v[i] = v[i - 1] + x;
}
vector<int> sum(M);
// 각 인덱스 까지의 누적합이 이미 저장 되어있기 때문에 i부터 j 구간의 합은 인덱스j(1부터 j까지의 합) - 인덱스i - 1(0부터 i -1 까지의 합) 으로 바로 구해짐
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
sum[i] = v[b] - v[a - 1];
}
for (int i = 0; i < M; i++)
{
cout << sum[i] << '\n';
}
return 0;
}
- 내일은 코딩테스트에 더 자주나오는 문제 풀이 및 언리얼 강의 1-2 ~ 1-3 학습
