[백준]15666 - N과 M (12)

고려사항

객체지향설계 수업을 듣게 되었고, 전에 C언어 수업을 듣지 않은 나는 어떠한 대책을 강구해야만 했다.

이에 python으로 풀던 매일의 알고리즘 문제를 c++로 적절히 변환하여 자연스럽게 접해보려고 한다.

원래의 python 코드

#S2_15666_N과 M (12)

def bt(n,m,a,s,seq,res):
  if len(seq)==m:
    res.append(seq)
    return

  prev=-1
  for i in range(s,n):
    if prev!=a[i]:
      bt(n,m,a,i,seq+[a[i]],res)
      prev=a[i]

  return res

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
res=bt(n,m,a,0,[],[])

for i in res:
  print(" ".join(map(str,i)))

---

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void bt(int n, int m, vector<int>& a, int s, vector<int>& seq, vector<vector<int>>& res) {
    if (seq.size()==m) {
        res.push_back(seq);
        return;
    }
    
    int prev=-1;
    for (int i=s; i<n; i++) {
        if (prev != a[i]) {
            seq.push_back(a[i]);
            bt(n,m,a,i,seq,res);
            seq.pop_back();
            prev=a[i];
        }
    }
}

int main() {
    int n,m;
    cin >> n >> m;
    
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end());
    
    vector<vector<int>> res;
    vector<int> seq;
    
    bt(n,m,a,0,seq,res);
    
    for (const auto& r:res) {
        for (int i=0; i<r.size(); i++) {
            if (i>0) cout << " ";
            cout << r[i];
        }
        cout << "\n";
    }
    
    return 0;
}

헤더 파일들

#include <iostream>
#include <vector>
#include <algorithm>

*헤더 파일: C나 C++에서 자주 사용되는 함수, 상수, 데이터 타입, 클래스 등을 미리 선언해 놓은 파일로, 코드의 재사용성을 높이고 복잡한 프로그램의 모듈화를 도움. java나 python에서는 import로 패키지나 모듈을 불러옴. 비슷한 느낌인 듯.

• <iostream>: c++에서 표준 입력을 이용하기 위함.
• <vector>: 벡터를 사용하기 위함. java의 ArrayList와 유사하다고 함.
• <algorithm>: 정렬같은 알고리즘 함수를 사용하기 위함. 이 코드에서는 sort()때문에 사용.
  
  
  
  

네임스페이스

using namespace std;

C++에서 std는 표준 라이브러리의 모든 구성 요소들이 포함된 네임스페이스.

자주 사용하는 cin, cout, vector, sort 등을 사용할 때마다 std::를 붙여야 하는데, 이 코드는 using namespace std;를 통해 이를 생략하고 사용할 수 있게 함.

• 왜 std::를 붙여야 하는가?: 표준 라이브러리의 모든 요소들을 별도의 공간(std)에 배치하여 사용자가 정의한 다른 이름과 충돌하지 않도록 함. 표준 라이브러리의 함수를 사용할 때, 그 함수가 std 네임스페이스에 속해 있음을 명확히 할 수 있음.
• 네임스페이스가 무엇인가?: C++에서 이름의 충돌을 방지하기 위한 개념으로, 서로 다른 코드에서 동일한 이름의 함수, 변수, 클래스 등을 구분하기 위해 사용.
• java와 python과의 비교
  • Java: Java에는 네임스페이스라는 개념 대신 패키지(package)가 있음. 클래스나 메소드 이름 충돌을 피하기 위해 패키지를 사용하며, java.util.List와 같이 명시적으로 사용.
  • Python: Python에서는 모듈 자체가 네임스페이스 역할을 함. import로 모듈을 불러오고 math.sqrt처럼 모듈명 뒤에 점을 붙여서 접근할 수 있음. from math import sqrt처럼 부분적으로 가져올 수도 있음.

백트래킹 함수

void bt(int n, int m, vector<int>& a, int s, vector<int>& seq, vector<vector<int>>& res) {
    if (seq.size()==m) {
        res.push_back(seq);
        return;
    }
    
    int prev=-1;
    for (int i=s; i<n; i++) {
        if (prev != a[i]) {
            seq.push_back(a[i]);
            bt(n,m,a,i,seq,res);
            seq.pop_back();
            prev=a[i];
        }
    }
}

백트래킹이 쓰이긴 했는데 일단 C++ 자체에 집중하기로…

void bt(int n, int m, vector<int>& a, int s, vector<int>& seq, vector<vector<int>>& res) {
    // 함수 본문
}

• C++에서는 함수의 반환형을 명시해야 함 (void, int 등).
• C++에서는 변수를 참조로 전달할 때 참조자인 & 기호를 사용하여 참조(레퍼런스)를 나타냄. 이는 함수가 인자를 직접 수정할 수 있게 해줌.
• Java에서도 함수의 반환형을 명시해야 하며, public, private 같은 접근 제어자가 필요함. Java에서는 참조(레퍼런스) 개념이 있지만, 기본 자료형(primitive type)은 값에 의한 호출, 객체는 참조에 의한 호출임.
• Python에서는 함수 정의에 반환형을 명시하지 않으며, 함수는 기본적으로 객체나 값을 반환함. 모든 변수는 참조에 의한 호출이 기본이며, def 키워드를 사용해 함수를 정의함.

벡터

vector<int> a(n); // 크기가 n인 벡터 선언
vector<vector<int>> res; // 2차원 벡터 선언

• 위 방식으로 선언(크기 명시 없이 선언 가능)
• <> 이렇게 표현하는게 자바 제네릭 느낌

조건문

    if (seq.size()==m) {
        res.push_back(seq);
        return;
    }
    
    int prev=-1;
    for (int i=s; i<n; i++) {
        if (prev != a[i]) {
            seq.push_back(a[i]);
            bt(n,m,a,i,seq,res);
            seq.pop_back();
            prev=a[i];
        }
    }

• 조건문 괄호로 묶고 중괄호 {} 사용으로 블록 명시
• 배열 요소 접근 방식도 비슷한 듯
• push_back: vector같은 동적 배열에 새로운 요소를 추가, 벡터의 크기 증가시킴.
• pop_back: 벡터의 마지막 요소를 제거함. Python에서 list.pop()과 유사하고, Java에서는 remove(size() - 1)과 같은 동작을 수행.

main 함수

int main() {
    int n,m;
    cin >> n >> m;
    
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end());
    
    vector<vector<int>> res;
    vector<int> seq;
    
    bt(n,m,a,0,seq,res);
    
    for (const auto& r:res) {
        for (int i=0; i<r.size(); i++) {
            if (i>0) cout << " ";
            cout << r[i];
        }
        cout << "\n";
    }
    
    return 0;
}

• cin » n » m;: 표준 입력으로 두 개의 값을 입력 받음
  • cin
    • C++ 표준 입력 스트림으로, 콘솔로부터 데이터를 입력받는 데 사용됨.
    • character input의 약자. 표준 입력(stdin)에서 데이터를 읽음.
    • Python에서는 input() 함수, Java에서는 Scanner 클래스의 nextInt()와 비슷한 역할
  • >> 연산자 (추출 연산자, Extraction Operator)
    • cin과 함께 사용하여 입력받은 값을 변수에 저장하는 역할
    • 입력된 값을 오른쪽에 있는 변수로 추출한다는 의미에서 »를 사용함.
    • 위 코드의 경우 사용자가 n,m을 공백이나 줄바꿈으로 구분하여 입력하면 n,m 순서로 각각에 할당됨.
• sort(a.begin(), a.end());: 두 개의 iterator입력받아서 구간내의 요소를 오름차순으로 정렬함.
• for (const auto& r : res)
  • for문이 참 특이하게 생겼다고 느꼈음.
  • Python의 for element in list처럼 컨테이너의 각 요소를 자동으로 순회함.
  • const auto&
    • const: 읽기 전용임을 의미. r을 수정할 필요가 없기 때문에 사용.
    • auto&: 자동으로 r의 타입을 추론하고, 참조로 받음. 여기서는 r이 벡터의 참조가 됨.
  • python으로 치면 ‘for r in res:’ 느낌
• if (i > 0) cout « ” “;
  • 인덱스가 0보다 클 때만 공백을 출력하므로, 첫 번째 숫자 앞에는 공백이 출력되지 않도록 함.
  • python으로 치면 ‘if i > 0: print(“ “, end=””)’
  • 출력 연산자 (<<): 삽입 연산자(Insertion Operator)로, cout을 통해 출력할 데이터를 전달
  • 연산자를 연속으로 사용하여 여러 데이터를 한 번에 출력할 수 있음

    #include <iostream>
    using namespace std;
    
    int main() {
    int x = 10;
    cout << "Value of x is: " << x << "\n"; // Value of x is: 10
    return 0;
      }
    

return 0;

• 반드시 사용해야 하는가? -> 그건 아님
• C++ 표준에 따르면, main 함수에서 return 0;을 명시적으로 적지 않더라도, 컴파일러는 암묵적으로 return 0;을 추가해줌.
• main 함수가 끝까지 실행되면 자동으로 0을 반환함.

ETC

Buddy-Virty 음성인식 테스트 이후로 Xcode를 오랜만에 써봤다.