참고도서 : 파이썬 알고리즘 인터뷰 . 박상길 . 책만 . 2020
참고도서에서 언급하는 알고리즘 주제를 참고하여 C++로 풀어보는 것을 목표로 합니다.
알고리즘을 공부하면서도 소프트웨어적 설계를 추가합니다. 답을 내는 코드를 짜는게 아니라 각각이 모듈이 되어 서로 맞물려 동작하는 코드를 짜는 것을 목표로합니다.
참고로 상위 레벨의 코드를 볼 수록
using namespace std; 라는 코드가 보이지 않아, 없이 진행합니다.
문자열 뒤집기
유사문제로는 아래 문제가 있으며, 이는 마지막에 풀어보도록 하겠습니다.
9093번: 단어 뒤집기
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는
www.acmicpc.net
문제
문자열을 뒤집는 함수를 작성하고, 매개변수는 string이 아니라 vector입니다. 이 함수는 반환값이 없습니다.
우선 뼈대부터 만들어봅시다.
이제 이정도는 손수 짤 수 있어야합니다.
#include <iostream>
#include <vector>
void reverse(std::vector<char> &v) {
}
int main() {
std::vector<char> v;
v.push_back('a');
v.push_back('b');
v.push_back('c');
v.push_back('d');
reverse(v);
for (auto i : v) {
std::cout << i;
}
}참조매개변수를 전해줌으로써 함수에서 값을 변경한 것이 적용되게 합니다.
현재 제 머리속을 지나는 방법은 그냥 벡터를 하나 만들고, 벡터를 돌면서 뒤집어서 저장하게 하면 되지 않을까 생각하지만
문제는 reverse 함수의 반환값이 void라는 점입니다.
그렇기 때문에 새로운 변수를 선언한다거나의 방법은 사용하지 말고 진행해봅시다.
여기서 가장 많이 하는 실수가 바로 이겁니다.
1과 마지막 자리를 바꾸면 되는거아님? 그러면 그냥 for문으로 vector의 사이즈만큼 돌면서 끝과 앞을 바꾸면 되겠네?
여기에는 가장 큰 함정이 있습니다. 코드를 보시겠습니다.
void reverse(std::vector<char> &v) {
for (int i = 0; i < v.size(); i++) {
v[i] = v[v.size() - i - 1];
}
}이 방법이겠죠?
이거 틀린 방법입니다.
abcd를 입력하고 결과를 한 번 볼까요?
dccd 라는 결과가 나왔습니다. 왜 이런값이 나올까요?
v[0] = v[끝] 이라고 합시다
뭐 시간이 지나서
v[끝] = v[0] 이라는 값이 들어가는 경우에 어떻게 될까요?
v[0] = v[끝] = v[0]
v[0] 에는 v[끝]이 들어가면서 v[0]은 값을 잃어버립니다.
그러니 v[끝] = v[0] 이라고 하면 결국 v[끝] = v[끝]을 한 것과 다르지 않습니다.
그러므로 우리는 temp라는 개념을 알아야합니다.
temp란? temporary의 약자로 임시로 값을 보관한다는 의미입니다.
그리고 여기서 값을 바꾼다는 의미는 스왑(swap)이라고 합니다.
다음처럼 가장 유명한 방법입니다.
void reverse(std::vector<char> &v) {
char temp ;
for (int i = 0; i < v.size(); i++) {
temp = v[i];
v[i] = v[v.size() - i - 1];
v[v.size() - i - 1] = temp;
}
}그러나 위 방법도 문제가 있습니다. 결과를 보시죠.
무엇이 문제일까요?
for문을 끝까지 돌리면
abcd -> dbca -> dcba -> dbca -> abcd 가 됩니다.
그러므로 for문은 반만 돌려야합니다.
void reverse(std::vector<char> &v) {
char temp ;
for (int i = 0; i < v.size()/2; i++) {
temp = v[i];
v[i] = v[v.size() - i - 1];
v[v.size() - i - 1] = temp;
}
}딱히 어려운게 없었습니다.
하지만 이 귀찮음을 한 방에 날려줄 알고리즘이 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<char> v;
v.push_back('a');
v.push_back('b');
v.push_back('c');
v.push_back('d');
reverse(v.begin(), v.end());
for (auto i : v) {
std::cout << i;
}
}기본적으로 제공되는 알고리즘 모듈을 include하여 reverse라는 함수를 사용하면 그만이기 때문이죠..
하지만 최소한 reverse라는 함수가 어떻게 돌아갈지 생각할 수 있어야 합니다.
그리고 reverse 알고리즘 모듈을 사용하는 것이 당연한 말이겠지만 더 빠릅니다.
이걸 만든사람들이 reverse를 사용하기 위해 가장 효율적이고 빠른 알고리즘을 연구해놓았기 때문에 우리가 생각하는 것이상으로 빠르게 동작합니다. 그러므로 reverse함수를 include 해서 쓰는 것이 효율적입니다.
C++에서 제공하는 algorithm 헤더 파일에 포함된 reverse() 함수는 매우 효율적으로 구현되어 있으며,
일반적으로 직접 구현하는 것보다 더 빠릅니다.
algorithm 헤더 파일에 포함된 함수들은 이미 최적화되어 있어서 성능상의 이점을 가져올 수 있습니다.
또한 직접 구현할 경우 버그가 발생할 가능성이 높아지므로,
가능하다면 라이브러리를 사용하는 것이 좋습니다.
그러나, reverse() 함수가 vector와 같은 컨테이너에만 작동하므로,
특정 상황에서는 직접 구현한 것이 더 효율적일 수 있습니다.
따라서 어떤 방법이 더 나은지는 상황에 따라 다르므로,
사용하는 컨테이너와 데이터의 크기 등을 고려하여 선택하는 것이 좋습니다.
관련문제를 하나 풀어보도록 합시다.
9093번: 단어 뒤집기
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는
www.acmicpc.net
다음처럼 문장이 주어지면 단어만 뒤집는 프로그램을 만들어주세요.
저번시간에 공백을 포함한 문장을 받는 방법으로 getline을 배웠습니다. 그러므로 getline을 응용해보도록 합시다.
#include <iostream>
#include <string>
int main() {
int t; std::cin >> t;
std::cin.ignore();
while (t--) {
std::string munjang; getline(std::cin, munjang);
std::cout << munjang << std::endl;
}
}우선은 공백을 포함해서 문자열을 입력받는 출력하는 코드를 만들어보았습니다.
그러면 두가지 함수가 필요할 것이라 생각됩니다.
문자열을 띄어쓰기로 구분(단어)해서 벡터로 저장해주는 division 함수
단어를 뒤집어주는 revers함수가 필요하지 않을까 생각합니다.
division 함수의 input은 string 값과 빈 v의 참조값이 들어옵니다.
output은 bool로서 문제없이 구분지었다는 신호를 보낼 수 있지만 우선은 void로 지정합니다.
revers 는 책에서 언급한 함수를 그대로 사용합니다. 그러면 우선 division함수를 구현해봅시다.
void division(std::string munjang, std::vector<std::string> &v) {
std::string word = "";
for (auto i : munjang) {
if (i != ' ') {
word += i;
}
else {
v.push_back(word);
word = "";
}
}
if (word != "") {
v.push_back(word);
}
}다음처럼 구현을 하면 될 듯 합니다. 그렇게 된다면 v를 참조하게 함으로 메모리 효율면에서 좋습니다. 하지만 chatgpt한테 지금보다 더 효율적으로 바꿀 수 있는가를 물어봤습니다. 다음처럼 안내를 해주었습니다.
따라서 munjang 매개변수를 const std::string&로 변경하고, v 매개변수를 std::vector<std::string>&로 변경하여 참조로 전달하는 것이 더 효율적입니다. 이렇게 변경하면 munjang의 복사본이 생성되지 않으며, v도 원본에 직접 접근할 수 있습니다.
그렇게 변화된 코드가 아래의 코드입니다.
void division(const std::string& munjang, std::vector<std::string> &v) {
std::string word = "";
for (auto i : munjang) {
if (i != ' ') {
word += i;
}
else {
v.push_back(word);
word = "";
}
}
if (word != "") {
v.push_back(word);
}
}왜 munjang을 const 형식으로 선언하게 되는 걸까요? 이것도 질문을 해보도록 하겠습니다.
const std::string&은 "const reference to a string"을 의미합니다. 이 경우에는 해당 함수 내에서 munjang을 수정하지 않아야 하며, 이를 보장하기 위해 const로 선언했습니다. 즉, 이 함수 내에서 munjang이 참조하는 std::string 객체는 변경되지 않습니다. 이렇게 하면 munjang이 참조하는 std::string 객체의 복사본을 만들 필요 없이, 원본 std::string 객체를 효율적으로 전달할 수 있습니다. 또한, const로 선언된 매개변수는 함수 내에서 수정될 가능성이 없으므로, 코드 안정성도 향상됩니다.
즉 수정을 원치않는 경우에 쓰는 것 같습니다. 참조를 하게되면 함수에서 munjang을 변경할 가능성이 높아집니다.
그렇기 때문에 const로 변경을 하지 못하게 막으면서 참조를 하는 것입니다.
그래서 division 함수를 작성완료했습니다. 다음은 reverse 함수입니다.
여기서 고민이 빠집니다. 벡터를 전부 보낼까? 벡터를 하나씩 보낼까? 저는 개인저긍로 함수가 늘어지는 것을 방지하는 것이 좋다고 저는 생각합니다. 그렇기에 메인문에서 for문을 돌면서 하나씩 reverse로 보내도록 합시다.
그러면 우선 main문 부터 완성을 시킵니다.
int main() {
int t; std::cin >> t;
std::cin.ignore();
while (t--) {
std::vector<std::string> v;
std::string munjang; getline(std::cin, munjang);
division(munjang, v);
for (auto i : v) {
reverse(i);
}
}
}그 후에 reverse 함수를 작성합시다. string을 참고로 받아서 변환시킵니다. 위에서 만들었던 코드를 삽입합시다.
void reverse(std::string &word) {
}여기를 다음처럼 변경합니다.
void reverse(std::string &word) {
char temp;
for (int i = 0; i < word.length() / 2; i++) {
temp = word[i];
word[i] = word[word.length() - i - 1];
word[word.length() - i - 1] = temp;
}
}
이제 벡터를 출력해봅시다 main을 다음처럼 변경합니다.
int main() {
int t; std::cin >> t;
std::cin.ignore();
while (t--) {
std::vector<std::string> v;
std::string munjang; getline(std::cin, munjang);
division(munjang, v);
for (auto i : v) {
reverse(i);
std::cout << i << " ";
}
std::cout << std::endl;
}
}
그러면 전체코드는 이렇게 생겼습니다.
#include <iostream>
#include <string>
#include<vector>
void division(const std::string& munjang, std::vector<std::string> &v) {
std::string word = "";
for (auto i : munjang) {
if (i != ' ') {
word += i;
}
else {
v.push_back(word);
word = "";
}
}
if (word != "") {
v.push_back(word);
}
}
void reverse(std::string &word) {
char temp;
for (int i = 0; i < word.length() / 2; i++) {
temp = word[i];
word[i] = word[word.length() - i - 1];
word[word.length() - i - 1] = temp;
}
}
int main() {
int t; std::cin >> t;
std::cin.ignore();
while (t--) {
std::vector<std::string> v;
std::string munjang; getline(std::cin, munjang);
division(munjang, v);
for (auto i : v) {
reverse(i);
std::cout << i << " ";
}
std::cout << std::endl;
}
}한 번 돌려볼까요?
2
I am happy today
We want to win the first prize
출력이 문제없이 잘됩니다. 제출합니다.
정답입니다.
다른 사람의 코드를 보면서 공부를 해보자
40ms가 나오는 사람은 뭘까?
사실 108556KB가 궁금합니다만 비공개라.. 보고싶네요..
우선 isKang5532 님의 코드 풀이로 속도가 28ms 가 나옵니다.
#include <iostream>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define endl "\n"
int main()
{
FAST_IO;
int tc;
cin >> tc;
cin.ignore();
string s;
while (tc-- && getline(cin, s))
{
string ans;
string word;
for (int i = 0; i <= s.length(); i++)
if (i != s.length() && s[i] != ' ')
word += s[i];
else
ans += string(word.rbegin(), word.rend()) + ' ', word.clear();
cout << ans << endl;
}
}저 문장이 속도를 올리는 것으로 보입니다. 위 3가지를 진행하는 것인데 도대체 저게 뭘까요?
저도 처음보는 것이라 chatgpt를 활용합니다.
#define 전처리기 지시어는 코드 컴파일 전에 텍스트 치환이 이루어지는 기능을 수행합니다. 즉, FAST_IO가 나오는 곳마다 ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);로 대체됩니다.
이중 ios::sync_with_stdio(false)는 C++의 iostream 라이브러리에서 C 스타일의 입출력 방식과 동기화(synchronization)를 끄는 역할을 합니다. 이를 끄면 입출력 성능이 향상됩니다.
cin.tie(NULL)는 cin의 버퍼와 cout의 버퍼를 묶는 역할을 합니다. 기본적으로 C++의 iostream 라이브러리는 입출력 버퍼를 묶어서 사용하도록 설정되어 있습니다. 이를 끄면 cin과 cout이 서로 다른 버퍼를 사용하므로 입출력 속도가 향상됩니다.
cout.tie(NULL)은 cout의 출력 버퍼와 cerr의 출력 버퍼를 묶는 역할을 합니다. 이를 끄면 cout과 cerr이 서로 다른 출력 버퍼를 사용하므로 출력 속도가 향상됩니다.
ios::sync_with_stdio(false)를 사용하면 C 스타일의 printf와 scanf 함수를 사용할 수 없으므로, 이를 대체할 수 있는 printf와 scanf 함수인 std::printf와 std::scanf를 사용해야 합니다.
라고 합니다.. 뭐 속도가 크게 오른다는 것 같습니다.
while (tc-- && getline(cin, s))이 스킬도 꽤나 인상적입니다.
while (t--) {
std::string munjang; getline(std::cin, munjang);이 코드를 단 한줄로 압축시키는 스킬입니다.
그 밑에도 chatgpt에게 물어봐야할 것 같습니다 처음보는 방식입니다.
이 코드는 입력으로 들어오는 문자열을 단어 단위로 뒤집어서 출력하는 문제를 해결하기 위한 코드입니다.
while (tc-- && getline(cin, s))는 tc 횟수만큼 반복하면서 한 줄씩 입력을 받아옵니다. getline(cin, s)는 cin에서 한 줄씩 입력을 받아 s 변수에 저장합니다.
string ans;는 단어를 뒤집어서 저장할 문자열 ans를 초기화합니다.
string word;는 현재 읽은 단어를 저장할 문자열 word를 초기화합니다.
for (int i = 0; i <= s.length(); i++)는 입력받은 문자열 s의 각 문자를 하나씩 순회합니다. i != s.length() && s[i] != ' '는 문자열의 끝에 도달하지 않았고, 현재 문자가 공백이 아닐 때를 검사합니다.
word += s[i];는 현재 단어 word에 문자열의 현재 문자 s[i]를 추가합니다.
else ans += string(word.rbegin(), word.rend()) + ' ', word.clear();는 단어가 끝났을 때, 단어를 뒤집고 ans 문자열에 추가하고, word 변수를 초기화합니다. string(word.rbegin(), word.rend())는 word를 역순으로 뒤집은 문자열을 생성합니다.
cout << ans << endl;는 뒤집어진 문자열 ans를 출력합니다.
뭐 이렇게도 짜는구나 하고 넘어가겠습니다. 한가지 궁금증이라면 제 코드에도 한 번 #define을 넣고 돌려보고 속도가 얼마나 증가하는지 테스트 해보겠습니다.
#define FAST_IO std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);해당 문과
FAST_IO;메인에 이 두개를 추가한 상태입니다. 한 번 속도 변화를 보도록 하겠습니다
제 코드에는 별차이가 없습니다... 오히려 속도가 증가했군요
이 부분에 대해서는 조금더 연구가 필요할 것 같습니다.
'ㅇ 공부#언어 > (C++) 알고리즘' 카테고리의 다른 글
| (C++)알고리즘 탐구 5. 브루트 포스 (1/2) (풀이, 알고리즘 분석) (1) | 2023.04.05 |
|---|---|
| C++ 코딩 테스트 기술 모음 (0) | 2023.04.03 |
| (C++)알고리즘 탐구 4. 애너그램 그룹 (풀이, 남의 코드 분석) (1) | 2023.04.02 |
| (C++)알고리즘 탐구 3. 가장 많은 글자. (풀이, 남의 코드 분석) (0) | 2023.04.01 |
| (C++)알고리즘 탐구 1. 유효한 팰린드롬 (풀이, 남의 코드 분석) (0) | 2023.03.30 |