1. Mat class at() 메소드 사용

#include > using namespace cv; using namespace std; > int main() { Mat img = imread("lenna.jpg", IMREAD_GRAYSCALE); if (img.empty()) { cout << "Image not found.\n"; return -1; } imshow("Image", img); > Mat atImg = img.clone(); for (int r = 0; r < atImg.rows; r++) { for (int c = 0; c < atImg.cols; c++) { atImg.at(r, c) = saturate_cast(atImg.at(r, c) + 30); } } imshow("at Image", atImg); > waitKey(0); return 0; } ``` ##### 실행화면 > > > ```cpp // Overflow 오버플로우 img.at (r, c) = img.at(r, c) + 30; // 255값을 넘어가면 Overflow 발생 > // 해결 방법 img.at (r, c) = saturate_cast(img.at(r, c) + 30); // 255를 넘는 수는 255로 casting 된다. ``` > #### 2. 배열 연산자[] 사용 > ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { Mat img = imread("lenna.jpg", IMREAD_GRAYSCALE); if (img.empty()) { cout << "Image not found.\n"; return -1; } imshow("Image", img); > Mat arrayImg = img.clone(); for (int r = 0; r < arrayImg.rows; r++) { uchar* p = arrayImg.ptr(r); for (int c = 0; c < arrayImg.cols; c++) { p[c] = saturate_cast(p[c] + 30); } } imshow("arrayImage", arrayImg); > waitKey(0); return 0; } ``` ``` img.ptr : 이미지 데이터 포인터 ``` ##### 실행화면 > > #### 3. Open CV convertTo() 함수 사용하기 > ``` 영상의 밝기를 증가시키는 것은 Open CV에서 함수로 지원하고 있다. src.convertTo(dst, rType, alpha, beta); > // dst : output matrix // rType : output matrix type || depth (-1 : src와 같은 type으로) // alpha : scale factor (콘드라스트 조정에 주로 사용) // beta : added value (밝기에 주로 사용) ``` > ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { Mat img = imread("lenna.jpg", IMREAD_GRAYSCALE); if (img.empty()) { cout << "Image not found.\n"; return -1; } imshow("Image", img); > Mat convertImg; img.convertTo(convertImg, -1, 1, 30); // (outputImage, type, alpha, beta) -- alpha : contrast, beta : brightness imshow("convertImg ", convertImg); > waitKey(0); return 0; } ``` ##### 실행 화면 >

✔ 밝기 및 콘트라스트 조정

Brightness : 밝기
Contrast : 색상 대비 (밝기 생상 차이)

> > ``` increased constrast : 가장 밝은 값과 어두운 값의 차이를 키운다. decreased constrast : 가장 밝은 값과 어두운 값의 차이를 줄인다. > Image Enhancement를 위해 사용된다. ``` > > ``` α : Contrast 조정 값 (gain) (α > 1 → 색상 스펙트럼이 넓어진다. : high contrast) (α < 1 → 색상 스펙트럼이 좁아진다. : low contrast) β : Brightness 조정 값 (bias) ``` > ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { Mat img = imread("contrast.jpg", IMREAD_COLOR); if (img.empty()) { cout << "Image not found.\n"; return -1; } imshow("color Image", img); > double alpha = 1.5; int beta = 0; Mat enhaceImg; > img.convertTo(enhaceImg, -1, alpha, beta); // enhaceImg = img * alpha + beta; imshow("enhaceImg ", enhaceImg); > waitKey(0); return 0; } ``` ##### 실행 화면 > > ``` 왼쪽 원본 사진과 오른쪽 콘트라스트 조정한 사진을 비교해보면 확실히 색 대비가 커진 것을 볼 수 있습니다. ``` ---

✔ Test Image

lenna.jpg (400 x 400) contrast.jpg (553 x 346)

]]>

What's the question?

왼쪽 마우스를 클릭하고 드래깅하여 마우스를 up하는 순간 영역에 사각형 하나를 그린다.
지정한 사각형을 오른쪽 상단 기준 (10, 10) 떨어진 위치에 원래 크기로 하나 삽입하고,
그 아래에 50% 사이즈로 삽입하라.

Code

#include <opencv2/opencv.hpp>
#include <iostream>
>
using namespace cv;
using namespace std;
>
static bool cropping = false; // right Top에 한 번만 보여주기 위한 변수
static int mx1, my1, mx2, my2;
const string WINDOW_TITLE = "Lenna Image";
>
void onMouse(int event, int x, int y, int flags, void* src) {
    Mat& img = *(Mat*)src;
    if (event == EVENT_LBUTTONDOWN) { // 왼쪽 마우스 누르면 처음 좌표 저장
        mx1 = x;
        my1 = y;
    }
    else if (event == EVENT_LBUTTONUP) { // 왼쪽 마우스 떼면 끝 좌표 저장
        // Exception of boundary exceeded
        mx2 = min(x, img.cols);
        my2 = min(y, img.rows);
>
        //  ROI ractangle
        int width = mx2 - mx1;
        int height = my2 - my1;
        rectangle(img, Rect(mx1, my1, width, height), Scalar(0, 255, 0), 2);
>
        if (!cropping) {
            cropping = true;
            Mat cropImg(img, Rect(mx1, my1, width, height)); // 관심영역 이미지
            Mat smallCropImage = cropImg.clone(); // 작은 관심영역을 위한 복제
>
            // right top ROI origin
            int px = img.cols - (width) - 10;
            int py = 10;
            Mat originRoi = Mat(img, Rect(px, py, width, height));
            cropImg.copyTo(originRoi);
>
            // right top ROI small
            width /= 2;
            px += width;
            py += height;
            height /= 2;
>
            resize(smallCropImage, smallCropImage, Size(width, height));
            height = min(height, img.rows - py); // Exception of boundary exceeded
            smallCropImage.resize(height);
>
            Mat smallRoi = Mat(img, Rect(px, py, width, height));
            smallCropImage.copyTo(smallRoi);
        }
    }
    imshow(WINDOW_TITLE, img);
}
>
int main() {
    Mat img = imread("Lenna.jpg", IMREAD_COLOR);
    if (img.empty()) {
        cout << "Image not found.\n";
        return -1;
    }
    imshow(WINDOW_TITLE, img);
>
    setMouseCallback(WINDOW_TITLE, onMouse, &img);
>
    waitKey(0);
    return 0;
}

실행화면

✔ Test Image

lenna.jpg (400 x 400)

관심영역 (ROI)

관심 영역 ROI는 Region Of Interest로 의미 그대로 이미지 내부의 관심있는 영역을 의미한다.

#include > using namespace cv; using namespace std; > int main() { Mat A; A = imread("lenna.jpg", IMREAD_COLOR); if (A.empty()) { cout << " no image" << endl; return -1; } > Rect r(10, 10, 100, 100); Mat D = A(r); // A의 r부분을 D가 pointing (얕은 복사) D = Scalar(0, 0, 0); // 관심 영역의 모든 화소가 (0, 0, 0)이 된다. > imshow("src", A); waitKey(); return 0; } ``` ##### 실행 결과

✔ Mat 복사 및 자료형 반환 메소드(Deep Copy)

> ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { double data[] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.0, 9.9, 10, 11, 12 }; > Mat m1(3, 4, CV_64F, data); Mat m2 = m1.clone(); // 새로운 행렬 반환 > Mat m3, m4; m1.copyTo(m3); // 행렬을 parameter로 들어온 행렬에 복사 m1.convertTo(m4, CV_8U); // 데이터 타입 변경 > cout << "[m1] = " << m1 << "\n\n"; cout << "[m2] = " << m2 << "\n\n"; cout << "[m3] = " << m3 << "\n\n"; cout << "[m4] = " << m4 << "\n\n"; > // m3의 데이터 변화는 m1에게 미치지 않는다. (Deep Copy) m3 = 1.1; cout << "[m1] = " << m1 << "\n\n"; cout << "[m3] = " << m3 << "\n\n"; waitKey(); return 0; } ``` ##### 실행 화면

✔ 관심 영역 로고 삽입

오른쪽 하단에 로고 삽입

#include <opencv2/opencv.hpp>
#include <iostream>
>
using namespace cv;
using namespace std;
>
int main()
{
    Mat A = imread("sea.jpg", IMREAD_COLOR);
    Mat B = imread("logo.jpg", IMREAD_COLOR);
>    
    // (widthA - widthB, heightA - heightB) 위치에서
    // widthB, heightB의 직사각형을 관심영역으로
    Rect R(A.cols - B.cols, A.rows - B.rows, B.cols, B.rows);
>
    Mat roi(A, R);
    B.copyTo(roi);
>
    imshow("sea & logo", A);
    waitKey();
    return 0;
}

> ###### 참고

✔ 관심 영역 값으로 출력하기

Mat A = imread("lenna.jpg", IMREAD_COLOR);
Mat roi(A, Rect(10, 10, 2, 2));
>
cout << "[roi] = \n" << roi << "\n";
>
// (10, 10)위치의 B, G, R 값 , (10, 11)위치의 B, G, R 값
// (10, 11)위치의 B, G, R 값 , (11, 11)위치의 B, G, R 값 을 출력한다.

실행 화면

✔ 영상 사이즈 변경 resize()

Mat src = imread(""lenna.jpg");
Mat dst;
resize(std, dst, Size(100, 100));
imshow("smallImage", dst);

> ##### 실행 화면 ----

✔ Test Image

lenna.jpg (400 x 400) sea.jpg (509 x 339) logo.jpg (80 x 40)

]]>

다양한 종류의 Mat Class 생성자 형태

Mat Class는 OpenCV에서 영상을 담을 때 사용하는 데이터 구조로 다양한 생성자를 제공한다.
(다양한 생성자를 활용하여 다양한 형태의 Mat 객체를 생성 가능)

#include > using namespace cv; using namespace std; > int main() { float data[] = { 1.2f, 2.3f, 3.2f, 4.5f, 5.f, 6.5f, }; > Mat m1(2, 3, CV_8U); // 채널 미지정시 C1가 default Mat m2(2, 3, CV_8U, Scalar(300)); // uchar : 안에 값이 255를 넘을 경우 255로 할 Mat m3(2, 3, CV_16S, Scalar(300)); // short : 300으로 저장 Mat m4(2, 3, CV_32F, data); // data 값으로 초기 > Size sz(2, 3); // width = 2, height = 3; Mat m5(sz, CV_64F); Mat m6(Size(2, 3), CV_32F, data); > cout << "[m1] = \n" << m1 << endl; cout << "[m2] = \n" << m2 << endl; cout << "[m3] = \n" << m3 << endl; cout << "[m4] = \n" << m4 << endl; cout << "\n[m5] = \n" << m5 << endl; cout << "[m6] = \n" << m6 << endl; > waitKey(0); return 0; } ``` ##### 실행 화면 > ##### ⚠ 간단하게 type 알아보기 > ```cpp Mat(3, 4, CV_8UC3); // Mat::Mat(int rows, int cols, int type) // CV_ : openCV의 상수 prefix로 CV가 쓰인다. (Constant prefix) // 8U : 8bit unsigned // C3 : Channel이 3개 (C1 -> grayScale, C3 -> RGB) // 따라서, 8비트 unsigned 타입의 3개의 채널을 가진다. // CV_8U : Mat::depth()로 알 수 있으며 C3 : Mat::channels()를 통해 알 수 있다. ```

✔ Mat Class 멤버 변수 & 멤버 메소드

> ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { Mat m1(4, 3, CV_32FC3); cout << "차원 수 : " << m1.dims << "\n"; cout << "행 개수 : " << m1.rows << "\n"; cout << "열 개수 : " << m1.cols << "\n"; cout << "행렬 크기 : " << m1.size() << "\n\n"; > cout << "전체 원소 개수 : " << m1.total() << "\n"; cout << "한 원소의 크기 : " << m1.elemSize() << "\n"; cout << "한 원소의 한 채널 크기 : " << m1.elemSize1() << "\n\n"; > cout << "타입 : " << m1.type() << "\n"; cout << "타입 (채널 수 | 깊이) : " << ((m1.channels() - 1) << 3) + m1.depth() << "\n"; cout << "깊이 : " << m1.depth() << "\n"; cout << "채널 : " << m1.channels() << "\n\n"; > cout << "step : " << m1.step << "\n"; cout << "step1 : " << m1.step1() << "\n"; > waitKey(0); return 0; } ``` ##### 실행 화면

✔ Mat 객체의 자료형 지정 오류 예시

> ``` short 2개가 모여서 integer가 되기 때문에 두 개씩 mapping 된다. ```

✔ 특수한 행렬을 생성하는 함수

> ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { Mat m1 = Mat::ones(3, 4, CV_8UC1); Mat m2 = Mat::zeros(2, 4, CV_8UC3); Mat m3 = Mat::eye(3, 5, CV_8U); > cout << "[m1] = \n" << m1 << endl; cout << "[m2] = \n" << m2 << endl; cout << "[m3] = \n" << m3 << endl; > waitKey(0); return 0; } ``` ##### 실행 화면 >

✔ Mat 클래스의 할당(=) 연산자

> ##### Code ```cpp #include #include > using namespace cv; using namespace std; > int main() { Mat m1(2, 3, CV_8U, 2); Mat m2(2, 3, CV_8U, 1); > m1 = 100; Mat m3 = m1 + m2; Mat m4 = m1 -2; Mat m5 = m1; > cout << "[m1] = \n" << m1 << endl; cout << "[m2] = \n" << m2 << endl; cout << "[m3] = \n" << m3 << endl; cout << "[m4] = \n" << m4 << endl; cout << "[m5] = \n" << m5 << endl; > m5 = 2; > cout << "\n[m1] = \n" << m1 << endl; cout << "[m5] = \n" << m5 << endl; > waitKey(0); return 0; } ``` ##### 실행 화면 >

✔ Mat 객체 복사 : Shallow Copy(얕은 복사) vs Deep Copy(깊은 복사)

Mat A;
A = imread("image.jpg", IMREAD_COLOR); // 메모리 할당
>
Mat F = A; // 할당 연산자 : 얕은 복사가 수행된다 (메모리를 공유)
Mat B = A.clone(); // clone() : 깊은 복사가 수행된다.

]]>

1. 검정 윈도우 창 띄우기

Mat blackWindow = Mat(400, 600, CV_8UC3, Scalar(0, 0, 0));
imshow("Black Window", blackWindow);

#include > using namespace cv; using namespace std; > int main() { Mat blackWindow = Mat(400, 600, CV_8UC3, Scalar(0, 0, 0)); > line(blackWindow, Point(100, 100), Point(300, 300), Scalar(0, 0, 255), 5); rectangle(blackWindow, Point(250, 30), Point(450, 200), Scalar(0, 255, 0), 7); circle(blackWindow, Point(100, 300), 60, Scalar(255, 0, 0), 3); ellipse(blackWindow, Point(300, 350), Point(100, 60), 45, 130, 270, Scalar(255, 255, 255), 5); > imshow("Black Window", blackWindow); > waitKey(0); return(0); } ``` > ##### 실행 화면 >

✔ Open CV 마우스 이벤트 처리

Callback Function (콜백 함수)

- 특정 함수가 어떤 함수의 인자로서 사용될 때 이 함수를 콜백 함수라고 한다.

Open CV Mouse Callback Function

// 1. Mouse Callback Function 정의
>
- 마우스의 상태에 변화가 생겼을 때 특정 함수를 호출할 수 있도록 사용자가 특정 함수를 정의하고 등록할 수 있다.
- 마우스에 변화가 생겼을 때 '어떤 일'을 할 것인지를 정의
>
void onMouse(int event, int x, int y, int flags, void* param){
    // 사용자 정의 함수로 함수 이름은 마음대로 정의할 수 있다.(onMouse() 대신 mouseCallback() 가능)
    // Event : 마우스 이벤트
    // x, y : 마우스 위치
    // Flags : 이벤트 부가정보
    // param : 기타 파라메터
}

// 2. Mouse Callback Function 등록
setMouseCallback("windowName", onMouse, &src);

> ##### 마우스 이벤트 종류 (int event) ``` EVENT_LBUTTONDOWN 왼쪽 버튼 눌림 EVENT_MBUTTONDOWN 가운데 버튼 눌림 EVENT_RBUTTONDOWN 오른쪽 버튼 눌림 > EVENT_LBUTTONUP 왼쪽 버튼 UP EVENT_MBUTTONUP 가운데 버튼 UP EVENT_RBUTTONUP 오른쪽 버튼 UP > EVENT_MOUSEMOVE 마우스 이동 ``` > ##### 전체 코드 ```cpp #include #include > using namespace cv; using namespace std; > // 마우스 이벤트가 발생하면 호출되는 콜백 함수 #include #include > using namespace cv; using namespace std; > // 마우스 이벤트가 발생하면 호출되는 콜백 함수 void onMouse(int event, int x, int y, int flags, void* src) { if (event == EVENT_LBUTTONDOWN) { // 왼쪽 마우스가 눌리면 Mat& img = *(Mat*)(src); circle(img, Point(x, y), 100, Scalar(0, 0, 255), 5); putText(img, "I found a lenna!", Point(x, y + 100), FONT_HERSHEY_PLAIN, 2.0, 255, 2); imshow("windowName", img); // 영상이 변경되면 다시 표시한다. } else if (event == EVENT_RBUTTONDOWN) {} else if (event == EVENT_MBUTTONDOWN) {} else if (event == EVENT_MOUSEMOVE) {} } > int main() { Mat image = imread("lenna.jpg", IMREAD_COLOR); if (image.empty()) { cout << "does not read the file\n"; } > imshow("windowName", image); > setMouseCallback("windowName", onMouse, &image); > waitKey(0); return 0; } ``` ##### 실행 결과 >

✔ Open CV 키보드 이벤트 처리

Open CV는 waitKey()를 통해 키보드 입력을 받을 수 있다.

int key = waitKey(100); // delay 100

> ``` 하지만, waitKey()는 1Byte의 키값을 입력받기 때문에 기능 키(F1, F2, ... , F12), 방향 키 (→, ←, ↑, ↓)등의 특수 키를 입력받을 수 없다. 이때, waitKeyEx()를 사용하게 되면 2Byte의 키값을 입력받아 특수키 입력이 가능하다. ``` > ```cpp int key = waitKeyEx(100); // delay 100 ``` > > ##### 전체 코드 ```cpp #include #include > using namespace cv; using namespace std; > int main(){ Mat image = imread("lenna.jpg", IMREAD_COLOR); if (image.empty()) { cout << "does not read the file\n"; } > imshow("windowName", image); > while (true) { int key = waitKeyEx(); if (key == 'q') break; else if (key == 2424832) { // <- image -= 50; } else if (key == 2555904) { // -> image += 50; } imshow("windowName", image); > return 0; } ``` ##### 실행 화면

---

✔ Test Image

lenna.jpg (400 x 400)

]]>

#include <opencv2/opencv.hpp>
#include <iostream>
>
using namespavce cv;
using namespace std;
>
int main(){
    Mat image; // Mat : 이미지 저장 & 관리 클래스   
    image = imread("lenna.jpg", IMREAD_COLOR); // 이미지 읽기
    if(image.empty()){
        cout << "does not read the file\n";
    }
    >
    imshow("windowTitle", image); // 이미지 출력 ("windowTitle" → "Lenna Image")
    >
    waitKey(0); // 바로 창이 종료되지 않도록 키보드 입력 기다림
    return 0;
}

✔ GrayScale 이미지로 변환

#include <opencv2/opencv.hpp>
#include <iostream>
>
using namespavce cv;
using namespace std;
>
int main(){
    Mat image; // Mat : 이미지 저장 & 관리 클래스   
    image = imread("lenna.jpg", IMREAD_COLOR); // 이미지 읽기
    if(image.empty()){
        cout << "does not read the file\n";
    }
    >
    imshow("windowTitle", image); // 이미지 출력 ("windowTitle" → "Lenna Image")
    >
    Mat gray;
    cvtColor(img, gray, COLOR_BGR2GRAY);
>
    imshow("GrayScale Image", gray);
    imwrite("gray.jpg", gray); // 파일 저장
    >
    waitKey(0); // 바로 창이 종료되지 않도록 키보드 입력 기다림
    return 0;
}

※ Open CV의 color default : BGR (Blue, Green, Red)

✔ Test Image

lenna.jpg (400 x 400)

#include <bits/stdc++.h>
>
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

// call by reference (integer variable)
int fn(int* p){
    *p = 33;
}
int a = 1;
fn(&a); // -- 33으로 변경

void fn(vector<int> &v){
    v[1] = 333;
}
vector<int> g = {2, 3, 4, 5};
fn(g); // -- g[1] = 333으로 변경

1. Vector 벡터

1. vector STL

#inclue <vector>
>
using namespace std;
>
vector<int> v; // 비어있는 vector 
vector<int> v2(4); // 크기가 4인 vector 
vector<int> v3(5, 2); // 크기가 5인 2로 초기화된 vector
vector<int> v4(v2); // v2를 복사한 벡터
>
v.assign(5, 2); // 2의 값으로 5개 원소 할당
v.at(2); // 2번째 원소 참조
v[2];
v.front(); // 첫 번째 원소 참조
v.back(); // 마지막 원소 참조
v.clear(); // 모든 원소 제거 size()는 줄어들고 capacity는 그대로
v.push_back(3); // 마지막 원소 뒤에 3 삽입
v.pop_back(); // 마지막 원소 제거
v.begin(); // 첫 번째 원소 가리킴 (Iterator)
v.end(); // 마지막의 다음을 가리킨다. (Iterator)
v.reserve(n); // n개의 원소 저장위치 예약 동적할당
v.resize(n); // 크기 n으로 할당
v.resize(n, 3); // 크기를 n으로 변경하고 size가 더 커졌을 경우인자값 3을 초기화 
v.insert(v.begin() + 2, 3); // 2번째 위치에 3 삽입 
v.insert(v.begin() + 2, 3, 4); // 2번째 위치에 3개의 4 삽입 

2. 이차원 벡터 입력

vector<vector<int>> graph;
>
for (int i = 0; i <= n; i++) {
    vector<int> v;
    graph.push_back(v);
}
>
for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    graph[a].push_back(b);
}
>
// 3 3 3 3 3
// 3 3 3 3 3
// 3 3 3 3 3
vector<vector<int>> vv(3, vector<int>(5, 3));

3. vector sort() (벨로그)

bool comp(const int o1, const int o2){
    return true; // 두 데이터를 바꾸지 않는다.
    return false; // 두 데이터 o1과 o2을 바꾼다. (Swap)
}
>
// 오름차순 comp()
bool comp(const int o1, const int o2){
    return o1 <= o2;
}
>
// 내림차순 comp()
bool comp(const int o1, const int o2){
    return o1 > o2;
} 

// condition1이 가장 작거나
// conditinon2가 가장 큰 (condition1이 같은 경우)
// -> 가장 뒤로 가게 (오름차순)
>
bool comp(const int o1, const int o2){
    if(condition1[o1] == condition1[o2]){
        if(condition2[o1] < condition2[o2]){
            return true;
        }
        else{
            return false;
        }
    }
    else if(condition1[o1] > conditoin1[o2]){
        return true;
    }
    else{
        return false;
    }
}

sort(v.begin(), v.end()); // 오름차순
sort(v.begin(), v.end(), less<int>()); // 오름차순
sort(v.begin(), v.end(), greater<int>()); // 내림차순
sort(v.begin(), v.end(), comp);

이차원 벡터 시계방향 회전

// 행렬 시계방향 회전
vector<vector<int>> clockwiseRotate(vector<vector<int>> v, int count){
    int size = v.size();
    vector<vector<int>> result = v;
    >
    // count 만큼 시계방향 회전
    for(int t = 0; t < count; t++){
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                result[j][size - i - 1] = v[i][j];
            }
        }
        v = result;
    }
    return result;
}

이차원 벡터 반시계방향 회전

// 행렬 반시계방향 회전
vector<vector<int>> counterClockwiseRotate(vector<vector<int>> v, int count){
    int size = v.size();
    vector<vector<int>> result = v;
    >
    // count 만큼 반시계방향 회전
    for(int t = 0; t < count; t++){
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                result[size - j -1][i] = v[i][j];
            }
        }
        v = result;
    }
    return result;
}

2. Stack 스택 (벨로그)

3. queue 큐 (벨로그)

4. priority_queue 우선순위 큐 (벨로그)

priority_queue<int> pq;
priority_queue<int, vector<int>, compare> pq;

// 1. Top이 가장 큰 수 (우선순위가 큰 수일 때)
priority_queue<int, vector<int>, less<int>> pq;
>
// 2. Top이 가장 작은 수(우선순위가 작은 수일 때)
priority_queue<int, vector<int>, greater<int>> pq;
>
// 3. 우선순위 재정의하여 사용 (Custom 우선순위)
struct compare{
    bool operator()(int a, int b){
        return a < b; // Top이 가장 작은 수
        // return a > b; // Top이 가장 큰 수
    }
};

struct Data{
    int idx;
    int value;
};
>
struct Comp{
    bool operator()(const Data& a, const Data& b){
        return a.value > b.value; // value 작은 값이 우선순위
    }
};
>
priority_queue<int, vector<int>, Comp> pq;
>
pq.push({idx, value});
pq.top();
pq.pop();

// priority_queue는 clear() 멤버 함수가 존재하지 않는다.
while(!pq.empty()){
    pq.pop();
}

5. Heap 힙 (우선순위 큐 힙 벨로그) (최소힙) (최대힙)

priority_queue<int> pq; // maxHeap (default)
priority_queue<int, vector<int>, less<int>> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

6. Binary Search 이분 탐색

int left = 0;
int right = n;
>
while(left <= right){
    int mid = (left + right) / 2;
>            
    if(data[mid] == target){
        exist = true; // 맞는 logic으로 짜기
        break;
    }
    else if(data[mid] > target){
        right = mid - 1;
    }
    else{
        left = mid + 1;
    }
}

7. Two Pointer 투 포인터

sort(AB.begin(), AB.end()); // 오름차순
sort(CD.begin(), CD.end(), greater<int>); // 내림차순
>
long long int result = 0;
int ptab = 0, ptcd = 0;
>
while (ptab < AB.size() && ptcd < CD.size()) {
    int currentAB = AB[ptab];
    int target = -currentAB;
    >
    if (CD[ptcd] == target) {
            int ab = 0, cd = 0; // 같은 경우 개수 찾기
            while(AB[ptab] == currentAB && ptab < AB.size()){
                ab++;
                ptab++;
             }
             while(CD[ptcd] == target && ptcd < CD.size()){
                cd++;
                ptcd++;
             }
             result += (long long int) ab * cd;
        }
    else if (CD[ptcd] > target) {
        ptcd++;
    }
    else {
        ptab++;
    }
}

8. multiset 멀티셋 중복 Key 값 (벨로그)

// 1. 오름차순 정렬 (default)
multiset<int> ms;
multiset<int, less<int>> ms; 
>
// 2. 내림차순 정렬
multiset<int, greater<int>> ms;

// 데이터 삽입
ms.insert(50);
ms.insert(50);
ms.insert(10);
ms.insert(80);
ms.insert(80);

// 데이터 삭제
ms.erase(ms.begin()); // 첫번째 요소 삭제
ms.erase(--ms.end()); // 마지막 요소 삭제

// 데이터 접근
multiset<int>::iterator it;
for(it = ms.begin(); it != ms.end(); it++){
    cout << *it;
}

9. unordered_map 해쉬테이블

unordered_map<string, int> u; // key type, value type
u["A"] = 1;
u["B"] = 22;

// unordered_map 접근
for(auto elem : u){
    cout<<"key : "<<elem.first<<" value : "<<elem.second<<endl;
}

// 이차원 value 값
unordered_map<string, vector<int>> u; // key type, value type
vector<int> v;
string key = "abc";
>
u[key] = v;
u[key].push_back(2);
u[key].push_back(66);
>
for(int i = 0; i < u[key].size(); i++){
    cout << u[key][i] << " ";
}

10. String

// 문자열 입력
string s;
cin >> s;

// 한 줄 입력
while(getline(cin, s)){
    cout << s << endl;
}

// 문자열 길이
char str[25];
scanf("%s, str); // hello
strlen(str); // 5

// scanf로 string 입력받고 string type으로 만들기
char cstr[1010] = "";
scanf("%s", cstr);
>
string st(cstr);
cout << st;

// integer -> 문자열로 변환
int num = 10;
cout << to_string(number);
>
stoi = string to int
stof = string to float
stol = string to long
stoll = string to long long
stod = string to double

// 문자열 탐색
for(auto i : s){
    cout << i << endl
}

// 문자열 교체
string base = "this is a test string.";
string replace = "example 1";
>
base.replace(9, 5, replace); // 9 ~ (9+5-1) 교체

// 문자열 뒤집기
reverse(s.begin(), s.end());

// 문자열 찾기
string s = "helloll"
cout << s.find("ll") << endl;  // -> 2 ( 첫 시작 위치 인덱스)
cout << s.find("ll", 3) << endl; // -> 5 (3위치부터 검색) 

// 문자열 자르기
cout << s.substr(0, 4) << endl; // -> "hell" (0부터 4개)
cout << s.substr(5) << endl; // -> "ll" (5부터 끝까지)

// 뮨자열 교체
cout << s.replace(3, 2, "rr") << endl; // s 문자열 변경됨 
cout << s << endl;

// 문자열 대문자로 
for(int i = 0; i < s.length(); i++){
    s[i] = toupper(s[i]);
}
cout << s << endl;

// 문자열 소문자로 
for(int i = 0; i < s.length(); i++){
    s[i] = tolower(s[i]);
}
cout << s << endl;

// 문자열 공백 제거
string str = " jo hye  jeong ";
str.erase(remove(str.begin(), str.end(), ' '), str.end());
cout << str << endl;

// string 구분자로 자르기
vector<string> split(string str, char delimiter) {
    vector<string> answer;
    int prev = 0, current = str.find(delimiter);
> 
    while (current != -1) {
        string tmp = str.substr(prev, current - prev);
        answer.push_back(tmp);
 >       
        prev = current + 1;
        current = str.find(delimiter, prev);
    }
    answer.push_back(str.substr(prev, current - prev));
 >
    return answer;
}
>
int main(){
    vector<string> subS = split(s, ' ');
}

9. 최대공약수 (유클리드호제법) (벨로그)

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a; //(b가 0이 아니면 : b가 0이면)
}
>
int lcm(int a, int b) {
  return (a * b) / gcd(a, b);
}

10. 에라토스테네스의 체

bool isPrime[MAX];
vector<int> prime;
>    
for (int i = 0; i < MAX; i++) {
    isPrime[i] = true;
}
>
for (int i = 2; i < MAX; i++) {
    if (isPrime[i]) {
        prime.push_back(i);
        for(int j = 2 * i; j < MAX; j += i) {
            isPrime[j] = false;
        }
    }
}

11. 트리 순회

12. Union Find 서로소 집합

vector<int> parent;
>
void init() {
    for (int i = 0; i <= n; i++) {
        parent.push_back(i);
    }
}
>
int find(int a) {
    if (parent[a] != a)
        parent[a] = find(parent[a]);
    return parent[a];
}
>
void unionF(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    parent[pb] = pa;
}

if(find(a) == find(b)){
    // 같은 집합
}

Topological Sort 위상 정렬 (벨로그)

queue<int> q;
>
for (int i = 1; i <= n; i++) {
    if (student[i] == 0) {
        q.push(i);
    }
}
>
while (!q.empty()) {
    int front = q.front();
    q.pop();
        printf("%d ", front);
        for (int i = 0; i < graph[front].size(); i++) {
        if (--student[graph[front][i]] == 0) {
            q.push(graph[front][i]);
        }
    }
}

Kruskal's Algorithm 크루스칼 알고리즘 - 최소 스패닝 트리(MST) (벨로그)

struct Edge{
    int nodeA;
    int nodeB;
    int weight;
};
>
struct Comp{
    bool operator()(const Edge& A, const Edge& B){
        return A.weight > B.weight;
    }
};
>
vector<int> parent;
>
int find(int node){
    if(node == parent[node]) return node;
    else return find(parent[node]);
}
>
void unionF(int a, int b){
    int pA = find(a);
    int pB = find(b);
    parent[pA] = pB;
}

// main
priority_queue<Edge, vector<Edge>, Comp> edges;
>    
int edge = 0;
int result = 0;
>
for(int i = 0; i <= v; i++){
    parent.push_back(i); // 초기화
}
>
for(int i = 0; i < e; i++){
    int a, b, w;
    scanf("%d %d %d", &a, &b, &w); // a -> b 간선 가중치 w
    edges.push({a, b, w});
}
>    
while(edge < v - 1 || !edges.empty()){ // 간선 개수 v-1개
    Edge minE = edges.top();
    edges.pop();
>    
    if(find(minE.nodeA) != find(minE.nodeB)){
        unionF(minE.nodeA, minE.nodeB);
        result += minE.weight;
        edge++;
    }
}

Dijstra Algorithm (다익스트라 알고리즘) (벨로그)

특정한 하나의 정점에서 모든 정점으로의 최소 경로 (단, 음의 간선은 없다)

struct Edge{
    int id;
    int cost;
};
>
struct Comp{
    bool operator()(const Edge& a, const Edge& b){
        return a.cost > b.cost;
    }
};
>
vector<vector<Edge>> adjList;
vector<int> dist;
>
void dijkstra(int start){
    priority_queue<Edge, vector<Edge>, Comp> pq;
>    
    dist[start] = 0;
    pq.push({start, dist[start]});
>    
    while(!pq.empty()){
        Edge now = pq.top();
        pq.pop();
>        
        if(dist[now.id] < now.cost) continue;
>        
        int size = adjList[now.id].size();
        for(int i = 0; i < size; i++){
            Edge next = adjList[now.id][i];
>            
            if(dist[next.id] > now.cost + next.cost){
                dist[next.id] = now.cost + next.cost;
                pq.push({next.id, dist[next.id]});
            }
        }
    }
}

플로이드 워셜 알고리즘 (최단 경로)

모든 정점에서 모든 정점으로의 최단 경로

const int INF = 1E9;
>
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
>    
    vector<vector<int>> graph(n+1);
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if(i == j) graph[i].push_back(0); // 대각선 0
            else graph[i].push_back(INF); // INF로 초기화
        }
    }
>    
    for(int j = 0; j < m; j++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        graph[a][b] = c; // (양방향일 떄는 각각 설정)
    }
>    
    for(int k = 1; k <= n; k++){
        for(int a = 1; a <= n; a++){
            for(int b = 1; b <= n; b++){
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
            }
        }
    }
    return 0;
}

DFS

void dfs(vector<vector<int>> &graph, int node, vector<bool> &visite    
    visited[node] = true;
    printf("%d\n", node);
>    
    for(int i = 0; i < graph[node].size(); i++){
        int idx = graph[node][i];
        if(!visited[idx]){
            dfs(graph, idx, visited);
        }
    }
}
>
int main(){
    vector<vector<int>> graph = {
        {},
        {2, 3, 7},
        {1, 7},
        {1, 4, 5},
        {3, 5},
        {3, 4},
        {7},
        {2, 6, 8},
        {1, 7}
    };
>    
    vector<bool> visited(graph.size(), false);    
    dfs(graph, 1, visited);
>    
    return 0;
}

BFS

void bfs(vector<vector<int>> &graph, int node, vector<bool> &visited){
    visited[node] = true;
    queue<int> q;
    q.push(node);
>    
    while(!q.empty()){
        int top = q.front();
        q.pop();
>        
        printf("%d\n", top);
>        
        for(int i = 0; i < graph[top].size(); i++){
            int idx = graph[top][i];
            if(!visited[idx]){
                q.push(idx);
                visited[idx] = true;
            }
        }        
    }
}
>
int main(){
    vector<vector<int>> graph = {
        {},
        {2, 3, 8},
        {1, 7},
        {1, 4, 5},
        {3, 5},
        {3, 4},
        {7},
        {2, 6, 8},
        {1, 7}
    };
    >
    vector<bool> visited(graph.size(), false);
    bfs(graph, 1, visited);
    >
    return 0;
}

상하좌우 움직이기 (완전 탐색 & DFS)

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
>
void ice(vector<vector<int>> &graph, int y, int x){
    if(graph[y][x] == 1) return;
    >
    graph[y][x] = 1;
    >
    for(int i = 0; i < 4; i++){
        ice(graph, y + dy[i], x + dx[i]);
    }
}

이차원 벡터 초기화 (상하좌우 blocking)

int n, m;
scanf("%d %d", &n, &m);
>    
vector<vector<int>> data(n+2);
>        
for(int i = 0; i < n+2; i++){
    data[i].resize(m+2, 1); // 0 또는 1 조건에 맞게
}
>    
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        int x;
        scanf("%1d", &x);
        data[i][j] = x;
    }
} 

이차원 벡터 BFS (pair / make_pair)

void mapBFS(vector<vector<int>> &graph, vector<vector<bool>> &visited, int y, int x){
    visited[y][x] = true;
>    
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
>    
    while(!q.empty()){
        pair<int, int> front = q.front();
        q.pop();
>        
        int currY = front.first;
        int currX = front.second;
>        
        for(int i = 0; i < 4; i++){
            int nextY = currY + dy[i];
            int nextX = currX + dx[i];
>            
            if(!visited[nextY][nextX]){
                q.push(make_pair(nextY, nextX));
                graph[nextY][nextX] = graph[currY][currX] + 1;
                visited[nextY][nextX] = true;
            }
        }
    }
}
>
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
>    
    vector<vector<int>> data(n+2);
    vector<vector<bool>> visited(n+2);
>        
    for(int i = 0; i < n+2; i++){
        data[i].resize(m+2, 1);    
        visited[i].resize(m+2, true);
    }
>    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x;
            scanf("%1d", &x);
            data[i][j] = x;
            visited[i][j] = false;
        }
    } 
>    
    mapBFS(data, visited, 1, 1);
    printf("%d", data[n][m]);
> 
    return 0;
}

약수의 개수 구하기

int number = 12, divCount = 0;
for(int i = 1; i * i <= number; i++){
    if(number % i == 0){
        divCount++;
        if(i * i < number){
            divCount++;
          }
    }
}

정규 표현식

✔ 헤더

#include <regex> // c +11 부터 사용 가능

✔ 정규식 생성

// (regex 인스턴스를 생성해 생성자에게 검사할 형식을 인수로 넘겨준다.)
regex re("~~~~"); // 매개변수로 검사 형식 넘겨줌

✔ Syntax (문법)

^x : '^'는 문자열 시작을 의미 (x로 시작한다.)
x$ : '$'는 문자열 종료를 의미 (x로 끝난다.)
.x : '.'은 개행문자(\n)를 제외한 모든 문자를 의미
x+ : '+'는 1회 이상 반복을 의미 ({1, }와 같음)
x* : '*'은 0회 이상 반복을 의미({0, }와 같음)
x? : '?'는 0 or 1개의 문자 매칭을 의미 ({0, 1})
x|y : '|' 는 or을 의미 (x또는 y)
(x) : '()'는 그룹을 표현 ex) (abc){3} ⇒ abcabcabc 검출
x{n} : '{}'는 반복을 의미 x가 n번 반복된다.
x{n, } : x가 n번 이상 반복된다.
x{n, m} : x가 n번 ~ m번 사이 반복된다.
[xy] : '[]'는 x or y를 찾는다는 의미. ([a-z0-9] ⇒ 소문자 or 숫자)
[^xy] : '[^]'은 not을 의미. (xy 제외하고 찾는다.)
>
\\d : 숫자 (digit)
\\D : 숫자 제외 (not digit)
\\s : 공백 (space)
\\S : 공백 제외 (not space)
\\t : tab
\\w : 알파벳 (대, 소문자), 숫자 [A-Za-z0-9]
\\W : \w 제외한 특수문자

✔ Code

프로그래머스 문제 참고

for(int i = 0; i < queries.size(); i++){
        string reg = "";
>        
        int qmCount = 0;
        for(int j = 0; j < queries[i].length(); j++){
            if(queries[i][j] == '?'){
                qmCount ++;
            }
            else{
                if(qmCount > 0){
                    reg += "\\w{" + to_string(qmCount) + "}";
                    qmCount = 0;
                }
                reg += queries[i][j];
            }
        }
        if(qmCount > 0){
            reg += "\\w{" + to_string(qmCount) + "}";
        }
>        
        regex re(reg);
>        
        int result = 0;
        for(int j = 0; j < words.size(); j++){
            if(regex_match(words[j], re)){
                result ++;
            }
        }
        answer.push_back(result);
    }

Open CV 설치 링크

1. Open CV 설치

2. VS 프로젝트 생성 > Windows 데스크톱 마법사

ⓐ Windows 데스크톱 마법사 프로젝트 생성
ⓑ 빈 프로젝트 체크

3. 빌드 모드 설정 / Open CV 헤더 파일 위치 설정

ⓐ 프로젝트 속성 VC++ 디렉터리
ⓑ 포함 디렉터리 > 편집 > "opencv압축해제폴더\opencv\build\include" 추가

4. Open CV 라이브러리 위치 설정

ⓐ 라이브러리 디렉터리 > 편집 > "압축해제폴더\opencv\build\x64\vc15\lib" 추가

5. Open CV 라이브러리 추가 종속성 설정 / 동적 라이브러리 복사

ⓐ 링커 > 입력 > 추가 종속성 > "opencv_world453.lib" 추가
ⓑ "압축해제폴더\opencv\build\x64\vc15\bin"에 있는
   "opencv_world453.dll" 파일 workspace로 copy & paste

📄 문제 설명

Problem

방향그래프가 주어지면 시작점으로부터 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.
(단, 모든 간선의 가중치는 10 이하의 자연수이다.)

Input

첫째 줄 : 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
(모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.)
둘째 줄 : 시작 정점의 번호 K(1 ≤ K ≤ V)
셋째 줄 : E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)
(이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 의미)
(u와 v는 서로 다르며 w는 10 이하의 자연수)
(서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.)

Output

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

Example Input 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

Example Output 1

0
2
3
7
INF

📝 문제 해설

이 문제는 제목처럼 최단 경로 문제이다.
최단 경로 문제란 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.

▶ 최단 경로 문제 종류

- 단일 출발(single-source) 최단 경로
    어떤 하나의 정점에서 출발해 나머지 모든 정점까지의 최단경로를 찾는 문제
>
- 단일 도착(single-destination) 최단 경로
    모든 정점에서 출발해 특정 하나의 정점까지의 최단경로를 찾는 문제
>
- 단일 쌍(single-pair) 최단 경로
    어떤 정점 v에서 v'로 가는 최단 경로를 구하는 문제
>
- 전체 쌍(all-pair) 최단 경로
    모든 정점 쌍들의 사이의 최단 경로를 구하는 문제

▶ 최단 경로 알고리즘

- BFS(완전 탐색 알고리즘)
    가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구할 때 가장 빠르다
>
- 다익스트라 알고리즘 (Dijkstra Algorithm)
    음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발 단일 도착의 최단경로 문제
>
- 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm)
    가중 그래프에서의 단일 쌍, 단일 출바르 단일 도착의 최단경로 문제
>
- 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
    전체 쌍 최단 경로 문제

▶ 다익스트라 알고리즘 (Dijkstra's Algorithm)

V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서
특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
>
◼ 특징
- 각 정점을 최대 한 번씩만 방문하여 최단 거리를 확정한다.
- 아직 방문하지 않은 정점들 중 최단 거리인 점을 찾아 방문하고 최단거리 획정 반복
- 총 V * V번의 연산이 필요해 O(V²)의 시간 복잡도를 가진다.
- 방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는 과정에서 우선순위 큐 / 힙을 이용하면 더욱 개선된 알고리즘 가능

</> Source Code

#include <bits/stdc++.h>
#define INF 1E9
>
using namespace std;
>
struct Edge{
    int id;
    int cost;
};
>
struct Comp{
    bool operator()(const Edge& a, const Edge& b){
        return a.cost > b.cost;
    }
};
>
vector<vector<Edge>> adjList;
vector<int> dist;
>
void dijkstra(int start){
    priority_queue<Edge, vector<Edge>, Comp> pq;
>    
    // 1)
    dist[start] = 0;
    pq.push({start, dist[start]});
>    
    while(!pq.empty()){
        Edge now = pq.top();
        pq.pop();
>        
        // 2)
        if(dist[now.id] < now.cost) continue;
>        
        // 3)
        int size = adjList[now.id].size();
        for(int i = 0; i < size; i++){
            Edge next = adjList[now.id][i];
>            
            // 1]
            if(dist[next.id] > now.cost + next.cost){
                dist[next.id] = now.cost + next.cost;
                pq.push({next.id, dist[next.id]});
            }
        }
    }
}
>
int main(){    
    int v, e, start;
    scanf("%d %d %d", &v, &e, &start);
>    
    // 1. init dist, 2. init adJList
    for(int i = 0; i <= v; i++){
        dist.push_back(INF);
        vector<Edge> tmp;
        adjList.push_back(tmp);
    }    
>    
    // 3. input adjList
    for(int i = 0; i < e; i++){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        adjList[a].push_back({b, w});
    }
>    
    // 4. dijkstra
    dijkstra(start);
>    
    // 5. print result
    for(int i = 1; i < dist.size(); i++){
        if(dist[i] < INF){
            printf("%d\n", dist[i]);
        }
        else{
            printf("INF\n");
        }
    }
>    
    return 0;
}

📄 문제 설명

Problem

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
>
최소 스패닝 트리란,
주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중 가중치의 합이 최소인 트리이다.

Input

첫째 줄 : 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)
다음 E개 줄 : 각 간선에 대한 정보를 나타내는 세 정수 A, B, C
(A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미)
(C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.)
>
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다.
가중치는 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터

Output

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

Example Input 1

3 3
1 2 1
2 3 2
1 3 3

Example Output 1

3

📝 문제 해설

이 문제는 제목처럼 최소 스패닝 트리 문제이다.

▶ 최소 신장 트리 (Minimum Spanning Tree / MST)

무향 연결 가중 그래프 G에서 간선의 가중치의 합이 최소인 신장(spanning) 트리이다.
>
◼ 신장 트리(spanning tree)란?
그래프 내의 모든 정점을 포함하는 트리이면서, 그래프의 최소 연결 부분 그래프이다.
최소 연결: 간선의 수가 가장 적다는 의미
(v개의 정점을 가지는 그래프의 최소 간선의 수는 (v-1)개)
>
◼ MST 특징
- 간선의 가중치 합이 최소
- v개의 정점을 가지는 그래프에 대해서 반드시 (v-1)개의 간선만을 이용.
- 사이클을 포함하지 않는다.

▶ MST 구현 방법 - 크루스칼 알고리즘 (Kruskal's Algorithm)

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
struct Edge{
    int nodeA;
    int nodeB;
    int weight;
};
>
struct Comp{
    bool operator()(const Edge& A, const Edge& B){
        return A.weight > B.weight;
    }
};
>
vector<int> parent;
>
int find(int node){
    if(node == parent[node]) return node;
    else return find(parent[node]);
}
>
void unionF(int a, int b){
    int pA = find(a);
    int pB = find(b);
    parent[pA] = pB;
}
>
int main() {    
    int v, e;
    scanf("%d %d", &v, &e);
>    
    priority_queue<Edge, vector<Edge>, Comp> edges;
>    
    int edge = 0;
    int result = 0;
>
    for(int i = 0; i <= v; i++){
        parent.push_back(i);
    }    
>    
    for(int i = 0; i < e; i++){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);        
        edges.push({a, b, w});
    }
>    
    while(edge < v - 1 || !edges.empty()){
        Edge minE = edges.top();
        edges.pop();
>        
        if(find(minE.nodeA) != find(minE.nodeB)){
            unionF(minE.nodeA, minE.nodeB);
            result += minE.weight;
            edge++;
        }
    }
>    
    printf("%d", result);
>    
    return 0;
}

📄 문제 설명

Problem

N명의 학생들을 키 순서대로 줄을 세우려고 한다.
일부 학생들의 키만을 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

Input

첫째 줄 : N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)
(M은 키를 비교한 회수이다.)
다음 M개의 줄 : 키를 비교한 두 학생의 번호 A, B가 주어진다.
(학생 A가 학생 B의 앞에 서야 한다는 의미 / 학생들 번호는 1번 ~ N번)

Output

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력
(답이 여러 가지인 경우에는 아무거나 출력)

Example Input 1

3 2
1 3
2 3

Example Output 1

1 2 3

Example Input 2

4 2
4 2
3 1

Example Output 2

4 2 3 1

📝 문제 해설

이 문제는 두 학생의 키를 비교한 m개의 결과를 가지고 키 순서 결과를 출력하는 프로그램이다.
>
키가 작은 사람 뒤에 키가 큰 사람이 나열되어 한 방향으로 연결이 된다.
따라서 <위상정렬>을 사용해 문제를 해결하였다.

▶ 위상정렬 (Topological Sort)

DAG(Directed Acyclic Graph)에서 그래프의 방향성을 거스르지 않고, 정점들을 나열하는 것
* DAG : 비순환 방향 그래프 (순환을 가지지 않는)
>
- 위상정렬은 각 정점을 우선순위에 따라 배치한 것.
- 일반적으로 위상정렬의 결과는 유일하지 않다.

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
>
    vector<int> student;
    vector<vector<int>> graph;
>
    for (int i = 0; i <= n; i++) {
        student.push_back(0);
        vector<int> a;
        graph.push_back(a);
    }
>
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
>
        student[b] ++;
        graph[a].push_back(b);
    }
>
    queue<int> q;
>
    for (int i = 1; i <= n; i++) {
        if (student[i] == 0) {
            q.push(i);
        }
    }
>
    while (!q.empty()) {
        int front = q.front();
        q.pop();
>
        printf("%d ", front);
>
        for (int i = 0; i < graph[front].size(); i++) {
            if (--student[graph[front][i]] == 0) {
                q.push(graph[front][i]);
            }
        }
    }
 >   
    return 0;
}

📄 문제 설명

Problem

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.
여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려 한다.
>
집합을 표현하는 프로그램을 작성하시오.

Input

첫째 줄 : n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)
        (m은 입력으로 주어지는 연산의 개수)
다음 m개의 줄 : 각각의 연산이 주어진다.
- 0 a b의 형태 : 합집합 연산
        a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합치는 연산.
>
- 1 a b 형태 : 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산
          이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.
>
(a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.)

Output

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다.
(yes/no 를 출력해도 된다)

Example Input 1

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

Example Output 1

NO
NO
YES

📝 문제 해설

이 문제는 주어진 원소들이 같은 집합안에 포하되어 있는지 확인하는 문제로
<Union Find>를 활용해 해결하였다.

▶ 서로소 집합 (Disjoint Set, Union-Find)

교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조
>
- Union 연산 : 
    어떤 두 원소 a, b에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산
>
- Find 연산 :
    어떤 원수 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환

서로소 집합 표현

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
int n, m;
vector<int> parent;
>
void init() {
    for (int i = 0; i <= n; i++) {
        parent.push_back(i);
    }
}
>
int find(int a) {
    if (parent[a] == a)return a;
    return parent[a] = find(parent[a]);
}
>
void unionF(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    parent[pb] = pa;
}
>
int main() {
    scanf("%d %d", &n, &m);
>
    init();
>
    for(int i = 0; i < m; i++){
        int cmd, a, b;
        scanf("%d %d %d", &cmd, &a, &b);
>        
        if (cmd == 0) {
            unionF(a, b);
        }
        else {
            if (find(a) == find(b)) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
    }
 >   
    return 0;
}

📄 문제 설명

Problem

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
>
상덕이가 털 보석점에는 보석이 총 N개 있다.각 보석은 무게 Mi와 가격 Vi를 가지고 있다.
상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다.
가방에는 최대 한 개의 보석만 넣을 수 있다.
>
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄 : 각 보석의 정보 Mi와 Vi (0 ≤ Mi, Vi ≤ 1,000,000)
다음 K개 줄 : 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
>
모든 숫자는 양의 정수이다.

Output

첫째 줄 : 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

Example Input 1

2 1
5 10
100 100
11

Example Output 1

10

Example Input 2

3 2
1 65
5 23
2 99
10
2

Example Output 2

164

📝 문제 해설

이 문제는 주어진 보석의 무게와 가치를 고려해 주어진 가방 안에 최대 하나의 보석을 넣어
최대 가치를 만들어 내는 문제이다.
>
우선순위 큐를 활용해 문제를 해결하였다.

문제 해결 순서

1. 보석의 무게(weight)와 가치(value)를 가지고 있는 Jewerly 구조체 생성
2. Jewerly type의 벡터 jew와 가방의 정보를 가지고 있는 벡터 bag 선언
>
3. jew는 무게를 기준으로, bag은 수용크기 기준으로 오름차순 정렬
>
4. 가치가 높은 보석이 우선순위를 갖는 우선순위 큐(pq) 생성
>
5. bag을 순서대로 탐색하며 수용크기보다 작거나 같은 보석을 while문으로 순회하며 pq에 삽입
  (수용 크기보다 더 큰 보석을 만나면 while문을 탈출하게 된다.)
6. pq의 top에는 무게가 수용크기보다 작거나 같은 보석 중 가치가 가장 큰 보석.
7. pq top 삭제
>
8. jew와 bag 벡터가 empty()가 아닐 때까지 5 ~ 7 반복

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
struct Jewerly{
    int weight;
    int value;
};
>
bool weightComp(const Jewerly& a, const Jewerly&b){
    return a.weight < b.weight;
}
>
struct valueComp{
    bool operator()(const Jewerly& a, const Jewerly& b){
        return a.value < b.value;
    }
};
>
int main(){    
    int n, k;
    scanf("%d %d", &n, &k);
>    
    vector<Jewerly> jew;
    vector<int> bag;
>    
    for(int i = 0; i < n; i++){
        int m, v;
        scanf("%d %d", &m, &v);        
        jew.push_back({m, v});
    }
>    
    for(int i = 0; i < k; i++){
        int c;
        scanf("%d", &c);        
        bag.push_back(c);    
    }
>        
    sort(jew.begin(), jew.end(), weightComp);
    sort(bag.begin(), bag.end());
>    
    long long int result = 0;
    priority_queue<Jewerly, vector<Jewerly>, valueComp> pq;
>    
    int bagIdx = 0;
    for(int i = 0; i < bag.size(); i++){
        while(bagIdx < n & jew[bagIdx].weight <= bag[i]){
            pq.push(jew[bagIdx]);
            bagIdx++;
        }
>        
        if(!pq.empty()){
            result += pq.top().value;
            pq.pop();
        }
    }    
>    
    printf("%lld", result);
>    
    return 0;
}

📄 문제 설명

Problem

<가운데를 말해요>
>
: 정수 하나씩 외칠 때마다 지금까지 나온 수 중 중간값을 말하는 게임.
만일, 외친 정수의 개수가 짝수개라면 중간에 있는 두 수 중 작은 수를 말해야한다.

Input

첫째 줄 : 정수의 개수 N (1 ≤ N ≤ 100,000)
다음 N개의 줄 : N개의 정수가 차례대로 주어진다. (-10,000 ≤ 정수 ≤ 10,000)

Output

한 줄에 하나씩 N줄에 걸쳐 <가운데를 말해요 게임>의 말해야하는 수를 순서대로 출력한다.

Example Input 1

7
1
5
2
10
-99
7
5

Example Output 1

1
1
2
2
2
2
5

📝 문제 해설

이 문제는 N개의 수가 주어지는데 주어질 때마다 중간값을 출력하는 문제이다.
>
우선순위 큐로 최대힙(maxHeap)과 최소힙(minGeap)을 만들어 해결하였는데,
문제 해결을 위해 지켜주어야할 규칙이 두가지 있다.
>
1. maxHeap의 size가 minHeap의 size보다 크거나 같아야한다.
2. maxHeap의 top이 minHeap의 top보다 커야한다.
  (만일, maxHeap의 top이 더 큰 경우 swap)
>
해당 조건을 만족한다면 항상 maxHeap의 top이 중간 값이 된다.

예를 들어, n이 7이고 정수가 순서대로 1 5 2 10 -99 7 7 일 때 아래와 같다.

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
int main() {    
    int n;
    scanf("%d", &n);
>    
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
>    
    for(int i = 0; i < n; i++){
        int x;
        scanf("%d", &x);
>        
        if(maxHeap.size() <= minHeap.size()){
            maxHeap.push(x); 
        }
        else{
            minHeap.push(x);
        }
>        
        while(!minHeap.empty() && maxHeap.top() > minHeap.top()){
            int max = maxHeap.top();
            int min = minHeap.top();
>             
            maxHeap.pop();
            minHeap.pop();
>            
            maxHeap.push(min);
            minHeap.push(max);
        }
>        
        printf("%d\n", maxHeap.top());
>        
    }
>    
    return 0;
}

📄 문제 설명

Problem

이중 우선순위 큐(dual priority queue)
-> 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조
>
전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라
우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다.
>
이중 우선순위 큐는 <데이터 삽입 연산>과 <데이터 삭제 연산>이 가능하다.
>
데이터를 삭제하는 연산은 또 두 가지로 구분되는데,
<우선순위가 가장 높은 것>을 삭제하는 연산과
<우선순위가 가장 낮은 것>을 삭제하는 연산이다. 
>
예를 들어, 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자.
Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 
>
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후
최종적으로 Q에 저장된 데이터 중 <최댓값>과 <최솟값>을 출력하는 프로그램을 작성하라.

Input

첫 번째 줄 : 입력 테스트 데이터의 수를 나타내는 정수 T
각 테스트 데이터의 첫째 줄 : Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)
다음 k 줄 : 연산을 나타내는 문자('D' 또는 'I')와 정수 n
>
('I n'은 정수 n을 Q에 삽입하는 연산이며, 동일한 정수가 삽입될 수 있다.)
('D 1'는 Q에서 최댓값을 삭제 / 'D -1'는 Q 에서 최솟값을 삭제하는 연산이다.)
(최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제된다.)
>
만약 Q가 비어있다면 ‘D’ 연산은 무시해도 좋다.
Q에 저장될 모든 정수는 32-비트 정수

Output

테스트 데이터에 대해, 모든 연산 처리 후 Q에 남아 있는 값 중 <최댓값>과 <최솟값>을 출력.
두 값은 한 줄에 출력하되 하나의 공백으로 구분. 만약 Q가 비어있다면 <"EMPTY">를 출력하라.

Example Input 1

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

Example Output 1

EMPTY
333 -45

📝 문제 해설

이 문제는 명령 문자가 I일 때는 값 삽입을,
D일 때 값이 1이라면 최댓값을 -1이라면 최솟값 삭제하는 문제이다.
>
동일한 정수가 삽입될 수 있다는 점에서 <multiset>을 활용해 해결하였다.

▶ multiset

multiset은 set과 거의 비슷하지만, set과 달리 <중복된 key값>을 허용하는 컨테이너이다.
또한, 원소를 삽입시에 자동으로 정렬이 된다.

#include <bits/stdc++.h>
>
using namespace std;
>
int main() {
>    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
>    
    int t;
    cin >> t;
>    
    for(int i = 0; i < t; i++){
        int k;
        cin >> k;
>        
        multiset<int> ms;
>        
        for(int j = 0; j < k; j++){
            char c;
            int x;
            cin >> c >> x;
>        
            if(c == 'I'){
                ms.insert(x);
            }
            else if(c == 'D'){
                if(!ms.empty()){
                    if(x == 1){
                        // 최댓값 삭제
                        ms.erase(--ms.end());
                    }
                    else{
                        // 최솟값 삭제 
                        ms.erase(ms.begin());
                    }
                }
            }
        }
>        
        if(ms.empty()){
            cout << "EMPTY\n";
        }
        else{
            cout << *(--ms.end()) << " " << *(ms.begin()) << "\n";
        }
    }
>
    return 0;
}

📄 문제 설명

Problem

N개의 수 A[1], A[2], ..., A[N]과 L이 주어진다.
D[i]는 A[i-L+1] ~ A[i] 값 중 최솟값일 때, D[i]를 출력하는 프로그램을 작성하시오.
(이때, i ≤ 0 인 A[i]는 무시하고 D를 구해야 한다.)

Input

첫째 줄 : N과 L(1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄 : N개의 수 (-10^9 ≤ Ai ≤ 10^9)

Output

첫째 줄에 D[i]를 공백으로 구분하여 순서대로 출력한다.

Example Input 1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

Example Output 1

1 1 1 2 2 2 2 2 3 3 2 2

📝 문제 해설

이 문제는 i가 [0]~[N-1]일 때 [i-l+1]~[i] 범위안의 최솟값을 출력하는 문제이다.
가장 작은 값이 필요하므로 우선순위 큐(Priority Queue)를 사용해서 문제를 해결하였다.

▶ 우선순위 큐(Priority Queue)

Queue는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out)형태의 자료구조이다.

반면, Priority Queue는 <우선순위가 높은 데이터>가 먼저 나가는 형태의 자료구조로 
내부적으로 힙(Heap)과 유사하게 구현되어 있으며, 우선순위가 가장 높은 값이 top을 유지한다.

priority_queue reference

// 1. Top이 가장 큰 수 (우선순위가 큰 수일 때)
priority_queue<int, vector<int>, less<int>> pq;
>
>
// 2. Top이 가장 작은 수(우선순위가 작은 수일 때)
priority_queue<int, vector<int>, greater<int>> pq;
>
>
// 3. 우선순위 재정의하여 사용 (Custom 우선순위)
struct compare{
    bool operator()(int a, int b){
        return a < b; // Top이 가장 작은 수
        // return a > b; // Top이 가장 큰 수
    }
};
>
priority_queue<int, vector<int>, compare> pq;

다시 문제로 돌아와서,

우선순위 큐를 만들어 값을 넣다보면 범위 외 값이 섞이는 경우가 생긴다.
이를 처리할 수 있도록 값(value)과 위치(idx)정보를 저장하고 있는 구조체(Data)를 만든다.

여기서 작은 값이 되지않는 큰 값들은 pop()해줄 필요가 없다는 것이다.
따라서, 가장 작은 값의 위치(pq.top().idx)가 범위 안([i-l+1] ~ [i])에 있는지 확인하고
범위 바깥 값을 pop() 해주고, 가장 작은 값(pq.top().value)을 프린트해주면 된다.

⚠ scanf() / printf() 시간초과 ?

⚠ 평소 데이터 입출력 시에 C표준 입출력 함수 scanf() / printf()를 사용하는데,
해당 문제는 오히려 위의 입출력 사용시에 시간 초과가 난다.
>
따라서 cin과 cout을 사용해도 입출력 속도를 높일 수 있는 아래 코드 사용.

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

🔹 ios::sync_with_stdio(false);
// true : 동기화 상태가 default
>
C와 C++ 입출력 방식을 제한없이 섞어 쓸 수 있어 C++ 버퍼(iostream)와 C의 버퍼(stdio)를
모두 사용하고 동기화가 되어 있어 delay가 발생하는데, 위의 코드로 동기화를 끊을 수 있다.
즉 C와 C++의 버퍼가 서로 독립되어 사용하는 버퍼 수가 줄어들고 속도가 향상된다.

🔹 cin.tie(NULL); cout.tie(NULL);
// cin과 cout이 서로 tie가 되어 있는 상태가 default
>
---------------------------
std::cout << "Enter name:";
std::cin >> name;
---------------------------
>
✔ tie 
cin, cout이 묶여있으며 다른 스트림에서 입출력 작업을 하기전에 자동으로 flush(콘솔에 표시)
-> "Enter name" 먼저 출력 이후 입력 받음
>
✔ untie 
입출력 작업 하기 전에 자동 flush(콘솔에 표시)에 신경쓰지 않는다.
버퍼가 가득 차거나 수동적으로 flush 시켜주기 전까지는 출력되지 않는다.
-> 입력 이후 "Enter name"이 출력될 수 있음

⚠ 주의 사항
1. C의 버퍼와 C++버퍼가 별개로 독립되기 때문에 scanf, printf, getchar같은
C의 입출력 함수와 cin, cout을 섞어쓰면 입출력의 순서가 올바르지 않게 나올 수 있다.
2. 멀티 쓰레드 환경에서 예상하지 못한 결과가 도출될 수 있다. (싱글쓰레드 사용)

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
struct Data{
    int idx;
    int value;
};
>
struct Comp{
    bool operator()(const Data& a, const Data& b){
        return a.value > b.value;
    }
};
>
int main() {    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
>    
    int n, l;
    cin >> n >> l;
>    
    priority_queue<Data, vector<Data>, Comp> pq;
>    
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
>        
        pq.push({i, x});
>        
        while(pq.top().idx < i - l + 1){
            pq.pop();
        }
>        
        cout << pq.top().value << ' ';    
    }
    return 0;
}

📄 문제 설명

Problem

이진 트리를 입력받아
- 전위 순회(preorder traversal)
- 중위 순회(inorder traversal)
- 후위 순회(postorder traversal) 결과를 출력하는 프로그램작성하시오.

Input

첫째 줄 : 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)
다음 N개 줄 :각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드
노드의 이름은 A부터 차례대로 영문자 대문자 (항상 A가 루트 노드)
자식 노드가 없는 경우에는 .으로 표현된다.

Output

첫째 줄 : 전위 순회
둘째 줄 : 중위 순회
셋째 줄 : 후위 순회 결과를 출력한다.
각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

Example Input 1

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

Example Output 1

ABDCEFG
DBAECFG
DBEGFCA

📝 문제 해설

이 문제는 왼쪽 자식과 오른쪽 자식을 갖는 node라는 구조체를 만들어 해결하였다.
전위/중위/후위 순회는 재귀를 이용하며, 각 순회마다 출력과 재귀호출 순서를 조절하면 된다.

</> Source Code

#include <bits/stdc++.h>
#define MAX 26
>
using namespace std;
>
struct node{
    char left;
    char right;
};
>
vector<node> v(MAX);
>
void preOrder(char node){ // 전위 순회
    // root - left - right
    if(node == '.') return;
>    
    printf("%c", node);
    preOrder(v[node].left);
    preOrder(v[node].right);
}
>
void inOrder(char node){ // 중위 순회
    // left - root - right
    if(node == '.') return;
>    
    inOrder(v[node].left);
    printf("%c", node);
    inOrder(v[node].right);
}
>
void postOrder(char node){ // 후위 순회
    // left - right - root
    if(node == '.') return;
>    
    postOrder(v[node].left);
    postOrder(v[node].right);
    printf("%c", node);
}
>
int main(){    
    int n;
    scanf("%d", &n);
>    
    char rt, l, r;
    for(int i = 0; i < n; i++){
        cin >> rt >> l >> r;        
        v[rt].left = l;
        v[rt].right = r;
    }
>    
    preOrder('A');
    printf("\n");
>    
    inOrder('A');
    printf("\n");
>    
    postOrder('A');
>    
    return 0;
}

📄 문제 설명

Problem

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
>
명령은 총 여섯 가지이다.
>
- push X: 정수 X를 큐웨 넣는 연산
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
      (만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력)
- size: 큐에 들어있는 정수의 개수를 출력
- empty: 큐가 비어있으면 1, 아니면 0을 출력
- front: 큐의 가장 앞에 있는 정수를 출력
      (만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력)
- back: 큐의 가장 뒤에 있는 정수를 출력
      (만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력)

Input

첫째 줄 : 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)
다음 N개 줄 : 명령과 필요시에 정수
            (주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.)

Output

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

Example Input 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

Example Output 1

1
2
2
0
1
2
-1
0
1
-1
0
3

📝 문제 해설

▶ Queue (큐)

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
int main() {
>
    queue<int> q;
>
    int n;
    scanf("%d", &n);
>
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "push") {
            int x;
            scanf("%d", &x);
            q.push(x);
        }
        else if (s == "pop") {
            int front = -1;
            if (!q.empty()) {
                front = q.front();
                q.pop();
            }
            printf("%d\n", front);
        }
        else if (s == "size") {
            printf("%d\n", q.size());
        }
        else if (s == "empty") {
            int empty = 0;
            if (q.empty()) {
                empty = 1;
            }
            printf("%d\n", empty);
        }
        else if (s == "front") {
            int front = -1;
            if (!q.empty()) {
                front = q.front();
            }
            printf("%d\n", front);
        }
        else if (s == "back") {
            int back = -1;
            if (!q.empty()) {
                back = q.back();
            }
            printf("%d\n", back);
        }
>
    }
    return 0;
}

📄 문제 설명

Problem

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하라
>
명령은 총 다섯 가지이다.
>
- push X: 정수 X를 스택에 넣는 연산
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력
      (만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력)
- size: 스택에 들어있는 정수의 개수를 출력
- empty: 스택이 비어있으면 1, 아니면 0을 출력
- top: 스택의 가장 위에 있는 정수를 출력
      (만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력)

Input

첫째 줄 : 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)
다음 N개 줄 : 명령과 필요시에 정수
            (주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.)

Output

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

Example Input 1

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

Example Output 1

2
2
0
2
1
-1
0
1
-1
0
3

Example Input 2

7
pop
top
push 123
top
pop
top
pop

Example Output 2

-1
-1
123
123
-1
-1

📝 문제 해설

▶ Stack (스택)

</> Source Code

#include <bits/stdc++.h>
>
using namespace std;
>
int main() {
>
    stack<int> st;
>
    int n;
    scanf("%d", &n);
>
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
>
        if (s == "push") {
            int x;
            scanf("%d", &x);
            st.push(x);
        }
        else if (s == "pop") {
            int top = -1;
            if (!st.empty()) {
                top = st.top();
                st.pop();
            }
            printf("%d\n", top);
        }
        else if (s == "size") {
            printf("%d\n", st.size());
        }
        else if (s == "empty") {
            int empty = 0;
            if (st.empty()) {
                empty = 1;
            }
            printf("%d\n", empty);
        }
        else if (s == "top") {
            int top = -1;
            if (!st.empty()) {
                top = st.top();
            }
            printf("%d\n", top);
        }
>        
    }
    return 0;
}