배열, 리스트, 벡터

숫자의 합 구하기

https://www.acmicpc.net/problem/11720

 

#include <iostream>
using namespace std;

int main() {
  int N = 0;
  string numbers;
  cin >> N;
  cin >> numbers;

  int sum = 0;
  for (int i = 0; i < numbers.length(); i++) {
    // numbers[i]를 정수로 계산하여 sum에 누적하기
    sum += numbers[i] - '0';
  }
  cout << sum << "\n";
  return 0;
}

 

// string형 -> 숫자형(int, long, double, float) 형 변환

#inlcude <string> // 헤더 파일 추가
string sNum = "1234";
string sNum_d = "1234.56";
int inum = stoi(sNum);
long lnum = stol(sNum);
double dnum = stod(sNum_d);
float fnum = stof(sNum_d);

// 숫자형(int, long, double, float) -> string형 형 변환

#inlcude <string> // 헤더 파일 추가
int inum = 1234;
long lnum = 1234;
double dnum = 1234.56;
float fnum = 1234.56f;
string intToString = to_string(inum);
string longToString = to_string(lnum);
string doubleToString = to_string(dnum);
string floatToString = to_string(fnum);

 

평균 구하기

https://www.acmicpc.net/problem/1546

 

#include <iostream>
using namespace std;

int main() {
  int N = 0;
  int A[1000];
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  long sum = 0;
  long max = 0;
  
  for (int i = 0; i < N; i++) {
    if (A[i] > max) {
      max = A[i];
    }
    sum = sum + A[i];
  }
  // 한 과목과 관련된 수식을 모두 더한 후 관련된 수식으로 변환해 로직이 간단해짐
  double result = sum * 100.0 / max / N;
  cout << result << "\n";
  return 0;
}

 

구간 합 구하기 1

https://www.acmicpc.net/problem/11659

 

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int suNo, quizNo;
  cin >> suNo >> quizNo;
  int S[100001] = {};

  for (int i = 1; i <= suNo; i++) {
    int temp;
    cin >> temp;
    S[i] = S[i-1] + temp; // 구간 합 구하기
  }
  for (int i = 0; i < quizNo; i++) {
    int start, end;
    cin >> start >> end;
    cout << S[end] - S[start-1] << "\n";
  }
  
  return 0;
}

 

구간 합 구하기 2

https://www.acmicpc.net/problem/11660

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int N, M;
  cin >> N >> M;

  vector<vector<int>> A(N + 1, vector<int>(N + 1, 0));
  vector<vector<int>> D(N + 1, vector<int>(N + 1, 0));

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      cin >> A[i][j];
      // 구간 합 구하기
      D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
    }
  }
  for (int i = 0; i < M; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    // 구간 합 배열로 질의에 답변하기
    int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
    cout << result << "\n";
  }
  
  return 0;
}

 

나머지 합 구하기

https://www.acmicpc.net/problem/10986

 

연속된 자연수의 합 구하기

https://www.acmicpc.net/problem/2018

 

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  int count = 1;
  int start_index = 1;
  int end_index = 1;
  int sum = 1;

  while (end_index != N) {
    if (sum == N) { // 답을 찾았을 때
      count++;
      end_index++;
      sum = sum + end_index;
    }
    else if (sum > N) { // 현재 합이 답보다 클 때
      sum = sum - start_index;
      start_index++;
    }
    else { // 현재 합이 답보다 작을 때
      end_index++;
      sum = sum + end_index;
    }
  }
  cout << count << "\n";
  
  return 0;
}

 

주몽의 명령

https://www.acmicpc.net/problem/1940

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, M;
  cin >> N >> M;
  vector<int> A(N, 0);

  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());

  int count = 0;
  int i = 0;
  int j = N - 1;

  while (i < j) { // 투 포인터 이동 원칙에 따라 포인터를 이동하여 처리
    if (A[i] + A[j] < M) {
      i++;
    }
    else if (A[i] + A[j] > M) {
      j--;
    }
    else {
      count++;
      i++;
      j--;
    } 
  }
  cout << count << "\n";

  return 0;
}

 

'좋은 수' 구하기

https://www.acmicpc.net/problem/1253

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  vector<int> A(N, 0);

  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  int Result = 0;

  for (int k = 0; k < N; k++) {
    long find = A[k];
    int i = 0;
    int j = N - 1;

    while (i < j) { // 투 포인터 알고리즘
      if (A[i] + A[j] == find) { // 서로 다른 두 수의 합인지 체크
        if (i != k && j != k) {
          Result++;
          break;
        }
        else if (i == k) {
          i++;
        }
        else if (j == k) {
          j--;
        }
      }
      else if (A[i] + A[j] < find) {
        i++;
      }
      else {
        j--;
      }
    }
  }
  cout << Result << "\n";

  return 0;
}

 

DNA 비밀번호

https://www.acmicpc.net/problem/12891

 

#include <iostream>
using namespace std;

int checkArr[4];
int myArr[4];
int checkSecret = 0;
void Add(char c);
void Remove(char c);

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int S, P;
  cin >> S >> P;
  int Result = 0;
  string A;
  cin >> A;

  for (int i = 0; i < 4; i++) {
    cin >> checkArr[i];
    if (checkArr[i] == 0) {
      checkSecret++;
    }
  }

  for (int i = 0; i < P; i++) { // 초기 P 부분 문자열 처리
    Add(A[i]);
  }
  if (checkSecret == 4) {
    Result++;
  }
  // 슬라이딩 윈도우 처리 부분
  for (int i = P; i < S; i++) {
    int j = i - P;
    Add(A[i]);
    Remove(A[j]);
    // 4자리 수에 대한 크기가 모두 충족되었을 때는 유효한 비밀번호
    if (checkSecret == 4) {
      Result++;
    }
  }
  cout << Result << "\n";
   
  return 0;
}

void Add(char c) { // 새로 들어온 문자를 처리하는 함수
  switch (c) {
    case 'A':
      myArr[0]++;
      if (myArr[0] == checkArr[0])
        checkSecret++;
    break;
    case 'C':
      myArr[1]++;
      if (myArr[1] == checkArr[1])
        checkSecret++;
    break;
    case 'G':
      myArr[2]++;
      if (myArr[2] == checkArr[2])
        checkSecret++;
    break;
    case 'T':
      myArr[3]++;
      if (myArr[3] == checkArr[3])
        checkSecret++;
    break;
  }
}

void Remove(char c) { // 제거할 문자를 처리하는 함수
  switch (c) {
    case 'A':
      if (myArr[0] == checkArr[0])
        checkSecret--;
      myArr[0]--;
      break;
    case 'C':
      if (myArr[1] == checkArr[1])
        checkSecret--;
      myArr[1]--;
      break;
    case 'G':
      if (myArr[2] == checkArr[2])
        checkSecret--;
      myArr[2]--;
      break;
    case 'T':
      if (myArr[3] == checkArr[3])
        checkSecret--;
      myArr[3]--;
      break;
  }
}

 

최솟값 찾기 1

https://www.acmicpc.net/problem/11003

 

#include <iostream>
#include <deque>
using namespace std;
typedef pair<int, int> Node;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, L;
  cin >> N >> L;
  deque<Node> mydeque;

  for (int i = 0; i < N; i++) {
    int now;
    cin >> now;
    // 값이 들어올 때마다 정렬하지 않고
    // 현재 수보다 큰 값을 덱에서 제거하여 시간 복잡도를 줄임
    while (mydeque.size() && mydeque.back().first > now) {
      mydeque.pop_back();
    }
    mydeque.push_back(Node(now, i));
    // 범위에서 벗어난 값은 덱에서 제거
    if (mydeque.front().second <= i - L) {
      mydeque.pop_front();
    }
    cout << mydeque.front().first << ' ';
  }
  return 0;
}

 

 

스택으로 수열 만들기

https://www.acmicpc.net/problem/1874

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  vector<int> A(N, 0);
  vector<char> resultV;

  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  stack<int> myStack;
  int num = 1; //오름차순 수
  bool result = true;

  for (int i = 0; i < A.size(); i++) {
    int su = A[i]; // 현재 수열의 수
    // 현재 수열값 >= 오름차순 자연수: 값이 같아질 때까지 push() 수행
    if (su >= num) {
      while (su >= num) { // push()
        myStack.push(num++);
        resultV.push_back('+');
      }
      myStack.pop();
      resultV.push_back('-');
    }
    // 현재 수열값 < 오름차순 자연수: pop()을 수행하여 수열 원소를 꺼냄
    else {
      int n = myStack.top();
      myStack.pop();
      // 스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크다면 수열 출력 불가능
      if (n > su) {
        cout << "NO";
        result = false;
        break;
      }
      else {
        resultV.push_back('-');
      }
    }
  }
  if (result) {
    for (int i = 0; i < resultV.size(); i++) {
      cout << resultV[i] << "\n";
    }
  }
  
  return 0;
}