[백준]15666 - N과 M (12)
고려사항Permalink
객체지향설계 수업을 듣게 되었고, 전에 C언어 수업을 듣지 않은 나는 어떠한 대책을 강구해야만 했다.
이에 python으로 풀던 매일의 알고리즘 문제를 c++로 적절히 변환하여 자연스럽게 접해보려고 한다.
원래의 python 코드Permalink
#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++ 코드Permalink
#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;
}
헤더 파일들Permalink
#include <iostream>
#include <vector>
#include <algorithm>
*헤더 파일: C나 C++에서 자주 사용되는 함수, 상수, 데이터 타입, 클래스 등을 미리 선언해 놓은 파일로, 코드의 재사용성을 높이고 복잡한 프로그램의 모듈화를 도움. java나 python에서는 import로 패키지나 모듈을 불러옴. 비슷한 느낌인 듯.
- <iostream>: c++에서 표준 입력을 이용하기 위함.
- <vector>: 벡터를 사용하기 위함. java의 ArrayList와 유사하다고 함.
- <algorithm>: 정렬같은 알고리즘 함수를 사용하기 위함. 이 코드에서는 sort()때문에 사용.
네임스페이스Permalink
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처럼 부분적으로 가져올 수도 있음.
백트래킹 함수Permalink
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 키워드를 사용해 함수를 정의함.
벡터Permalink
vector<int> a(n); // 크기가 n인 벡터 선언
vector<vector<int>> res; // 2차원 벡터 선언
- 위 방식으로 선언(크기 명시 없이 선언 가능)
- <> 이렇게 표현하는게 자바 제네릭 느낌
조건문Permalink
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 함수Permalink
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 순서로 각각에 할당됨.
- cin
- 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;Permalink
- 반드시 사용해야 하는가? -> 그건 아님
- C++ 표준에 따르면, main 함수에서 return 0;을 명시적으로 적지 않더라도, 컴파일러는 암묵적으로 return 0;을 추가해줌.
- main 함수가 끝까지 실행되면 자동으로 0을 반환함.
ETCPermalink
Buddy-Virty 음성인식 테스트 이후로 Xcode를 오랜만에 써봤다.
Leave a comment