안녕하세요 선생님~!처음엔 15686번 문제를 bfs로 곁들여서(?) 풀었는데 시간초과가 나더라고요. 그래서 bfs를 사용하지 않고 푸니까 시간초과없이 문제가 정답처리 되었습니다. 정답 코드 : http://boj.kr/5fa47b86ba5246119038da418cfad011시간초과 났던 코드(bfs 사용) : http://boj.kr/ef1079acc43c4eb8ab9aeafe01d00bd2 이후 시간 초과가 났던 이유를 분석해봤는데, 제 생각은 아래와 같아요. 치킨집을 고르는 최대 개수 : 13C6 집의 최대 개수 : 100 13C6 * 100 = 171,600 (많이 여유로움) 하지만, bfs를 각 집마다 적용했으므로 (50 * 50) = 2500을 최대치로 잡고 더 곱해줘야 하므로 171,600 * 2500 = 629,000,000 따라서 시간 초과가 난다.  그래서 bfs를 사용하지 않고 abs를 사용해서 바로 거리를 계산하면 이 값이 최대 13이 되므로, 171,600 * 13 = 2,230,800 (여전히 여유로움)이라서 시간 초과 없이 통과되었다고 판단했어요. 제 질문은 아래와 같아요.bfs를 사용했을 때의 시간 복잡도 계산식에 오류가 없나요? (잘 계산한게 맞나요?)bfs를 사용하지 않을 때의 시간 복잡도 계산식에도 오류가 없나요? (잘 계산한게 맞나요?)  

안녕하세요 선생님! 결국 시간초과 문제를 해결했긴 했지만, 시간 복잡도를 어떻게 계산하는게 좋을지 궁금해서 질문드리려고 해요. 시간 초과가 났던 코드http://boj.kr/8fe9f1e620454720a985b58a993d229a통과 됐던 코드http://boj.kr/864f7c65db52442bada271fe193a2ec3기본적으로 선생님의 설명대로, 300C3 == 대략 4,500,000(450만) 은 반드시 든다고 가정했어요. 이때, 두 코드의 차이점은 다음과 같아요.movePlayer + isSamePosition 함수를 각기 사용하는가checkedPlayer 함수 하나를 사용하는가 만약 movePlayer + isSamePosition 를 사용한다면 제 생각에는 300 + 10 = 310 정도를 생각했고, 이로 인해 최종 시간 복잡도는 13억 5000만(450만 * 대략 300) 으로 생각했어요. 이는 13초 정도로 생각했고요. 하지만 checkedPlayer 함수를 사용하는 순간, 중간에 break 할 수 있어 300까지 계산할 일은 거의 없겠지만.. 정말 최악의 최악일 경우 n-1 player의 맨 h 행까지 계산해야할 수도 있을거라고 생각했어요. 그럼 결국 300까지 계산하게 되는거고, 이 또한 시간 복잡도가 13초 정도가 되는거고요.그래서 제 질문의 핵심은 다음과 같아요.시간 초과가 났던 코드, 통과한 코드의 시간 복잡도는 어떻게 계산해야하는가? 계산 결과 어떤 시간 복잡도를 가진다고 봐야하는가?checkedPlayer를 사용한다고 하더라도 최악의 경우에는 300번 가량을 계산해야하는 것은 마찬가지일 것 같은데, 왜 통과되는것인가? 물론 시간복잡도를 완전 정확히 계산할 수는 없지만, loop 횟수나 재귀함수의 호출횟수로 정량화하여 대략 예상하고 싶은데 이 예상치 조차 세워지지 않아서 혼란스러워 질문드렸어요 ㅜㅡㅜ  

2-G a[i]로 입력을 받으시는데 다른 문제들과 연계되는 특별한 이유가 있는지 궁금합니다

 학습하는 분들께 도움이 되고, 더 좋은 답변을 드릴 수 있도록 질문전에 다음을 꼭 확인해주세요.1. 강의 내용과 관련된 질문을 남겨주세요.2. 인프런의 질문 게시판과 자주 하는 질문(링크)을 먼저 확인해주세요.(자주 하는 질문 링크: https://bit.ly/3fX6ygx)3. 질문 잘하기 메뉴얼(링크)을 먼저 읽어주세요.(질문 잘하기 메뉴얼 링크: https://bit.ly/2UfeqCG)질문 시에는 위 내용은 삭제하고 다음 내용을 남겨주세요.=========================================[질문 템플릿]1. 강의 내용과 관련된 질문인가요? (예)2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예)3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예)[질문 내용]강의 중급 2편의 56강 9분19초에서 size++; 윗 줄의 bucket.add(value); 라는 코드는 자바 라이브러리에 있는 코드인가요? 아니면영한님께서 작성한 코드인건가요?강의에서 사용한 코드를 보면 배열의 값을 대입시키는 코드는 안보이는데 마지막에 있는 add()메서드가 값을 저장하게 된다고 말씀하셨는데 앞선 강의에서는 해당인덱스게 정수 값을 대입시키는 것 밖에 나와있지 않아서 질문하게 되었습니다

안녕하세요! 8분 대의 nlogn 설명에서 정렬할 때 n이 곱해진다고 하셨는데 무슨 말인지 잘 모르겠습니다. C++의 stl의 sort함수가 nlogn으로 알고 있는데 그걸 말씀하신 건지?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.교안내용을 아예 배껴와도 DevC++에서 a.pop_back(); 에서 에러가 자꾸떠요.. http://boj.kr/ca9f117386e64005af40d6311178f7ce

이전 글에 같은 내용의 질문을 확인했는데 해당 글에 다른 분이 댓글다신거 확인하고도 의문이 안풀려서요.저는 peek() 메소드를 사용해서 코드를 작성했는데 첫번째 예시에 대한 답은 잘나오는데 두번째 예시의 답이 24가 아닌 26으로 나옵니다.왜 26이 나오는지 도저히 모르겠어요..혹시 peek() 메소드로는 해당 문제풀이가 힘든걸까요? import java.util.Scanner; import java.util.Stack; public class IronRod { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String laser = scanner.next(); System.out.println(solution(laser)); } private static int solution(String laser) { int answer = 0; Stack<Character> stack = new Stack<>(); // 선생님 풀이 for(int i = 0; i < laser.length(); i++){ if(laser.charAt(i) == '('){ stack.push('('); } else { stack.pop(); if(laser.charAt(i - 1) == '('){ answer += stack.size(); } else { answer++; } } } // 제가 작성한 코드 for(char c : laser.toCharArray()){ if(c == '('){ stack.push(c); } else { if(stack.peek() == '('){ stack.pop(); answer += stack.size(); } else { stack.pop(); answer++; } } } return answer; } }

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.이 강의를 먼저 듣는게 좋을까요? 아니면 강사님의 CS강의를 먼저 듣는게 좋을까요? 아직 강의 극초반이라 여쭤봅니다.

안녕하세요, 늘 좋은 강의 감사드립니다.다름이 아니라 해당 문제를 풀면서 go(idx, sum) 함수의 초기값을 어떻게 보내는지에 따라 오답처리가 되어 문의드립니다. 제가 처음 짠 코드는 다음과 같습니다.#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 987654321; ll dp[104][24]; int arr[104]; int n; int target; ll go(int idx, int sum){ if(idx==n-1){ if(sum==arr[idx])return 1; else return 0; } ll &ret = dp[idx][sum]; if(ret!=-1) return ret; ret = 0; if(sum+arr[idx] <=20){ ret += go(idx+1, sum+arr[idx]); } if(sum-arr[idx]>=0){ ret += go(idx+1, sum-arr[idx]); } return ret; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); memset(dp, -1, sizeof(dp)); cin >> n; for(int i=0; i<n; i++){ cin >> arr[i]; } target = arr[n-1]; cout << go(0,0) << '\n'; return 0; } 위와 같이 go(0,0)으로 한 경우 오답처리가 되었습니다. 반면 go(1, arr[0])로 시작한 경우 정답처리가 됩니다.제가 생각하기에 go 함수 내 조건문에 따라 음수값은 처리하여go(1, arr[0])와 차이가 없다고 생각했는데 어디서 문제인거지 알 수 있을까요?  

 어느 파트인지섹션 5 - 그래프 순회 (DFS & BFS)내가 이해한 내용DFS와 BFS 모두 모든 노드를 탐색하고, 시간 복잡도도 같다고 이해했습니다.궁금한 점DFS로만 풀리고 BFS로 안풀리는 문제도 있나요? BFS로 DFS문제가 다 풀리면, 왜 강사님은 DFS로 먼저 접근하시는건가요? 

어제 노션 공유 신청했는데 아직 안 와서 다시 공유 요청했습니다... 그럼 혹시 다음 주 월요일까지 기다려야 하나요...?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.질문 1. n의 범위가 30을 넘지 않고 조합문제라면, 비트마스킹이라고 가정하고 풀어도 될까요? 아니면, 문제마다 생각하는게 좋을까요? 질문 2. 매개변수 설명해주시는 부분에서for(int i=1; i<n; i++){ go(1 | (1<<i)); }위 부분은 0번째 인덱스인 사과가 1인경우. 즉, 사과를 포함하는 모든 경우의 수이잖아요.여기서 사과를 포함하는 경우만 보는게 아니라 완탐을 하고싶다면, 굳이 함수 매개변수로 비트연산을 전달 안 하고 그냥 비트마스킹을 하면 되는거죠?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요! 좋은 강의 개설해 주셔서 감사합니다! 마지막 class에서 () 내부에 Int = 20이라고 설정하시고 main 함수에서 출력할 때 그냥 이름만 넣어줘도 자동으로 20이 나왔는데 이 원리가 어떤 건지 궁금합니다 : Int를 넣어주면 Int를 출력값으로 받겠다는 의미 아닌가요?

http://boj.kr/e469d016f48d45fdba8b5dc64066e87c문제풀이 로직은 다음과 같습니다.1. 수빈이가 짝수 시간에는 0번 s_visited에 홀수시간에 도달한 장소는 1번 s_visited에 저장을 합니다. 동생이 이동하면서 수빈이와 같은 시간에 정확히 도착하거나 2만큼 차이가 난다면 바로 출력하게끔했는데 17 5 입력이 자꾸 4가 아닌 6이 나오더라고요

int dp[N+1]의 배열을 채울때 1,2,4,원을 만들 수 없는 것은 이해했으나 7원의 경우는 어떻게 되나요?

안녕하세요 선생님! 선생님의 해설 잘 들었습니다.다만 제 코드가 어떤 테스트케이스에서 걸리는지 도저히 모르겠어요. 3시간 넘게 테스트케이스만 만들고 테스트해봤는데 다 잘 되고 있어서.. 제 코드는 다음과 같이 구현되어 있어요. 경우의 수는 더하기라는 것을 활용노드의 level(depth,거리) 단위로 bfs 진행이를 위해 정적으로 size 활용한 while(size--) 활용visited, cnt 배열로 각각 최소 거리와 최소 시간을 도출해냄다만 제 코드의 유의할점은 prevLoopNum과 loopNum을 사용한다는 점이에요. 이는 0 -> 1 ---(더하기 1)--> 2 0 -> 1 ---(곱하기 2)---> 2와 같은 경우에 서로 다른 경로로 인식되는 경우를 방지하기 위함이에요. 즉, 입력: 0 3 출력: 3 1이 나오도록 만들기 위함이에요. https://www.acmicpc.net/source/share/cc7572065f6146b8850e8ee371089353 

큰 돌 선생님 안녕하세요.항상 명강의 잘 듣고 있습니다. (_ _)다름이 아니라 약간 큰 돌쌤을 빙의해서 문제들을 먼저 풀고 > 해결을 보면서 차근차근 나아가고 있는데요. 다름이 아니라 3197 백조의 호수2개의 Queue 로 푸는 건 인지했습니다. 그런데 시간 초과가 발생해서요.코드 링크 http://boj.kr/23d82bb7e38c40b094f71a83b76d7e19제가 예상하는 부분은 check() 메서드에서 fill(&visited2[0][0], &visited2[0][0] + (SIZE - 1) * (SIZE - 1), 0);이 부분이 시간 초과에 영향이 큰 것 같은데 맞을까요? 문제는 이제 틀리더라도 맞는 방향으로 나아가는 것 같은데, 항상 문제를 풀고 나면 시간 계산을 할 때 어렵네요.바쁘지 않으실 때 확인 부탁드립니다.감사합니다.

안녕하세요, 큰돌 선생님!완전 이진 트리에 대한 설명에 대해 보충 의견 드리고자 글 남기게 되었습니다. 설명 중 "완전이진트리의 특징은 깊이가 3일 경우 2^3 - 1 = 7개의 노드를 갖는다" 라고 설명해주신 부분이 존재합니다.다만 해당 특징은 완전이진트리 중에서도 포화이진트리에 대한 설명으로 알고 있습니다.문제의 조건 중 2^k - 1 개의 노드를 갖는다는 조건이 존재하기 때문에, 단순한 완전이진트리가 아닌 포화이진트리가 되기 때문에 해당 문제의 해설이 성립될 수 있었던 것이라고 생각합니다. 혹시 제가 완전이진트리에 대한 개념이 잘못된거라면 지적 부탁드립니다! 감사합니다.

package 인프런.시뮬레이션_복습01; import java.util.HashMap; import java.util.Map; public class 비밀번호 { public static class Point{ int row; int col; Point(int row,int col){ this.row=row; this.col=col; } } private static Map<Integer,Point> map; private static final int INF=3; private static int getDistance(int row1,int col1,int row2,int col2){ return (int)Math.pow(row1-row2,2) + (int)Math.pow(col1-col2,2); } private static boolean isValid(int dis){ //거리가 대각선 포함 이동시간이 1인 경우 if(dis<=2) return true; return false; } static class Solution { public int solution(int[] keypad, String password){ int time = 0; map=new HashMap<>(); for(int i=0;i<INF*INF;i++){ map.put(keypad[i],new Point(i/3,i%3)); } String[] inputs=password.split(""); /** * 시작 값 초기화 */ int nowX=map.get(Integer.parseInt(inputs[0])).row,nowY=map.get(Integer.parseInt(inputs[0])).col; for(int i=1;i<inputs.length;i++){ int x=Integer.parseInt(inputs[i]); int nRow=map.get(x).row; int nCol=map.get(x).col; if(nowX==nRow && nowY==nCol) continue; if(isValid(getDistance(nowX,nowY,nRow,nCol))){ time++; }else{ time+=2; } nowX=nRow; nowY=nCol; } return time; } public static void main(String[] args){ Solution T = new Solution(); System.out.println(T.solution(new int[]{2, 5, 3, 7, 1, 6, 4, 9, 8}, "7596218")); System.out.println(T.solution(new int[]{1, 5, 7, 3, 2, 8, 9, 4, 6}, "63855526592")); System.out.println(T.solution(new int[]{2, 9, 3, 7, 8, 6, 4, 5, 1}, "323254677")); System.out.println(T.solution(new int[]{1, 6, 7, 3, 8, 9, 4, 5, 2}, "3337772122")); } } }해시맵을 사용하여 풀었는데 이 방법도 시간 복잡도 혹은 공간 복잡도면에서 괜찮나요??

안녕하세요 선생님!저는 3-D (4179) 문제를 다른 방식으로 풀었어요.불이 확산되는 속도 vs 사람이 빠져나가는 속도를 비교한게 아니라, 매 loop마다 불을 먼저 확산시키고, 그다음 사람을 움직여보면서 탈출 가능여부를 체크했어요.또한, index를 0이 아닌 1부터 사용하도록 구현해두어 그에 맞게 조건문들도 구현해두었고요.제가 만든 테스트 케이스, gpt가 만들어준 테스트 케이스는 전부 통과하는데 백준에서는 계속 틀렸다고 나오네요.  어떤 테스트 케이스에서 걸리는건지 도통 모르겠는데, 도와주실 수 있으신가요?http://boj.kr/fafb46e051fc462fb1c2e8c1f12c403f