반응형
그룹액티비티 1번
#include <iostream>
#include <vector>
using namespace std;
vector<int> stack; // 전역 스택
int top = -1; // 스택의 꼭대기를 나타내는 변수
// push 함수: 스택에 값을 추가
void push(int value) {
stack.push_back(value);
top++;
}
// pop 함수: 스택에서 값을 제거하고 반환
int pop() {
if (top >= 0) {
int value = stack[top];
stack.pop_back();
top--;
return value;
} else {
cout << "Stack Underflow" << endl;
return -1; // 스택이 비어있으면 -1 반환
}
}
// printBinary 함수: 스택을 사용하여 2진수로 변환 후 출력
void printBinary(int n) {
while (n > 0) {
push(n % 2); // 2로 나눈 나머지를 스택에 push
n /= 2; // n을 2로 나눔
}
// 스택에서 pop하여 2진수를 출력
while (top >= 0) {
cout << pop();
}
cout << endl;
}
// 메인 함수
int main() {
int number;
cout << "Enter a positive integer: ";
cin >> number;
if (number <= 0) {
cout << "Please enter a positive integer!" << endl;
} else {
cout << "Binary of " << number << ": ";
printBinary(number);
}
return 0;
}설명
- 전역 스택:
- vector<int>를 전역적으로 선언하여 스택처럼 사용합니다.
- push와 pop 구현:
- push는 vector에 값을 추가하고, pop은 마지막 값을 반환한 뒤 제거합니다.
- 이진수 변환 로직:
- 입력 숫자를 2로 나눈 나머지를 스택에 저장하고, 스택에서 값을 꺼내면서 출력하여 이진수를 생성합니다.
응용 문제 1: 특정 비트를 뒤집는 2진수 변환 함수
문제
스택을 이용하여 양의 정수를 2진수로 변환한 후, 사용자가 입력한 특정 비트를 뒤집어 새로운 2진수를 출력하는 프로그램을 작성하시오.
#include <iostream>
#include <vector>
using namespace std;
vector<int> stack; // 전역 스택
int top = -1; // 스택의 꼭대기 위치
// push 함수: 스택에 값을 추가
void push(int value) {
stack.push_back(value);
top++;
}
// pop 함수: 스택에서 값을 제거하고 반환
int pop() {
if (top >= 0) {
int value = stack[top];
stack.pop_back();
top--;
return value;
} else {
cout << "Stack Underflow" << endl;
return -1; // 스택이 비어있으면 -1 반환
}
}
// 2진수 변환 함수
void printBinaryWithFlip(int n, int flipPosition) {
vector<int> binaryRepresentation;
// 숫자를 2진수로 변환하여 스택에 저장
while (n > 0) {
push(n % 2);
n /= 2;
}
// 스택에서 값을 꺼내며 2진수 저장
while (top >= 0) {
binaryRepresentation.push_back(pop());
}
// 뒤집을 비트가 범위를 벗어났는지 확인
if (flipPosition < 0 || flipPosition >= binaryRepresentation.size()) {
cout << "Error: Flip position out of range!" << endl;
return;
}
// 출력 전 원래 2진수 출력
cout << "Original binary: ";
for (int bit : binaryRepresentation) {
cout << bit;
}
cout << endl;
// 특정 위치 비트를 뒤집음
binaryRepresentation[flipPosition] = 1 - binaryRepresentation[flipPosition];
// 결과 출력
cout << "Modified binary: ";
for (int bit : binaryRepresentation) {
cout << bit;
}
cout << endl;
}
int main() {
int number, flipPosition;
cout << "Enter a positive integer: ";
cin >> number;
if (number <= 0) {
cout << "Please enter a positive integer!" << endl;
return 0;
}
cout << "Enter the bit position to flip: ";
cin >> flipPosition;
printBinaryWithFlip(number, flipPosition);
return 0;
}
그룹액티비티 2번
2. Call Stack, System Stack, Runtime Stack 설명 및 Stack Overflow 정의
Call Stack / System Stack / Runtime Stack
이 용어는 모두 프로그램 실행 중 함수 호출과 반환을 관리하는 메모리 영역을 의미합니다.
- 역할:
- 함수 호출 시 함수의 매개변수, 지역 변수, 복귀 주소 등이 저장됩니다.
- 함수가 종료되면 관련 데이터는 스택에서 제거됩니다.
- 특징:
- LIFO (Last In, First Out) 구조를 따릅니다.
- 함수 호출이 중첩될수록 스택의 사용량이 증가합니다.
Stack Overflow
- 스택의 크기는 제한적이며, 너무 많은 함수 호출이나 무한 재귀로 인해 스택이 가득 차면 Stack Overflow라는 오류가 발생합니다.
응용 문제 2: 두 숫자의 2진수 XOR 계산
문제
스택을 사용하여 두 양의 정수를 2진수로 변환하고, 해당 2진수의 XOR 연산 결과를 출력하는 프로그램을 작성하시오.
- XOR 연산은 동일한 자리의 비트가 다르면 1, 같으면 0이 됩니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> stackA, stackB; // 두 숫자의 스택
int topA = -1, topB = -1;
// push 함수
void push(vector<int>& stack, int& top, int value) {
stack.push_back(value);
top++;
}
// pop 함수
int pop(vector<int>& stack, int& top) {
if (top >= 0) {
int value = stack[top];
stack.pop_back();
top--;
return value;
} else {
cout << "Stack Underflow" << endl;
return -1;
}
}
// 2진수 변환 함수
void convertToBinary(int n, vector<int>& stack, int& top) {
while (n > 0) {
push(stack, top, n % 2);
n /= 2;
}
}
// XOR 연산 함수
void printXOR(int num1, int num2) {
convertToBinary(num1, stackA, topA);
convertToBinary(num2, stackB, topB);
vector<int> binaryA, binaryB;
// 스택에서 값을 꺼내며 2진수 저장
while (topA >= 0) binaryA.push_back(pop(stackA, topA));
while (topB >= 0) binaryB.push_back(pop(stackB, topB));
// 두 2진수 크기를 동일하게 맞추기 위해 앞에 0 추가
int maxSize = max(binaryA.size(), binaryB.size());
while (binaryA.size() < maxSize) binaryA.insert(binaryA.begin(), 0);
while (binaryB.size() < maxSize) binaryB.insert(binaryB.begin(), 0);
// 원래 2진수 출력
cout << "Binary of " << num1 << ": ";
for (int bit : binaryA) cout << bit;
cout << endl;
cout << "Binary of " << num2 << ": ";
for (int bit : binaryB) cout << bit;
cout << endl;
// XOR 연산 결과 출력
cout << "XOR result: ";
for (int i = 0; i < maxSize; i++) {
cout << (binaryA[i] ^ binaryB[i]);
}
cout << endl;
}
int main() {
int num1, num2;
cout << "Enter two positive integers:" << endl;
cin >> num1 >> num2;
if (num1 <= 0 || num2 <= 0) {
cout << "Please enter positive integers!" << endl;
return 0;
}
printXOR(num1, num2);
return 0;
}
객체지향프로그래밍 3번
1. 후위 표기식 계산 과정 및 스택 상태 변화
주어진 후위 표기식: 8 2 3 ^ / 2 3 * + 5 1 * -
후위 표기식 계산 규칙
- 피연산자는 스택에 push한다.
- 연산자가 나오면 스택에서 필요한 만큼 값을 pop하여 연산을 수행하고, 결과를 다시 push한다.
- 최종 결과는 스택에 남아 있는 하나의 값이다.
과정 설명
스택의 상태 변화를 단계별로 그림과 함께 설명합니다:
단계현재 처리 항목스택 상태 (위에서 아래로)설명
| 1 | 8 | 8 | 피연산자이므로 스택에 push. |
| 2 | 2 | 2, 8 | 피연산자이므로 스택에 push. |
| 3 | 3 | 3, 2, 8 | 피연산자이므로 스택에 push. |
| 4 | ^ | 8, 2^3 = 8 | 3 ^ 2 = 8 계산 후 결과를 push. |
| 5 | / | 8 / 8 = 1 | 8 / 8 = 1 계산 후 결과를 push. |
| 6 | 2 | 2, 1 | 피연산자이므로 스택에 push. |
| 7 | 3 | 3, 2, 1 | 피연산자이므로 스택에 push. |
| 8 | * | 2 * 3 = 6, 1 | 2 * 3 = 6 계산 후 결과를 push. |
| 9 | + | 1 + 6 = 7 | 1 + 6 = 7 계산 후 결과를 push. |
| 10 | 5 | 5, 7 | 피연산자이므로 스택에 push. |
| 11 | 1 | 1, 5, 7 | 피연산자이므로 스택에 push. |
| 12 | * | 5 * 1 = 5, 7 | 5 * 1 = 5 계산 후 결과를 push. |
| 13 | - | 7 - 5 = 2 | 7 - 5 = 2 계산 후 결과를 push. |
최종 결과
스택에 남은 값: 2
응용 문제 1: 중위 표기식 → 후위 표기식 변환 및 계산
코드.
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <cmath>
using namespace std;
// 연산자 우선순위 반환 함수
int precedence(char op) {
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
// 중위 표기식을 후위 표기식으로 변환
string infixToPostfix(const string& infix) {
stack<char> operators;
string postfix;
for (char ch : infix) {
if (isdigit(ch)) {
postfix += ch; // 숫자는 바로 추가
} else if (ch == '(') {
operators.push(ch); // 여는 괄호는 스택에 push
} else if (ch == ')') {
// 닫는 괄호: 여는 괄호가 나올 때까지 연산자를 pop
while (!operators.empty() && operators.top() != '(') {
postfix += operators.top();
operators.pop();
}
operators.pop(); // 여는 괄호 pop
} else {
// 연산자는 우선순위에 따라 스택에 push
while (!operators.empty() && precedence(operators.top()) >= precedence(ch)) {
postfix += operators.top();
operators.pop();
}
operators.push(ch);
}
}
// 남은 연산자 pop
while (!operators.empty()) {
postfix += operators.top();
operators.pop();
}
return postfix;
}
// 후위 표기식을 계산
int evaluatePostfix(const string& postfix) {
stack<int> operands;
for (char ch : postfix) {
if (isdigit(ch)) {
operands.push(ch - '0'); // 숫자는 스택에 push
} else {
// 연산자를 만나면 피연산자 두 개를 pop
int b = operands.top();
operands.pop();
int a = operands.top();
operands.pop();
// 연산 수행
if (ch == '+') operands.push(a + b);
else if (ch == '-') operands.push(a - b);
else if (ch == '*') operands.push(a * b);
else if (ch == '/') operands.push(a / b);
else if (ch == '^') operands.push(pow(a, b));
}
}
return operands.top(); // 최종 결과 반환
}
int main() {
string infix;
cout << "Enter an infix expression (e.g., ((8/(2^3))+(2*3))-(5*1)): ";
cin >> infix;
string postfix = infixToPostfix(infix);
cout << "Postfix expression: " << postfix << endl;
int result = evaluatePostfix(postfix);
cout << "Result: " << result << endl;
return 0;
}
응용 문제 2: 새로운 연산자 @ 추가
코드
#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
// 후위 표기식을 계산 (새로운 연산자 @ 추가)
int evaluatePostfixWithCustomOperator(const string& postfix) {
stack<int> operands;
for (char ch : postfix) {
if (isdigit(ch)) {
operands.push(ch - '0'); // 숫자는 스택에 push
} else {
// 연산자를 만나면 피연산자 두 개를 pop
int b = operands.top();
operands.pop();
int a = operands.top();
operands.pop();
// 연산 수행
if (ch == '+') operands.push(a + b);
else if (ch == '-') operands.push(a - b);
else if (ch == '*') operands.push(a * b);
else if (ch == '/') operands.push(a / b);
else if (ch == '^') operands.push(pow(a, b));
else if (ch == '@') operands.push(pow(a + b, 2)); // 새로운 연산자
}
}
return operands.top(); // 최종 결과 반환
}
int main() {
string postfix;
cout << "Enter a postfix expression (e.g., 4 5 @ 2 +): ";
cin >> postfix;
int result = evaluatePostfixWithCustomOperator(postfix);
cout << "Result: " << result << endl;
return 0;
}
응용 문제 3: 스택 크기 제한
코드
#include <iostream>
#include <stack>
#include <stdexcept>
using namespace std;
class LimitedStack {
private:
stack<int> data;
int capacity;
public:
LimitedStack(int cap) : capacity(cap) {}
void push(int value) {
if (data.size() >= capacity) {
throw overflow_error("Stack Overflow: Maximum capacity reached!");
}
data.push(value);
}
int pop() {
if (data.empty()) {
throw underflow_error("Stack Underflow: No elements to pop!");
}
int value = data.top();
data.pop();
return value;
}
bool empty() {
return data.empty();
}
int size() {
return data.size();
}
};
// 후위 표기식을 계산 (스택 크기 제한 적용)
int evaluatePostfixWithLimitedStack(const string& postfix, int maxStackSize) {
LimitedStack operands(maxStackSize);
for (char ch : postfix) {
if (isdigit(ch)) {
operands.push(ch - '0'); // 숫자는 스택에 push
} else {
// 연산자를 만나면 피연산자 두 개를 pop
int b = operands.pop();
int a = operands.pop();
// 연산 수행
if (ch == '+') operands.push(a + b);
else if (ch == '-') operands.push(a - b);
else if (ch == '*') operands.push(a * b);
else if (ch == '/') operands.push(a / b);
else if (ch == '^') operands.push(pow(a, b));
}
}
return operands.pop(); // 최종 결과 반환
}
int main() {
string postfix;
cout << "Enter a postfix expression (e.g., 8 2 3 ^ / 2 3 * + 5 1 * -): ";
cin >> postfix;
int maxStackSize;
cout << "Enter maximum stack size: ";
cin >> maxStackSize;
try {
int result = evaluatePostfixWithLimitedStack(postfix, maxStackSize);
cout << "Result: " << result << endl;
} catch (const exception& e) {
cout << "Error: " << e.what() << endl;
}
return 0;
}
객체지향프로그래밍 4번
연산자 우선순위
- 괄호 () > 거듭제곱 ^ > 곱셈/나눗셈 *, / > 덧셈/뺄셈 +, -
- 결합 규칙:
- +, -, *, /: Left Associativity
- ^: Right Associativity
변환 결과
1. 1 + (2 + 3) - 4 * (5 + 6 * 7) / 9
후위 표기식:
1 2 3 + + 4 5 6 7 * + * 9 / -
2. (1 - 2 / 3 * (4 - 5 / 6)) / (7 - 8 - (9 - 10))
후위 표기식:
1 2 3 / 4 5 6 / - * - 7 8 - 9 10 - - /
3. A + B - (C - D * E / F) / G - (H + I)
후위 표기식:
A B + C D E * F / - G / - H I + -
4. A + B - C ^ D ^ E * F
후위 표기식:
A B + C D E ^ ^ F * -
5. A + (B - C) ^ (D ^ (E * F))
후위 표기식:
A B C - D E F * ^ ^ +
6. (A * (B + C - D / E) ^ F) - (G + H) * I
후위 표기식:
A B C + D E / - F ^ * G H + I * -
변환 과정 설명
변환 과정은 스택을 이용한 Shunting-yard 알고리즘을 기반으로 진행됩니다.
- 피연산자는 그대로 출력합니다.
- 연산자는 스택에 push하며, 스택 내 연산자와 우선순위를 비교해 적절히 pop하고 출력합니다.
- 여는 괄호 (는 스택에 push하며, 닫는 괄호 )가 나올 때까지 스택에서 pop하여 출력합니다.
- 우선순위와 결합 규칙에 따라 연산자의 처리 순서를 조정합니다.
응용 문제
새로운 연산자 @를 추가하여, (A @ B)는 (A + B)^2을 의미한다고 가정합니다.
중위 표기식 A @ (B + C) - D * E를 후위 표기식으로 변환하고 계산하는 프로그램을 작성합니다.
#include <iostream>
#include <stack>
#include <string>
#include <cmath>
using namespace std;
// 연산자 우선순위 반환 함수
int precedence(char op) {
if (op == '@') return 3; // @는 ^와 동일한 우선순위
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
// 중위 표기식을 후위 표기식으로 변환
string infixToPostfix(const string& infix) {
stack<char> operators;
string postfix;
for (char ch : infix) {
if (isalnum(ch)) {
postfix += ch; // 피연산자는 바로 추가
} else if (ch == '(') {
operators.push(ch); // 여는 괄호는 스택에 push
} else if (ch == ')') {
// 닫는 괄호: 여는 괄호가 나올 때까지 연산자를 pop
while (!operators.empty() && operators.top() != '(') {
postfix += operators.top();
operators.pop();
}
operators.pop(); // 여는 괄호 pop
} else {
// 연산자는 우선순위에 따라 스택에 push
while (!operators.empty() && precedence(operators.top()) >= precedence(ch)) {
postfix += operators.top();
operators.pop();
}
operators.push(ch);
}
}
// 남은 연산자 pop
while (!operators.empty()) {
postfix += operators.top();
operators.pop();
}
return postfix;
}
// 후위 표기식을 계산 (새로운 연산자 @ 포함)
int evaluatePostfix(const string& postfix) {
stack<int> operands;
for (char ch : postfix) {
if (isalnum(ch)) {
int value;
cout << "Enter value for " << ch << ": ";
cin >> value;
operands.push(value); // 피연산자 값을 입력받아 push
} else {
// 연산자를 만나면 피연산자 두 개를 pop
int b = operands.top();
operands.pop();
int a = operands.top();
operands.pop();
// 연산 수행
if (ch == '+') operands.push(a + b);
else if (ch == '-') operands.push(a - b);
else if (ch == '*') operands.push(a * b);
else if (ch == '/') operands.push(a / b);
else if (ch == '^') operands.push(pow(a, b));
else if (ch == '@') operands.push(pow(a + b, 2)); // @ 연산 처리
}
}
return operands.top(); // 최종 결과 반환
}
int main() {
string infix = "A@(B+C)-D*E"; // 중위 표기식
cout << "Infix Expression: " << infix << endl;
// 중위 표기식을 후위 표기식으로 변환
string postfix = infixToPostfix(infix);
cout << "Postfix Expression: " << postfix << endl;
// 후위 표기식 계산
int result = evaluatePostfix(postfix);
cout << "Result: " << result << endl;
return 0;
}
객체지향프로그래밍 5번
#include <iostream>
#include <stack>
#include <string>
#include <cctype> // for isalnum()
using namespace std;
// 후위 표기식을 중위 표기식으로 변환하는 함수
string postfixToInfix(const string& postfix) {
stack<string> st; // 중위 표기식을 저장할 스택
for (char ch : postfix) {
if (isalnum(ch)) {
// 피연산자라면 스택에 push
st.push(string(1, ch));
} else {
// 연산자라면, 스택에서 두 개의 피연산자를 pop
string operand2 = st.top(); st.pop();
string operand1 = st.top(); st.pop();
// 괄호를 추가하여 중위 표기식으로 결합
string expr = "(" + operand1 + " " + ch + " " + operand2 + ")";
st.push(expr);
}
}
// 스택에 남아 있는 최종 결과 반환
return st.top();
}
int main() {
// 테스트 입력 1
string postfix1 = "A B C + - D *";
cout << "Postfix: " << postfix1 << endl;
cout << "Infix: " << postfixToInfix(postfix1) << endl << endl;
// 테스트 입력 2
string postfix2 = "A B + C - D E *";
cout << "Postfix: " << postfix2 << endl;
cout << "Infix: " << postfixToInfix(postfix2) << endl;
return 0;
}
객체지향프로그래밍 6번
최단경로계산
#include <iostream>
#include <queue>
#include <vector>
#include <utility> // for pair
#include <cstring> // for memset
using namespace std;
// 이동 가능한 8개의 방향
const int dx[] = {1, 1, 2, 2, -1, -1, -2, -2};
const int dy[] = {2, -2, 1, -1, 2, -2, 1, -1};
// 체스판 크기
const int N = 8;
// 방문 여부 체크
bool visited[N][N];
// BFS 탐색 함수
int findShortestPath(pair<int, int> start, pair<int, int> target) {
memset(visited, false, sizeof(visited)); // 방문 배열 초기화
queue<pair<pair<int, int>, int>> q; // 위치와 이동 횟수를 저장
// 시작 위치 큐에 삽입
q.push({start, 0});
visited[start.first][start.second] = true;
while (!q.empty()) {
auto current = q.front();
q.pop();
int x = current.first.first;
int y = current.first.second;
int moves = current.second;
// 목표 위치 도달 시 이동 횟수 반환
if (x == target.first && y == target.second) {
return moves;
}
// 8방향으로 이동
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 유효한 위치인지 확인 (체스판 범위 내 + 미방문)
if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({{nx, ny}, moves + 1}); // 다음 위치와 이동 횟수 큐에 추가
}
}
}
return -1; // 목표 위치에 도달할 수 없는 경우
}
int main() {
// 체스판의 시작점과 목표점
pair<int, int> start = {5, 2};
pair<int, int> target = {2, 6};
int result = findShortestPath(start, target);
if (result != -1) {
cout << "최단 이동 횟수: " << result << endl;
} else {
cout << "목표 위치에 도달할 수 없습니다." << endl;
}
return 0;
}
응용문제 (킹 최단경로 찾기)
#include <iostream>
#include <queue>
#include <cstring> // for memset
using namespace std;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}; // 8방향 x
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1}; // 8방향 y
// BFS 함수
int findKingShortestPath(int N, pair<int, int> start, pair<int, int> target) {
bool visited[N][N];
memset(visited, false, sizeof(visited)); // 방문 여부 초기화
// 큐에 현재 위치와 이동 횟수를 삽입
queue<pair<pair<int, int>, int>> q;
q.push({start, 0});
visited[start.first][start.second] = true;
// BFS 탐색
while (!q.empty()) {
auto current = q.front();
q.pop();
int x = current.first.first;
int y = current.first.second;
int moves = current.second;
// 목표 위치에 도달하면 이동 횟수 반환
if (x == target.first && y == target.second) {
return moves;
}
// 8방향으로 이동
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 유효한 위치인지 확인 (체스판 범위 내 + 미방문)
if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({{nx, ny}, moves + 1}); // 다음 위치와 이동 횟수 큐에 추가
}
}
}
return -1; // 목표 위치에 도달할 수 없는 경우
}
int main() {
int N;
cout << "체스판 크기 N을 입력하세요 (2 ≤ N ≤ 10): ";
cin >> N;
pair<int, int> start, target;
cout << "현재 위치 (x1, y1)을 입력하세요: ";
cin >> start.first >> start.second;
cout << "목표 위치 (x2, y2)을 입력하세요: ";
cin >> target.first >> target.second;
int result = findKingShortestPath(N, start, target);
if (result != -1) {
cout << "최단 이동 횟수: " << result << endl;
} else {
cout << "도달할 수 없습니다." << endl;
}
return 0;
}
객체지향프로그래밍 7번
1. FIFO 큐 (Queue)
- 개념: FIFO(First In, First Out) 큐는 선입선출 방식으로 동작하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가게 됩니다.
- 특징:
- Enqueue: 큐의 뒤에 데이터를 추가합니다.
- Dequeue: 큐의 앞에서 데이터를 제거합니다.
- 큐는 한쪽 끝에서만 추가(enqueue)되고 다른 한쪽 끝에서만 제거(dequeue)됩니다.
- 사용 예:
- 프로세스 관리에서 작업 대기열을 관리할 때.
- 프린터 대기열: 먼저 인쇄 요청한 것부터 처리.
2. Deque (Double Ended Queue)
- 개념: Deque는 양쪽 끝에서 데이터를 삽입하고 제거할 수 있는 자료구조입니다. 양쪽 끝에서 모두 추가하고 제거할 수 있어 큐와 스택의 특징을 모두 가질 수 있습니다.
- 특징:
- Front와 Rear 양쪽에서 삽입과 삭제가 가능합니다.
- push_front(): 앞에 데이터를 추가.
- push_back(): 뒤에 데이터를 추가.
- pop_front(): 앞에서 데이터를 제거.
- pop_back(): 뒤에서 데이터를 제거.
- 사용 예:
- 슬라이딩 윈도우 알고리즘에서 사용.
- 웹 브라우저에서 "뒤로 가기", "앞으로 가기" 기능 구현.
3. 우선순위 큐 (Priority Queue)
- 개념: 우선순위 큐는 큐의 기본 개념을 따르면서도, 각 요소가 **우선순위(priority)**를 가집니다. 우선순위가 높은 요소가 먼저 나오며, 우선순위가 같을 경우 삽입 순서에 따라 처리됩니다.
- 특징:
- enqueue 시 우선순위에 따라 삽입된 데이터가 정렬됩니다.
- 우선순위 큐는 내부적으로 힙(Heap)을 사용하여 구현되는 경우가 많습니다. 따라서 삽입과 삭제가 O(log N) 시간 복잡도를 가집니다.
- 우선순위가 높은 데이터를 먼저 제거합니다.
- 사용 예:
- 스케줄러: CPU가 어떤 작업을 우선순위에 따라 먼저 처리해야 할 때.
- 다익스트라 알고리즘: 최단 경로를 계산할 때.
- .
- 특징FIFO 큐Deque우선순위 큐
삽입/삭제 위치 한쪽 끝에서 삽입, 다른 끝에서 삭제 양쪽 끝에서 삽입과 삭제 가능 우선순위에 따라 삽입, 우선순위가 높은 것부터 삭제 삽입 순서와 출력 순서 입력 순서대로 출력 입력 순서에 상관없이 양쪽 끝에서 처리 가능 우선순위가 높은 데이터부터 출력 예시 작업 대기열, 프린터 대기열 슬라이딩 윈도우 알고리즘, 브라우저 뒤/앞 버튼 작업 스케줄링, 다익스트라 알고리즘 시간 복잡도 O(1) (상수 시간) O(1) (상수 시간) O(log N) (삽입과 삭제에서 힙을 사용하기 때문)
객체지향프로그래밍 8번
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int dx[] = {0, 0, 1}; // 오른쪽, 왼쪽, 아래쪽
const int dy[] = {1, -1, 0}; // 오른쪽, 왼쪽, 아래쪽
int N, M;
int maze[100][100];
bool visited[100][100];
// BFS를 이용한 미로 찾기
int bfs() {
queue<pair<pair<int, int>, int>> q; // (x, y) 좌표와 경로 길이
// 상변에서 출발할 수 있는 모든 지점에서 시작
for (int i = 0; i < M; ++i) {
if (maze[0][i] == 1) { // 흰색 셀만 출발 가능
q.push({{0, i}, 1}); // 시작점과 경로 길이 1
visited[0][i] = true;
}
}
while (!q.empty()) {
auto current = q.front();
q.pop();
int x = current.first.first;
int y = current.first.second;
int dist = current.second;
// 하변에 도달하면 경로 길이를 리턴
if (x == N - 1) {
return dist;
}
// 3방향으로 이동 (오른쪽, 왼쪽, 아래쪽)
for (int i = 0; i < 3; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 유효한 범위 내에서, 방문하지 않은 흰색 셀로만 이동
if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({{nx, ny}, dist + 1});
}
}
}
return -1; // 하변에 도달할 수 없는 경우
}
int main() {
cin >> N >> M; // N: 미로의 세로 크기, M: 미로의 가로 크기
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> maze[i][j]; // 1: 흰색, 0: 검은색
}
}
memset(visited, false, sizeof(visited)); // 방문 여부 초기화
int result = bfs();
if (result != -1) {
cout << "가장 짧은 경로의 길이: " << result << endl;
} else {
cout << "하변에 도달할 수 없습니다." << endl;
}
return 0;
}
응용 문제 코드
이 문제는 BFS를 사용하여 미로를 탐색하는 방식입니다. 이 코드는 미로의 크기가 최대 1000x1000일 때도 효율적으로 동작하도록 최적화합니다. 또한, 각 위치의 중복 방문을 방지하여 더 빠른 경로를 찾을 수 있도록 합니다.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int dx[] = {0, 0, 1}; // 오른쪽, 왼쪽, 아래쪽
const int dy[] = {1, -1, 0}; // 오른쪽, 왼쪽, 아래쪽
int N, M;
int maze[1000][1000];
bool visited[1000][1000];
// BFS를 이용한 미로 찾기
int bfs() {
queue<pair<pair<int, int>, int>> q; // (x, y) 좌표와 경로 길이
// 상변에서 출발할 수 있는 모든 지점에서 시작
for (int i = 0; i < M; ++i) {
if (maze[0][i] == 1) { // 흰색 셀만 출발 가능
q.push({{0, i}, 1}); // 시작점과 경로 길이 1
visited[0][i] = true;
}
}
while (!q.empty()) {
auto current = q.front();
q.pop();
int x = current.first.first;
int y = current.first.second;
int dist = current.second;
// 하변에 도달하면 경로 길이를 리턴
if (x == N - 1) {
return dist;
}
// 3방향으로 이동 (오른쪽, 왼쪽, 아래쪽)
for (int i = 0; i < 3; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 유효한 범위 내에서, 방문하지 않은 흰색 셀로만 이동
if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({{nx, ny}, dist + 1});
}
}
}
return -1; // 하변에 도달할 수 없는 경우
}
int main() {
cin >> N >> M; // N: 미로의 세로 크기, M: 미로의 가로 크기
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> maze[i][j]; // 1: 흰색, 0: 검은색
}
}
memset(visited, false, sizeof(visited)); // 방문 여부 초기화
int result = bfs();
if (result != -1) {
cout << "가장 짧은 경로의 길이: " << result << endl;
} else {
cout << "하변에 도달할 수 없습니다." << endl;
}
return 0;
}반응형
'IT 프로그래밍 > 객체지향프로그래밍' 카테고리의 다른 글
| [오픈소스소프트웨어] 7.2 Linux 부팅 과정 (0) | 2024.10.12 |
|---|---|
| 객체지향프로그래밍 시험 예상 문제 코드 (0) | 2024.06.22 |
| 객체지향프로그래밍 7 과제 Food Monster (0) | 2024.06.21 |
| 객체지향프로그래밍 6 과제 (0) | 2024.06.21 |
| 객체지향프로그래밍 5 과제 (0) | 2024.06.21 |