오늘 학습 진행 내용
알고리즘 특강 - 4
시간 복잡도, 공간 복잡도
프로그램 수행 성능을 최악의 경우를 가정하여 정량화하는 것
코딩테스트 기준
첫 난이도 하 --> 일단 해결이 중요
중, 상 난이도 -> 수행 속도가 중요
코드가 정답인지 판단할 수 있는 테스트 케이스
Input 조절을 통해서 시스템 부하 성능 테스트 중요
알고리즘 유용한지 판단하기 위한 기준(시간 복잡도)
공간 복잡도는 시간 복잡도에 비해서는 중요성 낮은 편
시간복잡도는 꼭 최악의 경우를 기준으로 계산(프로그램 수행 시간)
시간 복잡도는 Big-O 표기법으로 표시 O(N^2) 이런 형태로
공간 복잡도는 N개의 입력이 주어지면 공간을 얼마나 쓰는지 나타내는 것
알고리즘의 성능 향상을 위해서 공간을 필수적으로 더 사용해야 한다면 주저 X
자료 구조
배열
링크드리스트
링크드리스트는 유동적으로 연결고리를 떼었다가 붙였다가 할 수있는 자료구조
링크드리스트는 원소의 삽입/삭제에 강점이 있는 자료 구조
링크드리스트 자료 구조 구현 예제 코드
#include<iostream>
#include<string>
using namespace std;
//노드를 클래스로 정의 (data(노드 값),next(포인터) 정의 필수)
class Node{
private:
string data;
Node* next; //일단은 원시 포인터로 러프하게
public:
Node(string data){ //data = "흑연"
this-> data= data;
this->next =nullptr; //초기에는 다음 노드가 없으므로 nullptr 초기화
}
//LinkedList 클래스에서 Node의 private 멤버에 접근 가능
friend class LinkedList;
};
//링크드리스트 자료 구조를 크래릇로 정의해보기(head 정의 필수)
class LinkedList {
private:
Node* head;
int nodeCount; //노드 개수를 추적하기 위한 변수
public:
LinkedList(string value){
this->head = new Node(value); //head에 시작하는 Node를 연결
this->nodeCount = 1;
}
//LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결
void append(string value){
Node* curr =this->head;
while(curr->next != nullptr){ //curr의 다음이 끝에 갈 때까지 이동
curr = curr->next;
}
//while 루프 탈출하면
//curr->next == nullptr
cout<<"curr->next: "<< curr->next<<endl;
curr->next =new Node(value);
this->nodeCount++;
}
//원하는 위치의 노드를 찾아내는 getNode 함수작성해보기
Node* getNode(int index){
//nodeCount를 근거로 index가 유효한지 판단
if(index<0|| index>= nodeCount){
throw std::out_of_range("유효하지 않은 인덱스!");
}
Node* node = this->head; //링크드리스트의 Head를 처음 노드로 지정
for(int i=0; i<index; i++){
node = node->next; //원하는 위치에 당도할 때까지 다음 노드로 이동
}
return node;
}
void addNode(int index, string value){
Node& newNode = new Node(value); //일단 새로운 값을 기준으로 새노드를 생성
if(index == 0){ //0번째 추가를 하고 싶다면
newNode->next=this->head; //원래 Head였던 노드를 새 노드의 next로 지정
this->head = newNode; //Head를 새 노드로 변경
this->nodeCount++;
return;
}
//추가하고 싶은 idnex의 이전 노드 정보를 갖고 옴
Node* node = this->getNode(index-1);
//1, 이전 노드의 포인터를 next_node로 임시 저장
Node* nextNode = node->next;
//2. 이전 노드의 포인터를 지정
node->next = newNode;
//3. 새로 삽입한 노드의 포인터를 next_node로 지정
newNode->next = nextNode;
this->nodecount++;
}
}스택
LIFO(Last In First Out)후입선출의 성결을 가진 자료구조를 스택
역순의 성질이 필요한 곳에서 사용
스택에서 사용할 수 있는 기능
탑 : 스택의 Top(맨 위) 데이터를 보는 것
푸시 : 스택에 원소를 삽입하는 행위, 원소는 TOp에 들어감
팝 : 스택의 Top의 원소를 가져오는 행위(가져온 원소는 Stack에서 사라짐)
스택 자료 구조 구현 예제 코드
#include <iostream>
#include <vector>
#include <stdexcept>
class Stack {
private:
std::vector<int> stack; //벡터를 이용해서 관리
public:
Stack() = default; //기본 생성자 자동 생성
//스택의 맨 위 데이터를 반환
int top(){
if(stack.empty()){
throw std::out_of_range("스택이 비어있어요!");
}
return stack.back();
}
//스택의 맨 위 데이터를 반환
void push(int value){
stack.push_back(value);
}
// 스택에 데이터를 추가
void pop(){
if(stack.empty()){
throw std::underflow_error("스택이 비어서 꺼낼게 없어요!");
}
stack.pop_back();
}
};
int main(){
Stack s;
try{
s.push(10);
s.push(20);
s.push(30);
std::cout<<"현재 톱 원소: "<<s.top()<<std::endl;
s.pop();
std::cout<<"현재 톱 원소: "<<s.top()<<std::endl;
s.pop();
s.pop();
s.pop(); //예외 발생: 스택이 비어 있음.
}catch(const std::exception& e){
std::cerr<<e.what()<<std::endl;
}
return 0;
}큐
큐는 FIFO(First In First Out)의 선입선출 성격을 가진 자료 구조
큐에서 사용할 수 있는 기능
프론트 : 큐의 Front(맨 앞) 데이터를 갖고 오는 것
백 : 큐의 End(맨 뒤) 데이터를 갖고 오는 것
푸시 : 큐에 원소를 삽입하는 행위, 원소는 End에 들어감
팝 : 큐에서 원소를 제거하는 행위, FIFO 자료구조, Front에 위치한 원소를 제거
큐 자료 구조 구현 예제 코드
#include <iostream>
#include <vector>
#include <stdexcept>
class Queue {
private:
std::vector<int> queue;
public:
Queue() =default;
//큐의 첫 번째 원소 반환
int front() const {
if(queue.empty()){
throw std::out_of_range("큐가 비어있어요!");
}
return queue.front();
}
//큐의 마지막 원소 반환
int back() const {
if(queue.empty()){
throw std::out_of_range("큐가 비어있어요!");
}
return queue.back();
}
//큐에 원소 추가
void push(int value){
queue.push_back(value);
}
//큐의 첫 번째 원소 제거
void pop(){
if(queue.empty()){
throw std::underflow_error("큐가 비어서 꺼낼게 없어요!");
}
queue.erase(queue.begin());
}
};
int main(){
Queue q;
q.push(10);
q.push(20);
q.push(30);
std::cout<<"현재 프론트 원소: "<<q.front()<<std::endl;
std::cout<<"현재 백 원소: "<<q.back()<<std::endl;
q.pop();
std::cout<<"현재 프론트 원소: "<<q.front()<<std::endl;
q.pop();
q.pop();
}프로그래머스 문자열의 뒤의 n글자
문제 설명
문자열 my_string과 정수 n이 매개변수로 주어질 때, my_string의 뒤의 n글자로 이루어진 문자열을 return 하는 solution 함수를 작성해 주세요.
제한사항
my_string은 숫자와 알파벳으로 이루어져 있습니다.
1 ≤ my_string의 길이 ≤ 1,000
1 ≤ n ≤ my_string의 길이
입출력 예
my_string n result
"ProgrammerS123" 11 "grammerS123"
"He110W0r1d" 5 "W0r1d"
통과 코드
#include <string>
#include <vector>
using namespace std;
string solution(string my_string, int n) {
string answer = "";
int len = my_string.length();
answer= my_string.substr(len-n,n);
return answer;
}
**다른 사람 풀이**
#include <string>
#include <vector>
using namespace std;
string solution(string my_string, int n) {
string answer = "";
answer = my_string.substr(my_string.length() - n);
return answer;
}
프로그래머스 접미사 배열
문제 설명
어떤 문자열에 대해서 접미사는 특정 인덱스부터 시작하는 문자열을 의미합니다. 예를 들어, "banana"의 모든 접미사는 "banana", "anana", "nana", "ana", "na", "a"입니다.
문자열 my_string이 매개변수로 주어질 때, my_string의 모든 접미사를 사전순으로 정렬한 문자열 배열을 return 하는 solution 함수를 작성해 주세요.
제한사항
my_string은 알파벳 소문자로만 이루어져 있습니다.
1 ≤ my_string의 길이 ≤ 100
입출력 예
my_string result
"banana" ["a", "ana", "anana", "banana", "na", "nana"]
"programmers" ["ammers", "ers", "grammers", "mers", "mmers", "ogrammers", "programmers", "rammers", "rogrammers", "rs", "s"]
통과 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> solution(string my_string) {
vector<string> answer;
for(int i=0; i<my_string.length(); i++){
string temp = my_string.substr(i,my_string.length());
answer.push_back(temp);
}
sort(answer.begin(),answer.end());
return answer;
}다른 사람 풀이
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> solution(string my_string) {
vector<string> answer;
for (int i = 0; i < my_string.length(); i++)
answer.push_back(my_string.substr(i));
sort(answer.begin(), answer.end());
return answer;
}[4번 과제] C++ Summary - 연금술 공방 관리 시스템 구현
실습 코드(구현중)
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
// PotionRecipe 클래스: 재료 목록을 vector<string>으로 변경
class PotionRecipe {
public:
std::string potionName;
std::vector<std::string> ingredients; // 단일 재료에서 재료 '목록'으로 변경
// 생성자: 재료 목록을 받아 초기화하도록 수정
PotionRecipe() {};
PotionRecipe(const std::string& name, const std::vector<std::string>& ingredients)
: potionName(name), ingredients(ingredients) {
}
};
class RecipeManager {
private:
std::vector<PotionRecipe> recipes;
public:
RecipeManager() {}
PotionRecipe* addRecipe(const std::string& name, const std::vector<std::string>& ingredients) {
PotionRecipe newRecipe(name, ingredients);
recipes.push_back(newRecipe);
std::cout << ">> 새로운 레시피 '" << name << "'이(가) 추가되었습니다." << std::endl;
return &newRecipe;
}
PotionRecipe* findRecipeByName(const std::string& name) {
for (size_t i = 0; i < recipes.size(); ++i) {
if (recipes[i].potionName == name) {
return &recipes[i];
}
}
return nullptr; // 찾지 못한 경우 nullptr 반환
}
std::vector<PotionRecipe> findRecipesByIngredient(const std::string& ingredient) {
std::vector<PotionRecipe> result;
for(const auto& recipe: recipes){
if (std::find(recipe.ingredients.begin(), recipe.ingredients.end(), ingredient) != recipe.ingredients.end()) {
result.push_back(recipe);
}
}
return result;
}
const std::vector<PotionRecipe>& getAllRecipes() const {
return recipes;
}
};
class StockManager {
private:
std::map<std::string, int> potionStock;
const int MAX_STOCK = 3;
public:
StockManager() {};
void initializeStock(std::string potionName) {
potionStock[potionName] = MAX_STOCK;
};
bool dispensePotion(std::string potionName) {
if (potionStock.find(potionName) != potionStock.end()) {
if (potionStock[potionName] > 0) {
potionStock[potionName] -= 1;
return true;
}
else {
potionStock[potionName] = 0;
return false;
}
}
else {
std::cout << "존재하지 않는 포션입니다!" << std::endl;
return false;
}
}
void returnPotion(std::string potionName) {
if (potionStock.find(potionName) != potionStock.end()) {
if (potionStock[potionName] < 3) {
potionStock[potionName] += 1;
}
else {
potionStock[potionName] = 3;
}
}
}
int getStock(std::string potionName) const {
auto it = potionStock.find(potionName);
if (potionStock.find(potionName) != potionStock.end()) {
return it->second;
}
else {
return 0;
}
}
};
// AlchemyWorkshop 클래스: 레시피 목록을 관리
class AlchemyWorkshop {
private:
RecipeManager recipeManager;
StockManager stockManager;
public:
// addRecipe 메서드: 재료 목록(vector)을 매개변수로 받도록 수정
void addRecipe(const std::string& name, const std::vector<std::string>& ingredients) {
recipeManager.addRecipe(name, ingredients);
stockManager.initializeStock(name);
}
// 모든 레시피 출력 메서드
void displayAllRecipes() const {
std::vector<PotionRecipe> recipes = recipeManager.getAllRecipes();
if (recipes.empty()) {
std::cout << "아직 등록된 레시피가 없습니다." << std::endl;
return;
}
std::cout << "\n--- [ 전체 레시피 목록 ] ---" << std::endl;
for (size_t i = 0; i < recipes.size(); ++i) {
;
std::cout << "- 물약 이름: " << recipes[i].potionName << ", 현재 재고 : ("<< stockManager.getStock(recipes[i].potionName) <<")" << std::endl;
std::cout << " > 필요 재료: ";
// 재료 목록을 순회하며 출력
for (size_t j = 0; j < recipes[i].ingredients.size(); ++j) {
std::cout << recipes[i].ingredients[j];
// 마지막 재료가 아니면 쉼표로 구분
if (j < recipes[i].ingredients.size() - 1) {
std::cout << ", ";
}
}
std::cout << std::endl;
}
std::cout << "---------------------------\n";
}
//검색 메서드
PotionRecipe searchRecipeName(const std::string& name) {
PotionRecipe* result =recipeManager.findRecipeByName(name);
if (result == nullptr) {
std::cout << "조회 결과가 없습니다." << std::endl;
// 실패 시 기본 생성자로 초기화된 객체 반환
return PotionRecipe();
}
std::cout << "검색 결과 : " << std::endl;;
std::cout << "- 물약 이름: " << result->potionName << ", 현재 재고 : (" << stockManager.getStock(result->potionName) << ")" << std::endl;
std::cout << " > 필요 재료: ";
for (size_t j = 0; j < result->ingredients.size(); ++j) {
std::cout << result->ingredients[j];
if (j < result->ingredients.size() - 1) {
std::cout << ", ";
}
}
std::cout << std::endl;
return *result;
}
std::vector<PotionRecipe> searchRecipeByIngredient(std::string ingredient) {
std::vector<PotionRecipe>result = recipeManager.findRecipesByIngredient(ingredient);
std::cout << "검색 결과 : " << std::endl;
if (!result.empty()) {
for (size_t i = 0; i < result.size(); ++i) {
std::cout << "- 물약 이름: " << result[i].potionName << ", 현재 재고 : (" << stockManager.getStock(result[i].potionName) << ")" << std::endl;
std::cout << " > 필요 재료: ";
for (size_t j = 0; j < result[i].ingredients.size(); ++j) {
std::cout << result[i].ingredients[j];
if (j < result[i].ingredients.size() - 1) {
std::cout << ", ";
}
}
std::cout << std::endl;
}
}
else {
std::cout << "조회 결과가 없습니다." << std::endl;
}
return result;
}
};
//모험가 클래스 : 간이 물약 인벤토리 포함
class Adventurer {
private:
std::map<std::string, int> PotionInvetory;
std::string name;
public:
Adventurer(std::string name) :name(name) {};
void addPotion(std::string potionName) {
PotionInvetory[potionName] += 1;
}
void consumePotion(std::string potionName) {
auto it = PotionInvetory.find(potionName);
if (it != PotionInvetory.end() && it->second > 0) {
it->second -= 1;
std::cout << name << "이(가) " << potionName << "을(를) 사용했습니다." << std::endl;
}
else {
std::cout << potionName << "이(가) 인벤토리에 없습니다!" << std::endl;
std::cout << "연금술 공방에 방문해서 물약을 받으십시오!" << std::endl;
}
};
void returnPotionToShop(std::string potionName) {
auto it = PotionInvetory.find(potionName);
if (it != PotionInvetory.end() && it->second > 0) {
PotionInvetory[potionName] -= 1;
std::cout<< name << "이(가) " << potionName << "을(를) 연금술 공방에 반환했습니다." << std::endl;
}
else {
std::cout << potionName << "이(가) 인벤토리에 없습니다!" << std::endl;
}
};
void displayInventory() const {
std::cout << "\n--- " << name << "의 물약 인벤토리 ---" << std::endl;
if (PotionInvetory.empty()) {
std::cout << "인벤토리가 비어 있습니다." << std::endl;
}
else {
for (const auto& item : PotionInvetory) {
std::cout << "- " << item.first << ": " << item.second << "개" << std::endl;
}
}
std::cout << "---------------------------\n";
};
std::string getName() const {
return name;
}
};
int main() {
AlchemyWorkshop myWorkshop;
myWorkshop.addRecipe("Minor Health Potion", {
"Red Herb",
"Water Bottle"
});
myWorkshop.addRecipe("Minor Mana Potion", {
"Blue Herb",
"Water Bottle"
});
myWorkshop.addRecipe("Stamina Potion", {
"Green Herb",
"Water Bottle"
});
while (true) {
std::cout << "⚗️ 연금술 공방 관리 시스템" << std::endl;
std::cout << "1. 레시피 추가" << std::endl;
std::cout << "2. 모든 레시피 출력" << std::endl;
std::cout << "3. 물약이름으로 검색" << std::endl;
std::cout << "4.재료 이름으로 검색" << std::endl;
std::cout << "5. 모험가 방문 이벤트" << std::endl;
std::cout << "6. 종료" << std::endl;
std::cout << "선택: ";
int choice;
std::cin >> choice;
if (std::cin.fail()) {
std::cout << "잘못된 입력입니다. 숫자를 입력해주세요." << std::endl;
std::cin.clear();
std::cin.ignore(10000, '\n');
continue;
}
if (choice == 1) {
std::string name;
std::cout << "물약 이름: ";
std::cin.ignore(10000, '\n');
std::getline(std::cin, name);
// 여러 재료를 입력받기 위한 로직
std::vector<std::string> ingredients_input;
std::string ingredient;
std::cout << "필요한 재료들을 입력하세요. (입력 완료 시 '끝' 입력)" << std::endl;
while (true) {
std::cout << "재료 입력: ";
std::getline(std::cin, ingredient);
// 사용자가 '끝'을 입력하면 재료 입력 종료
if (ingredient == "끝") {
break;
}
ingredients_input.push_back(ingredient);
}
// 입력받은 재료가 하나 이상 있을 때만 레시피 추가
if (!ingredients_input.empty()) {
myWorkshop.addRecipe(name, ingredients_input);
}
else {
std::cout << ">> 재료가 입력되지 않아 레시피 추가를 취소합니다." << std::endl;
}
}
else if (choice == 2) {
myWorkshop.displayAllRecipes();
}
else if (choice == 3) {
std::cout << "검색어를 입력해주세요 : " << std::endl;
std::string searchKeyword;
std::cout << "물약 이름: ";
std::cin.ignore(10000, '\n');
std::getline(std::cin, searchKeyword);
PotionRecipe result = myWorkshop.searchRecipeName(searchKeyword);
std::cout << result.potionName << std::endl;
}
else if (choice == 4) {
std::cout << "검색어를 입력해주세요 : " << std::endl;
std::string searchKeyword;
std::cout << "재료 이름: ";
std::cin.ignore(10000, '\n');
std::getline(std::cin, searchKeyword);
myWorkshop.searchRecipeByIngredient(searchKeyword);
}
else if (choice == 5) {
Adventurer adventurer("홍길동");
std::cout << "공방에 모함가 " << adventurer.getName()<<"가 방문했습니다." << std::endl;
adventurer.displayInventory();
std::cout << "모험가가 어떤 행동을 할지 선택해주세요" << std::endl;
int ad_choice;
std::cin >> ad_choice;
if (std::cin.fail()) {
std::cout << "잘못된 입력입니다. 숫자를 입력해주세요." << std::endl;
std::cin.clear();
std::cin.ignore(10000, '\n');
continue;
}
if (ad_choice == 1) {
std::cout << "모험가가 물약을 받아갑니다";
myWorkshop.displayAllRecipes();
std::cout << "받아갈 물약의 이름을 입력하세요 : ";
std::string potionName;
std::cin.ignore(10000, '\n');
std::getline(std::cin, potionName);
/* myWorkshop.dispensePotion(potionName);
if(dispensePotion)*/
adventurer.addPotion(potionName);
}
if (ad_choice == 2) {
std::cout << "모험가가 물약을 반납합니다";
}
else if (ad_choice == 3) {
std::cout << "모험가가 물약을 마십니다" << std::endl;
}
else if (ad_choice == 0) {
std::cout << "모험가가 떠납니다..." << std::endl;
break;
}
else {
std::cout << "잘못된 선택입니다. 다시 시도하세요." << std::endl;
}
}
return 0;
}
개발합시다!