Chap3 자료구조

jade·2025년 2월 13일

DoIt_Algorithm_C++

목록 보기

2/7

Algorithm 공부 책: DoIt 알고리즘 코딩테스트 C++편

1. vector

1)개념 정의

C++ 라이브러리에서 제공하는 자료구조 컨테이너
크기가 자동으로 늘어남
인덱스를 이용해 각 데이터에 접근 가능

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

int main() {
	vector<int> A;
	A.push_back(1);//마지막에 1추가
	A.insert(A.begin(), 7); //맨 앞에 7 삽입
	A.insert(A.begin() + 2, 5);
	A[4] = 5; //값변경
	
	A.pop_back(); //마지막 값 삭제
	A.erase(A.begin() + 3);
	A.clear(); //모든 값 삭제
	
	A.size(); //A의 크기 구하기
	A.front(); //A의 처음값
	A.back(); //마지막 값
	A.at(5); //index5에 해당하는 값
	A.begin(); //첫번째 데이터 위치
	A.end(); //마지막 데이터의 다음위치
}

숫자의 합 구하기 11720번

#include <iostream>
using namespace std;
#define _CRT_SECURE_NO_WARNINGS
int main() {
	int N;
	string numbers;
	cin >> N;
	cin >> numbers;
	int sum = 0;
	for (int i = 0; i < numbers.length(); i++) {
		sum += numbers[i] - '0';
	}
	cout << sum;
	return 0;
}

평균 구하기 1546

#include <iostream>
using namespace std;
#include <vector>
int main() {
	int N=0;
	cin >> N;

	vector <int> score(N);
	int max = 0;
	double mean = 0;
	for (int i = 0; i < N; i++) {
		cin >> score[i];
		if (max < score[i]) max = score[i];
	}
	for (int j = 0; j < N; j++) {
		mean+= (double)score[j] / max * 100;
	}
	cout << mean/N;
	return 0;
}

2. 누적 구간합 Prefix Sum Array

1) 개념

S[i]=A[0]+A[1]+⋯+A[i]
시간복잡도를 O(n) → O(1)로 단축

구간합 11659번

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

int main() {
	//C와 C++ 입출력 버퍼의 동기화
	//false -> 동기화를 비활성화 -> 불안정하지만 속도 향상
	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;
}

구간합구하기5 11660번

문제: 백준문제 바로 보러가기
원리

구간합을 만들 때 원배열(1,1)부터 (x,y)까지의 직사각형 안에 들어있는 숫자들의 합을 dp(x,y)에 넣는다
파란색 구간의 합= dp(x2,y2)-dp(x1-1,y2)-dp(x2,y1-1)+dp(x1-1,y1-1)

코드

#include <iostream>
using namespace std;
#include <vector>
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));
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int temp;
			cin >> temp;
			if (i == 1 && j == 1) A[i][j] = temp;
			else if (i == 1) A[i][j] = A[i][j - 1] + temp;
			else if (j == 1) A[i][j] = A[i - 1][j] + temp;
			else A[i][j] = A[i][j - 1] + A[i - 1][j] - A[i - 1][j - 1] + temp;
		}
	}
	for (int i = 0; i < M; i++) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << A[x2][y2] - A[x1-1][y2] - A[x2][y1-1] + A[x1-1][y1-1]<<"\n";

	}

	return 0;
}

나머지 합 10986번

문제: 백준 문제 보러가기

3. 투포인터

1) 개념

문제를 통해 투 포인터 개념을 알아보자

연속된 자연수의 합 구하기 2018번

문제: 백준 문제 보러가기

두개의 포인터를 이용한다, 원하는 합 15(=res)라고 해보자
pos1= 1, pos2=1이면, 1에서 시작해 1로 끝나는 것이므로 1을 의미한다.
pos1=1, pos2=4면, 1+2+3+4=10 을 의미한다.
pos2=2, pos2=4면, 2+3+4=9를 의미한다
만약 합(=sum)이 15보다 크면, sum=sum-pos1 을 한다
→ 만약 sum=18이 나온 상황이라면,
sum=sum-pos1을 하고 pos1을 오른쪽으로 한칸 이동한다.
→ 이경우 18-1 = 17이 된다.
이때도 17>15이기 때문에 다시 sum=sum-pos1을 한다.
17-2=15, sum=res가 되는 경우를 찾았다! → 이 때는 pos2를 늘린다.

코드

#include <iostream>
using namespace std;
#include <vector>
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	cin >> N;

	int pos1 = 1; int pos2 = 1;
	int sum = 1;
	int cnt = 1;

	while (pos2 != N) {
		if (sum == N) {
			cnt++;
			pos2++;
			sum = sum + pos2;
		}
		else if (sum > N) {
			sum = sum - pos1;
			pos1++;
		}
		else {
			pos2++;
			sum = sum + pos2;
		}
	}
	cout<< cnt<< "\n";
	return 0;
}

주몽 1940번

문제: 백준 보러가기

코드

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b;
	cin >> a;
	cin >> b;

	vector <int> num(a, 0);

	//입력받기
	for (int i = 0; i < a; i++) {
		cin >> num[i];
	}
	//오름차순 정렬
	sort(num.begin(), num.end());

	int i=0, j=a-1; int cnt = 0;

	while (i <  j) {
			if (num[i]+num[j]==b) {
				cnt++;
				i++; j--;
			}
			else if (num[i] + num[j] > b) {
				j--;
			}
			else {
				i++;
			}
		
	}
	cout << cnt;

	return 0;

}

좋다 1253번

문제 백준문제 보러가기
코드

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

int main() {
	int N;
	cin >> N;
	vector <int> num(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	sort(num.begin(), num.end());
	int i,j;
	int cnt = 0;

	for (int w = 0 ; w < N; w++) {
		int want = num[w];
		i = 0; j = N - 1;

		while (i < j) {

			if (i == w) {
				i++;
				continue; //스스로를 포함하는 것을 제외
			}
			if (j == w) {
				j--;
				continue; //스스로를 포함하는 것을 제외
			}
			
			if(num[i] + num[j] == want) {
				cnt++;
				break;
			}
			else if (num[i] + num[j] > want) {
				j--;
			}
			else {
				i++;
			}	

		}
	}

	cout << cnt ;
	return 0;
}

원래 w=2부터 하려고 함 → 서로 다른 숫자들이 들어올 경우 오름차순 이후의 배열의 0번째와 1번째는 좋은수가 될 수 없음
그러나 문제에 “서로 다른” 숫자가 들어온다고 말하지 않음
따라서 w=2부터 하면 입력이 0 0 0 들어올 경우 방어 불가

4. 슬라이딩 윈도우

1. 개념

두개의 포인터로 범위 지정한 다음
범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결
투포인터와 비슷

dna 비밀번호 12891번

문제 : 백준 보러가기

#include <iostream>
using namespace std;
#include <vector>
int S, P;
int myarr[4];
int checkarr[4];
int checked = 0;
int res = 0;
void Add(char c);
void Remove(char c);

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

	//입력받기
	cin >> S >> P;
	string str;
	cin >> str;

	for (int i = 0; i < 4; i++) {
		cin >> checkarr[i];
		if (checkarr[i] == 0) checked++; **//만약 0인경우 이미 조건 성립 -> checked++**
	}

	//초기문자열보내기
	for (int i = 0; i < P; i++) {
		Add(str[i]);
	}
	if (checked == 4) res++;

	**//슬라이딩 윈도우 처리**
	for (int i = P; i < S; i++) {
		int j = i - P;
		Add(str[i]);
		Remove(str[j]);
		if (checked == 4) {
			res++;
		}
	}
	cout << res;
	return 0;
}
void Add(char c) {
	switch (c){
	case 'A': 
		myarr[0]++; 
		if (myarr[0] == checkarr[0]) checked++;
		break;
	case'C':
		myarr[1]++;
		if (myarr[1] == checkarr[1]) checked++;
		break;
	case 'G':
		myarr[2]++;
		if (myarr[2] == checkarr[2]) checked++;
		break;
	case 'T':
		myarr[3]++; 
		if (myarr[3] == checkarr[3]) checked++;
		break;
	
	}
}

void Remove(char c) {
	switch (c) {
	case 'A':
		if (myarr[0] == checkarr[0]) checked--;
		myarr[0]--;
		break;
	case'C':
		if (myarr[1] == checkarr[1]) checked--;
		myarr[1]--;
		break;
	case 'G':
		if (myarr[2] == checkarr[2]) checked--;
		myarr[2]--;
		break;
	case 'T':
		if (myarr[3] == checkarr[3]) checked--;
		myarr[3]--;
		break;
	
	}

}

슬라이딩 윈도우 처리!!

→ 뒷문자열 하나씩 추가하고 맨 앞문자열 하나씩 제거하고,
→ 하나씩 옮겨질 때마다 checked==4가 되는지 확인하여 문자열이 정답에 해당하는지 아닌지 확인
초기 상태 checked !!
- 만약 checkarr[i]가 0이라면, 해당 문자는 따로 체크하지 않아도 조건을 이미 만족.
- 하지만 현재는 Add()가 호출되기 전에는 checked를 갱신하지 않기 때문에 이 경우를 놓칠 수 있음
  
  ⇒ 초기 상태에서 checkarr가 0인 항목은 checked++로 갱신시켜놔야함!

최솟값 찾기2 11003

→ pass

5. 스택과 큐

1) 개념

스택

후입선출LIFO
push, pop, top(top위치에 있는 데이터 확인)

선입선출FIFO
back(큐에서 가장 끝 데이터), front(큐에서 가장 앞 데이터)
push, pop

우선순위 큐

우선순위가 높은 데이터가 먼저 나오는 큐
일반적으로 heap을 이용해 구현
힙은 트리 종류 중 하나 → 챕터 6에 또 나옴

스택 수열 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> wantarr(N, 0);
	vector <char> resarr;
	stack <int> mystack;
	bool yes = true;

	//배열 입력
	for (int i = 0; i < N; i++) {
		cin >> wantarr[i];
	}
	
	int pop_cnt = 0; //pop을 몇번 했는지
	int num = 1; //오름차순 해야함

	for(int i=0;i<N;i++){
		while (wantarr[i] >= num) {
			mystack.push(num++);
			resarr.push_back('+');
		}

		if (wantarr[i] == num) {
			mystack.pop();
			resarr.push_back('-');
		
		}
		else if(wantarr[i] < num){
			if (**!mystack.empty()** && mystack.top() == wantarr[i]) {
				mystack.pop();
				resarr.push_back('-');
			}
			else {
				cout << "NO";
				yes = false;
				break;
			}

		}
	}
	if (yes) {
		for (int i = 0; i < resarr.size(); i++) {
			cout << resarr[i] << "\n";
		}
	}
	return 0;
}

오큰수 17298번

문제 백준문제보러가기
코드 → 스택 이용

내가 짠 코드
마지막 부분에 배열을 reverse 시켜야 하는 불편함이 존재..

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

int main() {
	int N;
	cin >> N;
	vector <int> inarr(N, 0);
	vector <int> outarr(N, 0);

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

	stack <int> st; //출력할 스택

	for (int i = 0; i < N; i++) {
		int f = inarr[i];
		int o = 0;

		if (i == N - 1) {
			st.push(-1);
			break;
		}

		for (int j = i + 1; j < N; j++) {
			if (f < inarr[j]) {
				o = inarr[i];
				st.push(inarr[j]);
				break;
			}
		}
		if (o == 0) { 
			st.push(-1); 
		}
	}

	for (int i = 0; i <N; i++) {
		outarr[i] = st.top();
		st.pop();
	}
	
	for (int i = N-1; i >=0 ; i--) {
		cout << outarr[i] << " ";
	}

	return 0;
}

정답 코드
내가 짠 것보다 더 효율적이라고 생각
내가 짠 코드에서는 마지막에 outarr를 reverse 시키기 위한 for반복문이 들어가는데, 이 정답코드는 그런 과정을 거치지 않음!
정답코드의 핵심
stack에 배열의 값이 아닌 배열의 인덱스를 push
인덱스를 이용해 값을 비교하는 것이 포인트!

#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> inarr(N, 0);
	vector <int> outarr(N, 0);

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

	stack <int> st; //출력할 스택
	st.push(0);
	
	//핵심 코드!
	for (int i = 1; i < N; i++) {
		while (!st.empty() && inarr[st.top()] < inarr[i]) {
			outarr[st.top()] = inarr[i];
			st.pop();
		}
		st.push(i);
	}
	
	while (!st.empty()) {
		outarr[st.top()] = -1;
		st.pop();
	}

	for (int i = 0; i < N; i++) {
		cout << outarr[i] << " ";
	}

	return 0;
}

카드 게임 2164번

문제: 백준문제보러가기
코드

큐를 이용하면 되는 문제
front()는 제거하는 역할이 아니라 front에 있는 값을 알려만 주기 때문에, front() → pop()을 같이 해줘야함

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

int main() {
	int N;
	cin >> N;

	queue<int> q;

	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	while (q.size() > 1) {
		q.pop();
		q.push(q.front());
		q.pop();
	}

	cout << q.front();

	return 0;

}

절댓값 힙 11286번

문제: 백준문제 보러가기

우선순위큐를 힙을 통해 구현하는 방법

자신이 직접 우선순위를 정할 때는 구조체를 생성해야함
priority_queue는 "true를 반환하는 값이 먼저 오도록 정렬"
즉, a > b이면 a가 b보다 우선순위가 낮음을 의미합니다.
a=5 b=3 → 5>3 true → 3이 더 높은 우선순위
a=2 b=4 → 2>4 false → 2가 더 높은 우선순위

struct cmp{
  bool operator()(int a, int b){
      return a>b; //작은값이 더 높은 우선순위
  }
}

#include <queue>
priority_queue<int, vector<int>, cmp>;// 루트가 최소값인 우선순위 큐 선언

코드

우선순위를 잘 코딩하는것이 핵심
절댓값이 같으면 음수 우선, 다르면 절댓값 작은 수가 우선

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

struct compare{
	bool operator()(int a, int b) {
		int first = abs(a);
		int last = abs(b);

		//절댓값이 같으면 음수가 우선순위가 높음
		if (first==last) {
			return a > b;
		}
		//절댓값이 작은 수가 우선순위가 높음
		else {
			return first > last;
		}
	}

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

	int N;
	cin >> N;

	priority_queue<int, vector<int>, compare> q;
	
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		if (temp == 0) {
			if (q.empty()) {
				cout << 0 << '\n'; 
			}
			else {
				cout << q.top() << '\n';
				q.pop();
			}
		}
		else {
			q.push(temp);

		}
	}

	return 0;
}

jade

이전 포스트

C++문법 정리

다음 포스트

Chap3 자료구조

DoIt_Algorithm_C++

1. vector

1)개념 정의

숫자의 합 구하기 11720번

평균 구하기 1546

2. 누적 구간합 Prefix Sum Array

1) 개념

구간합 11659번

구간합구하기5 11660번

나머지 합 10986번

3. 투포인터

1) 개념

연속된 자연수의 합 구하기 2018번

주몽 1940번

좋다 1253번

4. 슬라이딩 윈도우

1. 개념

dna 비밀번호 12891번

최솟값 찾기2 11003

5. 스택과 큐

1) 개념

스택 수열 1874번

오큰수 17298번

카드 게임 2164번

절댓값 힙 11286번

우선순위큐를 힙을 통해 구현하는 방법

C++문법 정리

Chap4 정렬

0개의 댓글