inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

묻고 답해요

176만명의 커뮤니티!! 함께 토론해봐요.

조합 시간복잡도 질문

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 강사님, 강의 잘 듣고 있습니다. 조합을 구하는 함수의 시간복잡도에 대해 질문 드리고 싶습니다. // Online C++ compiler to run C++ program online #include <iostream> #include <vector> using namespace std; int r=0; vector<int> t; int cnt=0; int forcount=0; void combi(int idx) { if(t.size()==r) { cnt++; return; } for(int i=idx; i<=10; i++) { forcount++; t.push_back(i); func(i+1); t.pop_back(); } } int main() { // Write C++ code here while(true){ cnt=0; forcount=0; cin>>r; func(1); cout<<"cnt = "<<cnt<<"\n"; cout<<"forcount = "<<forcount; } return 0; } 조합 함수의 시간복잡도는 O(nCr), 위의 함수에서는 cnt의 값이라고 알고 있습니다. 그런데, 시간복잡도는 주어진 입력의 크기에 대한 연산의 총합이라고 알고 있습니다. 그러면, combi 함수의 for문 연산의 수인 forcount도 고려해야 하지 않나요? 왜? cnt만 고려해도 되는지 궁금합니다.

  • c++
  • 코딩-테스트
lego0313 댓글 2 좋아요 0 조회수 592

리턴 값으로 초기화 시 복사 생성자 호출이 안됩니다.

미해결

홍정모의 따라하며 배우는 C++

#include<iostream> #include<cassert> using namespace std; class Fraction { private: int m_numerator; int m_dominator; public: Fraction(int numerator, int dominator) :m_numerator(numerator), m_dominator(dominator) { assert(dominator != 0); } Fraction(const Fraction& fraction) :m_numerator(fraction.m_numerator) , m_dominator(fraction.m_dominator) { assert(fraction.m_dominator != 0); cout << "Copied" << endl; } friend std::ostream & operator << (std::ostream& out, const Fraction& fr) { out << fr.m_numerator << " / " << fr.m_dominator << endl; return out; } }; Fraction doSomething() { Fraction temp(1, 2); cout << &temp << endl; return temp; } int main() { //return값 복사 Fraction fr = doSomething(); cout << &fr << endl; return 0; } 위 코드에서 복사 생성자를 호출하지 않는 이유는 뭘까요? 사용환경에 따라서 rvo를 시켜주는건가요??

  • c++
지우 댓글 1 좋아요 2 조회수 233

9.12 강의 마지막에 내주신 숙제가 잘 이해가 안갑니다.

해결됨

홍정모의 따라하며 배우는 C++

대입연산자를 오버로딩 해보라고 말씀하셨는데 대입연산자를 이용해서 이니셜라이저리스트로 클래스를 생성해보란 말씀이신가요? 근데 그건 이미 교수님이 강의 마지막에 되는걸 보여주신거 아닌가요?

  • c++
안규철 댓글 1 좋아요 1 조회수 289

기존 C++ 시리즈와 현재시리즈중 우선순위

미해결

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버

[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] 와 비교해서 현재 시리즈를 먼저 진행하고 하는것이 알맞은 순서일까요? 이전 C++ 언리얼 MMO 과정에는 어셈블리도 다루고 좀더 딥하게 다루던걸로 기억해서 여쭈어봅니다

  • c++
  • 네트워크
  • ue-blueprint
  • 게임수학
  • windows-api
김망 댓글 1 좋아요 0 조회수 488

3.3 강의 후위 연산 질문

미해결

홍정모의 따라하며 배우는 C++

먼저 강의 정말 유익하게 잘 보았습니다. 본론으로 들어가면 선생님께서는 전위 연산을 사용하였더니 4라는 결과가 나왔지만 후위 연산을 사용하니깐 결과값이 3이 나왔습니다. 여기서 a는 2가 되는 것이 이해가 되지만 b는 왜 1이 되는지 의문이여서 질문글을 남깁니다.

  • c++
원인석 댓글 1 좋아요 1 조회수 228

강의 20:30에서 GameObject.h을 pch.h에서 헤더로 선언하지 않은 이유?

미해결

[게임 프로그래머 도약반] DirectX11 입문

안녕하세요 선생님, 강의를 듣다가 궁금증이 생겨 질문 남깁니다.강의의 20:30 부분에서 다른 클래스들과는 달리 GameObject 클래스는 왜 pch.h 파일에 헤더로 선언하여 사용하지 않는 것인지 궁금합니다.

  • c++
  • directx
댓글 1 좋아요 0 조회수 309

2-T. 번 강의 질문 스택 풀이시 시간복잡도

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요. 강의 잘듣고잇습니다. 단순하게 풀엇을떄 2중 forloop 시간복잡도 O(N^2) . 시간초과 발생하였습니다. 스택 풀이로 하면 통과는 하게되는데, 시간복잡도는 여전히 O(N^2). 인 것 아닌가요?

  • c++
  • 코딩-테스트
윽쓰욱스 댓글 3 좋아요 0 조회수 364

제 코드에서 잘못된 부분을 알고 싶습니다!

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 선생님, http://boj.kr/eabdc120ede54df9bf4da138381baa63 2870 번 수학숙제 문제를 풀어봤습니다. 입력받은 문자열에서 알파벳은 모두 '*' 로 바꾸고, 변경된 문자열을 토대로 재귀 함수를 이용하여 정수 부분을 추출하려고 하였으나, 어째서인지 문자열의 첫 번째 정수만 출력되고, 두번째 정수는 출력되지 않습니다. 예를들어, "lo3za4" 라는 입력값이 들어가면, 출력으로 첫 번째 정수인 3만 출력되고, 4는 출력되지 않습니다. 어느 부분에서 어떤 실수가 있는지 알려주시면 감사하겠습니다. 좋은 강의 늘 감사드립니다.

  • c++
  • 코딩-테스트
김영수 댓글 1 좋아요 0 조회수 263

4-C 질문

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 큰돌님 조금 다른 로직으로 풀었는데 TC랑 반례들 다 적용해보아도 다 통과되는데 제출하면 틀렸다고 해서 제가 어느부분을 놓친건지 질문드립니다. 전역변수 저는 연결정보를 다음과 같이 map과 set을 활용하였습니다. const int INF = 987654321; int n{}; int arPopular[15]{}; // 각 구의 인원수 저장 용도 map<int, set<int>> graph{}; // Key : 구. Value : 해당 구랑 연결된 구들 int minDiff = INF; // 나눠진 두 구의 최소 인원수 차이 구현 함수 프로토타입 // Gu - FindNode 가 서로 연결되어 있는지 여부 bool IsConnect(int Gu, int FindNode); // 하나의 구역이 끊김 없이 연결될 수 있는지 bool IsAreaConnected(const vector<int>& Area); // 인구수 차이 구해오기 int GetDifPop(const vector<int>& Area1, const vector<int>& Area2); 일단 저의 로직 순서는 다음과 같습니다. 비트마스킹으로 모든 경우의 수를 탐색한다. 각 경우의 수마다 비트가 0이면 vector1에다가, 1이면 vector2에다가 넣어준다. 여기까지 되었으면 일단 두 그룹으로 나뉘어진다. 각 그룹에 대해서 Union Find 알고리즘을 적용해서 서로 끊기지 않고 연결될 수 있는지 확인한다. 만약 두 그룹 모두 끊기지 않고 연결될 수 있다면 우리가 원하는 2개의 구역으로 나눈것이다. 이하 최소 찾는 로직부터는 동일. 코드 링크는 여기있습니다! http://boj.kr/bbe484bd863f42fbba08a1e48b55dad2

  • c++
  • 코딩-테스트
Park SungEun 댓글 1 좋아요 0 조회수 247

1-H 질문 있습니다!

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

선생님 안녕하세요 ! 제가 푼 문제 코드는 다음과 같습니다. http://boj.kr/3475d11fa8a2499bba282e226bdc5e92 제가 풀었을 떄는 시간초과가 났었습니다. 여기서 여쭤볼 것이 있습니다. Q1. 제가 작성한 코드에서 시간 복잡도를 계산할 떄 최악의 수를 생각하고 계산을 합니다. N이 100,000이고 K는 1일 떄 제가 작성한 코드는 대략 3N의 시간복잡도가 나오는 것으로 계산하였습니다. 또한 선생님의 풀이를 저는 2N의 시간복잡도로 생각을 합니다. 그러면 만일 실전에서 제가 작성한 3N이 시간 초과가 뜬다면 2N으로 줄일 방안을 생각하는 것이 맞을까요?!?

  • c++
  • 코딩-테스트
sangwoo8221 댓글 1 좋아요 0 조회수 287

4-A 질문입니다.

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

안녕하세요 큰돌님. 모든 경우의 수 탐색 과정에서 궁금한게 있어서 질문드립니다. 모든 경우의 수를 탐색하기 + 각 경우의 수에서 합 구하기 를위해 다음과 같은 코드가 구현되는 것은 이해했습니다. for (int i = 1; i < (1 << n); i++) { // i는 모든 경우의 수에서 각 케이스이다. for (int j = 0; j < n; j++) { // i에 해당하는 경우의 수에서 합 구하기위함 if(i & (1<<j)) } } 여기서 질문드리고싶은게 for문에서 i=1 부터 시작하는 이유가 i=0. 즉, 하나도 안고르는 경우는 탐색할 필요가 없기 때문인가요?

  • c++
  • 코딩-테스트
Park SungEun 댓글 1 좋아요 0 조회수 170

교안 p147 내용 질문 있습니다!!

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

선생님 안녕하세요!! 다름이 아니라 p147의 재귀를 이용한 순열에서 코드 질문이 있어 질문 남깁니다.!! swap(a[i], a[depth]); makePermutation(n, r, depth + 1); swap(a[i], a[depth]); 여기서 마지막에 swap함수를 한번 더 사용하는지 이유를 잘 모르겠습니다. 결국에 중간에 재귀함수로 돌면서 종료조건을 지키면 마지막에 swap을 한번 더 하는 의미가 무엇인지 모르겠습니다!! 알려주시면 감사하겠습니다!!!

  • c++
  • 코딩-테스트
sangwoo8221 댓글 2 좋아요 0 조회수 255

5-A 백준 순회공연 질문드립니다.

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pp; typedef map<int,int> m; priority_queue<int, vector<int>,greater<int>> pq; void l(){ cout << "------- " << endl;} int n; vector<pp> v; // day 정렬 bool cSort(const pp &a, const pp &b){ if(a.second != b.second){//sort by day return a.first < b.first; } return a.second > b.second; //sort by money } //input void i(){ cin >> n; int d,p; for(int i=0; i<n; i++){ cin >> p; cin >> d; v.push_back({d,p}); } sort( v.begin(), v.end() ); } //solution void s(){ int money=0; for(pp dp : v){ pq.push(dp.second);//price if(pq.size() > dp.first) pq.pop();// pop } while(!pq.empty()){ money += pq.top(); pq.pop(); } cout << money; } void sol(){ i();s(); } int main() { sol(); return 0; } 위 코드에서 cSort를 써서 소팅 하게 되면 틀리는데 혹시 어떤 문제인지 여쭤봐도 될까요? sort( v.begin(), v.end() ); 평범하게 소팅하면 통과가 되는데, cSort로 order by date, price로 정렬하면 에러가 터집니다.

  • c++
  • 코딩-테스트
euijae.lee0714 댓글 1 좋아요 0 조회수 192

2-L 질문있습니다!

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 스스로 코드를 짜고 틀려서 한자리 입력에서 잘못된 것 같아서 반례를 계속 실행하던 중 특이한 점을 발견했습니다. 반례 중 3 1 1:0 2 1:1 2 2:0 을 사용해서 실행해봤습니다. 이때 제 코드가 계속 올바른 답이 나오지 않아서 선생님이 해주신 코드로 했을 때도 특이하게 실행 결과가 00:00 46:00 다음과 같이 나옵니다. 제출했을 때는 맞았다고 뜨긴합니다... 제가 생각한 예제가 아예 잘못 생각한 예제인지 궁금합니다.

  • c++
  • 코딩-테스트
jjune0427 댓글 1 좋아요 0 조회수 186

다중 상속 시 부모 클래스 간 생성자 호출 순서가 궁금합니다.

해결됨

홍정모의 따라하며 배우는 C++

단일 상속 시에는 member initializer list에서 부모 클래스의 생성자와 멤버 간의 순서를 바꾸어도 무조건 부모 클래스의 생성자가 먼저 호출되었었는데, 다중 상속시에는 어떤 부모 클래스의 생성자가 먼저 호출될 지 궁금해서 테스트를 해봤습니다. // USBDevice의 constructor USBDevice(long id) : m_id(id) { cout << "USB" << endl; } // ~~~ // NetworkDevice의 constructor NetworkDevice(long id) : m_id(id) { cout << "Network" << endl; } 먼저 생성자의 호출 순서를 알 수 있게 간단하게 문자열을 출력하도록 수정하였습니다. class USBNetworkDevice : public USBDevice, public NetworkDevice { public: USBNetworkDevice(long usb_id, long net_id) : USBDevice(usb_id), NetworkDevice(net_id) { } }; 위 코드와 같은 수정하지 않은 상태에서는 USB 가 먼저 출력되고 그 다음 Network 가 출력되었습니다. member initializer list에서 순서를 바꾸어도 똑같았구요. class USBNetworkDevice : public NetworkDevice, public USBDevice { public: USBNetworkDevice(long usb_id, long net_id) : USBDevice(usb_id), NetworkDevice(net_id) { } }; 다음으로는 상속할 클래스를 나열할 때의 순서를 바꾸었더니 Network 가 먼저 출력되고 다음으로 USB 가 출력되었습니다. 상속할 클래스를 나열한 순서에 따라서 생성자의 호출 순서가 바뀐다고 보면 될까요? 아 그리고 이런 생성자 호출 순서를 고려해야 하는 작업이 있나요? 객체지향적으로 설계한다면 생성자의 호출 순서에 따라 결과가 바뀌도록 설계하진 않을 것 같아서요.

  • c++
durams 댓글 2 좋아요 1 조회수 689

9.3 강의 보다가 궁금한 점

미해결

홍정모의 따라하며 배우는 C++

class Cents { private: int m_cents; public: Cents(int cents = 0) { m_cents = cents; } int getCents() const { return m_cents; } int& getCents() { return m_cents; } Cents operator - () const { return Cents(-m_cents); } bool operator ! () const { return (m_cents == 0) ? true : false; } friend std::ostream& operator << (std::ostream &out, const Cents &cents) { out << "(" << cents.m_cents << ")"; return out; } }; int main() { Cents cents1(6); Cents cents2(0); cout << cents1 << endl; cout << cents2 << endl; cout << -cents(-10) << endl; cout << !cents1 << endl; cout << !cents2 << endl; return 0; } // 결과 (6) (0) (10) 0 1 이렇게 1~3번째와 4,5번째가 다른 이유가 궁금합니다.

  • c++
ii00 댓글 1 좋아요 1 조회수 169

1-N 분배법칙 질문

미해결

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

*, %는 연산자 우선순위가 같으니까 6:00 부근쯤 설명한 분배법칙을 적용하려면 해당 코드를 변경(주석처리 부분)해야 하는것 아닌가요? typedef long long ll; ll go(ll a, ll b, ll c) { if (b == 1) { return a % c; } ll ret = go(a, b / 2, c); //ret = (ret * ret) % c; ret = ret % c * ret % c; if (b % 2) { ret = (ret * a) % c; } return ret; }

  • c++
  • 코딩-테스트
댓글 3 좋아요 0 조회수 419

맞왜틀! 반례가 궁금합니다!ㅠㅠ

해결됨

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

http://boj.kr/91c2421aa3ef471eac5950368d3428c1 이렇게 코드를 작성하였더니 주어진 테케가 잘 돌아가는데 틀린 이유가 궁금합니다ㅜㅜ 반례도 생각해보았는데 다 잘 돌아가서 뭐가 문젠지 모르겠어서요ㅠㅠ항상 잘 듣고 있습니당 감사합니다 ㅎㅎ

  • c++
  • 코딩-테스트
밍링 댓글 1 좋아요 0 조회수 239

리소스를 관리하는데 shared_ptr를 써야되는가 RawPointer를 써야되는가 weak_ptr를 써야되는가?

미해결

[게임 프로그래머 도약반] DirectX11 입문

한 GameObject 내부에서 선언되는 Parent, Children와 한 MeshRenderer 내부에서 선언되는 Mesh, Material 등등과 같은 리소스들은 각각 Scene과 ResourceManager내부에서 관리(생성, 파괴)되기 때문에 이런 관리해주는 클래스 에서만 shared_ptr로 생성해주고 다른 클래스 에서는 weak_ptr로 전해받았었습니다. 그런데 문뜩 든 생각이 결국 다른 클래스에서 이런 객체들을 사용하기 위해 프레임마다 weak_ptr::lock을 사용하여 shared_ptr로 만들어서 사용할텐데 이러면 비용 부담이 너무 많이되어 배보다 배꼽이 큰 상황이 발생하는 것 같다는 생각이 들었고 이럴바엔 그냥 왠만한 클래스에선 리소스를 shared_ptr로 선언하고 사용한 후 관리해주는 클래스(Scene, ResourceManager)들에서 삭제될때 여기서도 동시에 shared_ptr를 지워버리는식으로 관리를 해주는게 더 좋을 것 같다고 생각을했는데 과연 옳은 생각인 건가요?

  • c++
  • directx
김도형 댓글 1 좋아요 0 조회수 260

이런 방식으로 로또 번호를 생성하는 것도 랜덤이라고 볼 수 있을까요?

미해결

[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part1: C++ 프로그래밍 입문

void ChooseLotto(int numbers[], int count) { // 랜덤으로 1~45 사이의 숫자 6개.... 중복 없이 int lotto[45]; for (int i = 0; i < 45; i++) { lotto[i] = i + 1; } // 공을 섞는 과정 for (int i = 0; i < 1000; i++) { int randNum1 = rand() % 45; int randNum2 = rand() % 45; Swap(&lotto[randNum1], &lotto[randNum2]); } for (int i = 0; i < count; i++) { numbers[i] = lotto[i]; } } 안녕하세요, 강의 잘 보고 있습니다. 저는 실습 풀이를 이렇게 했는데요. 로또 추첨을 할 때 커다란 통에 공을 집어넣고 6개의 번호가 쓰인 공을 꺼낸다고 하면, 한 번 꺼낸 공은 다시 추첨기에서 나오지 않아야 한다고 생각했습니다. 따라서 1~45의 값이 들어있는 배열을 선언하고, 해당 배열을 rand()와 swap()을 이용해 계속 반복하여 섞어주고, 마지막에 0번~5번 인덱스까지 6개의 수를 numbers 배열에 담아주었습니다. 이런 방식으로 로또 번호를 생성하는 것도 랜덤으로 번호를 생성한 것이라고 볼 수 있을까요?

  • c++
한진성 댓글 2 좋아요 0 조회수 1030

인기 태그

인프런 TOP Writers

주간 인기글