안녕하세요 강사님, 강의 잘 듣고 있습니다.AC처럼 테스트케이스가 여러 개 주어질 경우, 제한 시간은 어떻게 고려해야 하는지 질문드리고 싶습니다.예를 들어, 주어진 문제의 제한 시간이 1초라면,테스트 케이스를 다 합해서 1초 안에 처리해야 하는 건지,아니면, 각 케이스를 1초 안에 처리해야 하는 건지 궁금합니다.

안녕하세요 강사님, 강의 잘 듣고 있습니다.조합을 구하는 함수의 시간복잡도에 대해 질문 드리고 싶습니다.// 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만 고려해도 되는지 궁금합니다.

이렇게 for문안에 모두 넣었습니다. 예제 답으로는 154가 뜨지만 채점 시 100점으로 뜨네요. 혹시 문제없는 코드일까요?

function solution(arr) { const strArry = arr.split(""); let answer = []; let i = 0; while (i < strArry.length) { if (strArry[i] === "(") { answer.push(strArry[i]); } else { answer.pop(strArry[i]); } i++; } return answer.length === 0 ? "YES" : "NO"; } //console.log(solution("(()(()))(()")); console.log(solution("(((())))"));

function solution(sum, arr) { let left = 0; let right = 0; let add = 0; let count = 0; while (right < arr.length) { if (add >= sum) { add -= arr[left ++]; } else { add += arr[++right]; } if (add === sum) count++; } return count; } console.log(solution(6, [1, 2, 1, 3, 1, 1, 1, 2]));

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

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

안녕하세요 큰돌님 조금 다른 로직으로 풀었는데 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

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

위 코드에서 for문이 n번 만큼 반복되고 그 안에 있는 while문이 도는 횟수의 총 합이 n번이라고 하셨는데 그렇다면 위 코드의 시간복잡도는 [for문 시간복잡도: o(n)] * [while문의 시간 복잡도 : {o(n-1) + o(n-3) + ... o(1)} ]= o(상수 * n) 이렇게 이해하면 되는 걸까요?

안녕하세요 큰돌님. 모든 경우의 수 탐색 과정에서궁금한게 있어서 질문드립니다. 모든 경우의 수를 탐색하기 + 각 경우의 수에서 합 구하기 를위해 다음과 같은 코드가 구현되는 것은 이해했습니다.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. 즉, 하나도 안고르는 경우는 탐색할 필요가 없기 때문인가요?

package String; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class _01_12_암호_복습 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String s = br.readLine().strip(); s = s.replace('#', '1').replace('*', '0'); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i += 7) { String word = s.substring(i, i + 7); sb.append((char) Integer.parseInt(word, 2)); } System.out.println(sb); br.close(); } } 

tabulation 방식의 Bottom-up은 재귀를 호출하지 않기 때문에 당연히 테케 통과하구요강의를 들었을때도 강사님은 피보나치 코드 그대로 사용하셔서 저도 그대로 제출했는데 시간 초과가 뜹니다... 원래의 코드는 아래와 같구요def climbStairs(self, n): memo = {} if n == 1 or n == 2: return n if n not in memo: memo[n] = self.climbStairs(n-1) + self.climbStairs(n-2) return memo[n]discuss를 참고해서 수정한 코드는 테케를 통과했는데 아래와 같습니다class Solution(object): def climbStairs(self, n): memo = {} return self.dp(n, memo) def dp(self, n, memo): # base cases if n == 1 or n == 2: return n if n in memo: return memo[n] memo[n] = self.dp(n-1, memo) + self.dp(n-2, memo) return memo[n]제가 봤을 때는 두 코드의 로직에 대한 차이점은 없어보입니다만 왜 아래의 코드는 시간초과가 나지 않는거죠??

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

브론즈4 2742번 기찍 N 문제인데, 시간 설정? 에서는 BOJ2743 N찍기라고 나옵니다. 실수하셨나보네요. 수정 부탁드립니다.

강의자료 인쇄하려고하는데, 검정색 배경화면으로 나오는데 이거 인쇄용으로는 없나요? 너무 잉크 많이 쓰게 되는데 ..

#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로 정렬하면 에러가 터집니다.  

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

*, %는 연산자 우선순위가 같으니까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; }

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