강사님 안녕하세요.2주차 dfs, bfs 알고리즘 문제를 풀고 있습니다.2-I(2870) 문제나, 2-J(10709) 와 같은 형태의 문제가dfs, bfs 알고리즘과 관련이 있는건지 궁금합니다.

http://boj.kr/7b6776aa9c9545e58d94059272172eb9안녕하세요 선생님.3-C에서 저는 BFS를 통해서 구현하여 해결한 후, 강의를 통해 선생님 코드와 비교하며, 여러 구현방식을 익히는 중에 궁금한 점이 생겨서 질문드립니다.강의에 나온 코드는 검색 로직이 DFS로 구현되어 있는데, 제 코드의 검색 로직은 BFS인것만 제외하면 선생님 코드와 별 차이가 없다고 생각했습니다.그런데 막상 코드를 돌려보면제 코드의 시간은 164ms~172ms가 나오는 반면, 선생님의 코드는 88ms정도로 거의 90%가까이 빠르게 나옵니다.왜 이렇게 시간차이가 많이나는지 이해가 안는데 왜 그런지 여쭙고 싶습니다.(현재 여러 시도를 해보긴 했는데 오히려 더 느리게 나오고 잘 모르겠네요...ㅠ27,40번째 line의 중복 삽입 수정 버전 442mshttp://boj.kr/7fabb13a2ca441bda6e8591670ef9621함수 제거 버전 172mshttp://boj.kr/312e0d4df77c45219e46da19cc649e05)

안녕하세요. 선생님알고리즘 교안을 공부하다가 원형이중연결리스트의 예제로 나와있는 코드를 공부하다가 질문 드립니다http://boj.kr/dd49f798fc07434590e28e18f526ac3d << 이 코드를 출력하면3 1000 2 1 1 2 33 2 1 1 2 3이 나오는 것은 이해가 되었는데16행을 //로 주석처리를 하게 되면 17행의 a.erase(it)에 있는 it의 위치는 13행의 a.insert(it, 1000)에 있는 it의 위치보다 it++가 되어있는 것을 16행을 //로 주석처리하여 출력해서 출력된 값을 보고 알았습니다.그래서, 16행을 //처리시 출력된 값은 아래처럼 1000이 erase가 되지 않고 그 다음 위치인 2가 erase가 딥니다.3 1000 2 1 1 2 33 1000 1 1 2 3여기서 의문인게 12행에서 it을 a의 시작 주솟값이라고 초기화하였고, it++이 반복문에 들어가 있지 않은데 반복문같이 쓰인 것처럼 17행인 a.erase(it)의 it위치가 + 1이 된 것인가요?

안녕하세요!혹시 ch배열을 전역에서 크기를 할당하여 사용하면 안될까요?BFS메서드 안에서 크기를 할당해주는 이유가 궁금합니다! (제가 모르는 이유가 있을까 하여 질문드립니다!) 

4주차 비트마스킹을 풀고 있는데도저히 모르겠으면 그냥 강의를 보고 푸는게 나을까요?? 그냥 접근이 안되네요

큰돌님 강의 잘 보고 있습니다. 오큰수를 풀다가 궁금한 점이 생겨 질문 드립니다.저는 배열을 하나만 생성하고 stack에 직접 값을 넣으면서 풀이에서 막혔었는데요 스택을 써야 한다는 거까지는 떠올렸지만 스택에 인덱스를 넣고 a라는 배열을 새로 만들어 거기다 실제 값을 넣어야겠다라는 생각이 이어지질 않았습니다. 문제를 보고 어떤 부분에서 배열을 새로 만들어야겠다라는 판단을 해야 할까요? 괄호 문제 같은 경우 그냥 그대로 넣어버려서 쉽게 풀었지만 오큰수 문제의 경우 배열을 새로 만들고 거기에 실제 값을, 스택에는 인덱스를 넣어야겠다라는 유기적인 생각이 안 떠올라서 질문 드려봅니다.

어차피 정적변수나 전역변수나 쓰임이 비슷한거같기는 한데.... 딱 flag만 정적변수로 안하시더라구요 혹시 이유가있을까요??

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 이 문제를 혼자 풀 때..맵 입력 받고, 지훈이 이동 -> 지훈이 맵 탈출 확인 -> fire 퍼짐 이것의 무한 반복. 지훈이 맵 탈출한 경우, break로 끝내기 정도의 논리를 생각하고 코드 짜다가 강사님 해결 풀이를 보았습니다. 지훈이 이동은 bfs의 최적 길을 한칸씩 이동하는.. 불의 번짐으로 인해 매번 bfs 해야한다는 문제점이 있긴 하지만.. 이 방법을 생각했고요, 맵 탈출 확인은 bool type으로 확인하는 걸로, 불 번짐은 dfs로 한번씩 퍼뜨리는 걸 생각을 했는데요,,시간 초과가 날 것 같기는 한데, 이 방식의 논리는 어떻게 보시나요??

안녕하세요 선생님. 먼저 좋은 강의 정말 감사합니다 ! 이번에 두번 완강을 했는데 궁금한 것이 있습니다 ! 혹시 기업 코테를 준비할 때 빈출 알고리즘 유형을 알고 싶은데 어떤 것을 위주로 공부하면 좋을까요 ? 그리고 강의에서 하진 않았지만 더 알아야 할 알고리즘이 있다면 말씀해주시면 감사하겠습니다 !

안녕하세요 좋은 강의 감사합니다 !! 바로 본론으로 들어가면, 여기서 조건이 10^5 이니깐 O(n^2) 로 풀면 안된다고 하셨는데..for 문 안에 while 문이 있으니깐 결국 O(n^2) 아닌가요??temperatures 도 한번 훑고, stack 도 한번 훑으니깐 총 O(n^2) 이라고 생각했는데 잘못 이해하고 있나봐요 ㅜㅜ 시간복잡도 질문 - 밤의멜로디 님이 주신 질문에 대한 답변 내용이라면 while 문도 O(n^2) 이 아닌가 라는 생각이 듭니다..

안녕하세요 선생님.제가 교안을 공부하다가 이해가 가지 않아서 질문을 드립니다.http://boj.kr/386f3c2271d44c3d8ec3b88cb723b536이렇게 출력하면 출력된 값이 아래와 같습니다.10 : 09 : 11 : 98 : 22 : 87 : 33 : 76 : 44 : 65 : 5it.first는 기호 : 을 기준으로 왼쪽에, it.second는 기호 : 을 기준으로 오른쪽에 출력이 된것을 알 수가 있는데bool cmp(pair<int, int> a, pair<int, int> b){return a.first < b.second;}에서 a를 {10,0} b를 {9,1}로 보게 된다면 10 : 0 이 9 : 1보다 아래에 있어야 하는 것으로 생각했는데 제가 잘못 이해한 것 같아서 어떻게 이해해야 올바르게 이해를 한 것인지 궁금하여 문의 드립니다.더하여, bool cmp(pair<int, int> a, pair<int, int> b){return a.first < b.second;에서 a.first < b.second일 경우, bool형에 의해서 1이 출력되고, 이 조건에 따라sort(v.begin(), v.end(), cmp)이 정렬이 되는게 맞는지 문의드립니다.

이해가 하나도 안가네요 ㅠㅠ이럴경우 어떻게 해야될까요...문제는 간신히/??이해 했는데 설명들어도 무슨말인지 통 모르겠네요..

선생님께서 주신 1번 자료에서 [22,23]이라는 값이 있습니다. 이값때문에 [12,23], [21,23], [22,23]만 뽑히는거 아닌가요??어떻게 6개가 나오는지 이해가 되지않습니다.

선생님께서 풀어주신 dp 1차원 테이블 코드 말고도 2차원 dp 테이블로 풀어보았는데 해당 코드가 어떤 문제가 있는지 모르겠습니다.import sys sys.stdin = open("input.text", "rt") input = sys.stdin.readline sys.setrecursionlimit(10**6) data = [] n, limit = map(int, input().split()) #보석 종류, 무게 한계값 for _ in range(n): a,b = map(int, input().split()) data.append((a,b)) #무게, 가치 data.insert(0,(0,0)) #0번 인덱스 사용안함 dp = [[0] * (limit+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,limit + 1): weight = data[i][0] # 현재 물건 무게 value = data[i][1] # 현재 물건 가치 if j < weight: #현재 물건 담을 수 없으니 이전꺼 가져와야함 dp[i][j] = dp[i-1][j] else: #현재 물건 담을 수 있음 dp[i][j] = max(dp[i-1][j-weight] + value, dp[i-1][j]) print(dp[n][limit])해당 문제를 백준 배낭 냅색 알고리즘 문제에 제출하면 100점이 뜨는데 여기 문제에 예시를 출력해보면 28이 아닌 26이 나옵니다.. 어떤 것이 문제인지 모르겠고 dp 2차원을 최적화해서 1차원으로 만든 것인데 문제가 어디 부분인지 감이 안옵니다.  미리 답변 감사합니다 ! 

교안에는 없어서 질문드립니다!

밑의 코드의 내부 for문에서 최악의 경우 연산이 arr.length-1번 일어나기 때문에 시간 복잡도를 O(n^2)으로 봐야 할까요?function solution(m, arr) { let answer = 0, sum = 0; for (let i = 0; i < arr.length; i++) { sum = arr[i]; if (sum === m) { answer += 1; continue; } for (let j = i + 1; j < arr.length; j++) { sum += arr[j]; if (sum === m) { answer += 1; break; } else if (sum > m) { break; } } } return answer; }

안녕하세요!동적배열 강의관련 질문드립니다.정적배열과 동적배열의 시간복잡도를 비교하는 표에서,정적배열의 데이터 추가/삽입(insert_back/insert_at)이 이해가 안 되어 질문드립니다.정적배열은 선언과 동시에 크기가 정해지는데, 이미 초기화가 된 상태에서 추가나 삽입은 안 되지 않나요?혹시 크기만 선언된 비어있는 정적배열을 말하는건가 생각해보니, 비어있는거면 insert_at이나 delete_at을 할 때도 기존 데이터를 옮길 필요가 없으니 O(n)이 아니라 O(1)이지 않나싶어서 그건 아닌 것 같고,아니면 크기보다 데이터가 덜 들어간 케이스에서 저런 시간복잡도가 나오는건가요? ㅠㅠ 그렇다면 저게 다 이해가 됩니다.그런데 아무리 그래도 정적배열에서는 추가/삽입의 한계가 있지 않나요? 어떤 조건에서 저게 되는건지 알려주세요ㅠㅠ

http://boj.kr/377650e87589448abf24b7196faba01b안녕하세요 여러번 시도를 해봐도 어디서 틀린건지 잘 모르겠습니다..ㅜㅡㅜ

다름 아니라 dp를 걸 때 str,int 이 2개의 값으로만 dp를 거는데요.그 해당 값을 얻을 수 있었던 경로(visited)도 dp에 포함되어야 하는거 아닌가요 ?예를들면 str이 3이고 int가 3인 dp가 있을 때 (dp[3][3])해당 지점까지 가는 경로의 경우의 수가 여러가지 일테니각 경우의 수마다 얻을 수 있는 max값이 달라지지 않나요?dp에 이 2가지 요소만 들어가도 되는 이유를 잘 모르겠습니당 ㅠㅠ ㅎㅎ

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/651b3f6555054253aff3c5af3b037dbb이전에도 visited 위치에 대해서 질문한 적이 있는데, 이번에도 질문 드립니다.논리를 생각하고, 구현에서 막혀서 고민 중 강의의 코드를 보다가 구지 main과 dfs 둘 다 visited = 1 의 과정을 적어야 하는지에 대해 의문이 듭니다. 위의 제가 올려둔 코드처럼 할 경우 문제가 있는지 알고 싶습니다!