인사
안녕하세요.
오늘은 이전에 올렸던 C++ 학습일지 두 번째 글의 연장선으로, 큐와 스택의 개념 차이와 문자열 처리에 대해 배운 내용을 공유하려고 합니다. 실습과 공부를 병행하면서 새롭게 느꼈던 점들도 함께 정리해보았습니다.
큐 (Queue)
알고리즘을 공부하다 보면 큐와 스택 개념을 자연스럽게 접하게 됩니다.
저는 자바스크립트에서 동기·비동기 개념을 공부하던 중 처음 큐를 접했고, 이후 C++ 알고리즘 문제를 풀면서 다시 마주하게 되었습니다.
#include <stdio.h>
#include <queue>
void InputArr(int n, int** arr) {
int i;
for ( i = 0; i < n - 1; i++ ) {
arr[i] = new int[2];
scanf("%d %d", &arr[i][0], &arr[i][1]);
}
}
void DeleteArr(int n, int** arr) {
int i;
for (i = 0; i < n - 1; i++) {
delete[] arr[i];
}
delete[] arr;
}
void MakeMatrix(int n, int** arr, int** matrix, int* cnt) {
// 매트릭스 초기화 및 cnt 초기값 설정
int i;
for (i = 1; i < n + 1; i++) {
matrix[i] = new int [ n ];
cnt[i] = 0;
}
// 매트릭스 채우기
for (i = 0; i < n - 1; i++) {
int a = arr[i][0], b = arr[i][1];
matrix[a][cnt[a]] = b;
cnt[a] += 1;
}
}
void DeleteMatrix(int n, int** matrix, int* cnt) {
int i;
for (i = 1; i < n + 1; i++) {
delete[] matrix[i];
}
delete[] matrix;
delete[] cnt;
}
void BFS(int n, int** matrix, int* cnt, int* answers) {
// answer을 위한 리스트
int j = 0;
// 초기 설정
std::queue<int> que;
int* checks = new int [ n + 1 ];
// 초기값
int i, init = 1;
for (i = 1; i < n + 1; i++) {
if (i != init) checks[i] = 0;
else checks[i] = 1;
}
answers[j] = init;
j++;
que.push(init);
while (!que.empty()) {
int node = que.front();
que.pop();
int que_n = cnt[node];
for (i = 0; i < que_n; i++) {
int new_node = matrix[node][i];
if (checks[new_node] == 0) {
answers[j] = new_node;
j++;
checks[new_node] = 1;
que.push(new_node);
}
}
}
delete[] checks;
}
int main(void) {
// n의 값
int n;
scanf("%d", &n);
// 배열
int** arr = new int* [n-1];
InputArr(n, arr);
// 매트릭스 제작
int** matrix = new int* [ n + 1 ];
int* cnt = new int[n+1];
MakeMatrix(n, arr, matrix, cnt);
// BFS탐색
int* answers = new int[n];
BFS(n, matrix, cnt, answers);
// 정답
int i;
for (i = 0; i < n; i++) {
printf("%d ", answers[i]);
}
// 배열 삭제
DeleteArr(n, arr);
// 매트릭스 삭제
DeleteMatrix(n, matrix, cnt);
// 정답 삭제
delete[] answers;
return 0;
}
import sys
from collections import deque
class BFSclass():
def __init__(self, n, arr):
self.__n = n
self.__arr = arr
def MakeMatrix(self):
matrix = [ [] for _ in range(self.__n + 1) ]
for arr in self.__arr:
a, b = arr
matrix[a].append(b)
return matrix
def BFS(self, matrix):
# 값
init = 1
answers = []
# 초기 설정
que = deque([])
checks = [False] * (self.__n + 1)
# 초기값
que.append(init)
checks[init] = True
answers.append(init)
while que:
node = que.popleft()
for new_node in matrix[node]:
if not checks[new_node]:
checks[new_node] = True
answers.append(new_node)
que.append(new_node)
return answers
def FinalFunc(self):
# 매트릭스 만들기
matrix = self.MakeMatrix()
# BFS 탐색
return self.BFS(matrix)
# 입력
input = sys.stdin.readline
# n의값
n = int(input())
# 배열의 값
arr = []
for _ in range(n - 1):
arr.append(list(map(int, input().split())))
# 정답
b = BFSclass(n, arr)
answers = b.FinalFunc()
# 출력
print(" ".join(map(str, answers)))
📌 주요 차이점 (C++ vs Python)
-
데이터 제거 방식:
C++에서는 queue에서 데이터를 가져올 때 .pop()을 명시적으로 호출해야 제거됩니다. 반면, Python의 deque에서는 popleft()가 데이터를 가져오면서 자동으로 제거됩니다.
-
타입 지정 필요성:
C++에서는 큐 선언 시 타입을 명시해야 합니다 (std::queue<int> 등). Python은 동적 타이핑 언어라 따로 지정할 필요가 없습니다.
-
std:: 사용:
std::는 C++의 표준 라이브러리에 있는 함수를 사용하겠다는 의미입니다. 예: std::queue, std::string, std::cin 등.
스택 (Stack)
스택도 큐와 유사하게 데이터를 저장하고 제거하는 자료구조지만, 가장 마지막에 추가된 데이터가 가장 먼저 제거되는 후입선출(LIFO) 구조입니다. 웹 게시물이나 브라우저의 뒤로가기 기능 등을 예로 들 수 있습니다.
#include <stdio.h>
#include <stack>
#include <string>
#include <iostream>
void InputString(int n, std::stack<std::string>& stk) {
int i;
for (i = 0; i < n; i++) {
std::string title;
getline(std::cin, title);
stk.push(title);
}
}
void Answer(int n, std::stack<std::string>& stk) {
int i;
for (i = 0; i < n; i++) {
std::string title = stk.top();
stk.pop();
printf("%s\n", title.c_str());
}
}
int main(void) {
// n의 값
int n;
scanf("%d", &n);
getchar();
// 문자열 넣기
std::stack<std::string> stk;
InputString(n, stk);
// 정답
Answer(n, stk);
return 0;
}
핵심 포인트
-
stack.top()으로 가장 위의 데이터를 확인하고,
-
stack.pop()으로 해당 데이터를 제거합니다.
-
마찬가지로 타입 지정이 필요하고, 문자열 처리를 위해 <string>과 <iostream> 모듈을 함께 사용합니다.
문자열
문자열은 C++에서 특히 신경 써야 할 부분 중 하나입니다.
다른 언어들과 비교했을 때, 문자열을 단순한 데이터가 아니라 문자 배열로 처리하는 특성이 있어서 크기나 메모리 할당을 고려해야 할 경우가 많습니다.
#include <stdio.h>
#include <string>
#include <iostream>
#include <sstream>
#define BUFF_SIZE 1000
void Answer(int* j,std::string& data, int* answers) {
// 문자열 읽기
std::istringstream iss(data.c_str());
int value;
while (iss >> value) {
answers[(*j)++] = value;
}
}
void PrintAnswer(int* j, int* answers) {
int i;
for (i = 0; i < *j; i++) {
printf("%d", answers[i]);
if (i + 1 < *j ) {
printf("\n");
}
}
}
int main(void) {
// 문자 지정
std::string data;
getline(std::cin, data);
// 문자열 에서 빈칸은 지우기
int j = 0;
int* answers = new int [BUFF_SIZE];
Answer(&j, data, answers);
// 정답
PrintAnswer(&j, answers);
delete[] answers;
return 0;
}
package main
import (
"bufio"
"fmt"
"log"
"os"
"strconv"
"strings"
)
func Answer(line *string, answer *[]int) {
var (
stringList []string = strings.Fields(*line)
str_len int = len(stringList)
number int
err error
)
for i := 0; i < str_len; i++ {
string_target := stringList[i]
if number, err = strconv.Atoi(string_target); err == nil {
*answer = append(*answer, number)
} else {
log.Println(err)
return
}
}
}
func main() {
// 문자를 받아옴
reader := bufio.NewReader(os.Stdin)
line, _ := reader.ReadString('\n')
var (
answer []int
)
Answer(&line, &answer)
n := len(answer)
for i := 0; i < n; i++ {
fmt.Printf("%d\n", answer[i])
}
}
주요 학습 포인트
-
문자열 입력은 std::getline(std::cin, data); 방식 사용
-
문자열에서 정수를 추출할 때는 std::istringstream을 사용하여 파싱
-
배열을 사용할 경우에는 메모리 할당 및 해제에 주의해야 함
Go 언어 역시 문자열을 공백으로 나누어 처리할 수 있고, 정수로 변환하는 로직도 간단하지만, C++은 메모리와 타입에 좀 더 직접적으로 개입해야 한다는 차이점이 있습니다.
마무리
지금까지 큐, 스택, 그리고 문자열에 대한 C++의 사용법을 Python, Go와 비교해 보며 학습한 내용을 정리해봤습니다.
C++은 다른 언어에 비해 메모리를 직접 다루는 점이 다소 생소할 수 있지만, 오히려 덕분에 디버깅이 명확해지고, 메모리 누수를 방지하는 습관도 길러질 수 있다는 장점이 있다고 느꼈습니다.
앞으로는
-
vector 모듈 심화
-
구조체 응용
-
동적 프로그래밍
-
백준 문제 풀이
등을 통해 C++ 실력을 더 탄탄히 다질 계획입니다.
함께 공부하시는 분들도, 언제나처럼 화이팅입니다!
