제가 경험이 부족해서 그런 것 같은데요, 이 문제는 'x < y'라는 조건이 없다면 DFS로 풀 수 있는 문제가 아닌 것 같다는 생각이 들었습니다. https://www.acmicpc.net/problem/2644 에서 '입력' 파트를 보면, '번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.'라고만 나와있습니다. 즉, 'x < y'라는 조건이 주어져 있지 않습니다. 부모 노드 번호가 자식 노드 번호보다 작다는 조건이 주어져 있지 않는 것입니다. 그래서 저는 이 문제가 DFS로 풀리는 문제가 아닐 것 같다고 생각했었습니다. 위 그림에서는 노드2의 부모가 1이지만, 2보다 값이 큰 3이 될 수도, 4가 될 수도 있을 것이라 생각했습니다. 따라서 노드2를 방문한 이후에, 노드2와 연결된 노드 중 아직 방문하지 않은 노드들 중 어떻게 부모 노드를 찾아야하지? '부모 노드 번호 < 자식 노드 번호'라는 조건이 없으면, 부모 노드를 찾을 수 없을 것 같은데?하는 생각이 들었습니다. 문제에서 x<y라는 조건이 없는 것 같은데, 어떻게 '나와 연결되어 있고 아직 방문하지 않은 노드 중 번호가 가장 작은 노드를 방문해야겠다'는 생각을 하신 것인지 궁금합니다..
graph, visited의 사이즈를 다음 코드와 같이 노드 개수에 맞게 (n+1)로 하면 되겠다고 생각했는데, 노드 개수의 최댓값인 1000을 이용해 사이즈를 정하신 이유가 무엇인가요?? graph = [[False]*(n+1) for _ in range(n+1)] visited = [False]*(n+1)
T, M, N, K를 입력받아 사용한다고 하셨는데, M과 K는 각각 세로와 가로값으로 입력받고, K는 배추의 위치라는것을 알았습니다. 근데 T는 테스크케이스 라는 언급을 하셨고 코드에서도 아래와 같이 작성되있습니다. while (T-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(br.readLine()); N = Integer.parseInt(br.readLine()); K = Integer.parseInt(br.readLine()); // map 정보 // dfs 수행 .... } 2번의 테스크케이스를 만드는 이유는 무엇인가요? 그리고 단순히 궁금해서 여쭤보는데 가로와 세로 순서로 입력받고 코드를 실행하는것이 아닌 거꾸로 세로와 가로 순으로 실행하는지 궁굼합니다. 답변 부탁드립니다. 감사합니다.
안녕하세요. 위의 코드는 제가 강의를 듣기 전에 작성한 코드입니다. 백준에서 2가지로 주어진 테스트 케이스는 통과하는데 코드를 제출하면 틀렸다고 나옵니다. 코드 어디가 잘못된지를 모르겠습니다. 그리고 강의에서는 dfs 함수에 start 변수만 넣지 않고 count 변수도 넣으셨는데 count변수를 매개변수로 넣지 않고 코드를 작성하는 방법이 있는지 궁금하고, 이러한 방법이 없다면 왜 매개변수로 count 변수를 넣어줘야 하는걸까요?
안녕하세요! two_sum 문제에 dictionary를 적용 관련하여 문의드리고자합니다. 강의 코드에서는 중복값이 존재 (ex : nums = [4,1,9,7], target = 14])일 때에 대해서는 해결이 되지 않았고, 해당 문제에 대해서는 해결을 하였습니다. 다만 leet code에서는 같은 값이 n번(n>=2) 들어갔을 경우 (ex : nums = [4,1,9,7,7], target = 14])에 대해서도 true를 반환해야할 것으로 보입니다. 파이썬 dictionary의 경우 nums = [4,1,9,7,7]로 dictionary를 생성하게되면 중복값은 key값 생성이 되지 않는 것으로 확인됩니다. 예를들어, memo = {} for index, v in enumerate(nums): memo[v] = index 하게되면, { 4:0, 1:1, 9:2, 7:3, 7:4 }가 아닌 { 4:0, 1:1, 9:2, 7:4 }로 생성되는 것 같습니다. 이렇게 된다면 아래 조건식에서 판단이 어려운데 혹시 dictionary를 무조건 활용한다는 가정하에 가능한 방법(중복 key처리, 중복값에 대한 여부 저장 등(?))이 있을까요? 제가 문제에 대해 정확히 이해한것이 아닐 수 있어 만약 해당 상황에 대한 풀이는 필요하지 않다면 미리 양해말씀드립니다 ㅎㅎ..
linked list를 사용해야 하는 경우가 언제일까요? 실제 사용하는 문제를 보고 싶습니다 제 생각에는 array list로 구현하고 visit같은 경우도 list slicing 후 +로 리스트를 합치면 N(1) 만에 가능하기 때문에 시간이 부족한 코테에서 언제 linked list가 꼭 필요할까 궁금합니다
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 사진은 Red-Black 트리 제거 2번째 예시입니다. 이렇게 끝나면 Red-Black 트리가 안되지 않나요...? 3이 빨강이거나, 10이 검은색이어야 5번 규칙에 따라 Black-Height가 맞지 않나요? 이해가 잘 되지 않습니다... ㅠㅠ
안녕하세요, 강의 잘 듣고있습니다. 다름이 아니라, 마지막 문제인 냅색 문제에서 물건을 안넣은 경우에 recur(idx +1, weight, value)가 아닌 recur(idx, weight, value) 로만 파라미터를 설정하신 이유가 궁금합니다! 질문과 별개로 강의 내용이 정말 좋아서.. 당장 이번주 코딩 테스트인데 도움이 많이 될 것 같습니다. 좋은 강의 저렴하게 제공해주셔서 정말 감사합니다!
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요, 강사님! 섹션 2. 반복문 강의에 @4:35부분에서 "만약 2의 10승이었다면 2의 31승보다 더 큰 숫자가 된다. 그러면 int형 변수에 저장을 할 수 없는 숫자가 된다." 이렇게 말씀하셨는데 이 부분이 이해가 잘 되지않아서 그런데... 혹시 10의 10승을 2의 10승으로 잘못 말씀하신걸까요? 감사합니다!
if left and right: return root return left or right 에서요 if 절에 left == None 이런식으로 조건걸지않고 변수만 걸어놓는게 어떤 의미일까요 ?? 구글링하기도 애매해서 여쭤봅니다... 제 계산상 None and None 일 경우에 True라서 root가 반환되어야 될것같은데 if에서 안걸리고 return하는 부분이 조금 이해가 안돼서요 ... None and None도 return값이 None이고 None or None도 return 값이 None인것같은데 어떻게 작동하는건지 ... 궁금합니다
안녕하세요 올려주신 노션 코드에 질문이 있습니다 올려주신 내용엔 memo ={} for i , num in enumerate(nums): ~~~~~~~ memo[num] = i 이렇게 되어있는데요 이렇게 되면 memo dictionary에 아무것도 없어서 리턴이 안되는거 아닌지 궁금합니다
제가 짠 코드가 시간초과가 나서 강의자료 코드로 제출했는데도 시간초과가 나더라고요 pypy로 바꿔서 내니까 통과가 됐는데 이런 부분은 신경을 안써도 되는걸까요? pypy가 기본적으로 python보다 빠른건 알고 있었는데 저 개인적으로는 파이썬으로도 통과해야 코드를 정확하게 짰다고 생각해서 지금까지 python으로만 실행을 했는데 이후에 기업 코테나 역량 테스트에서 이런 부분을 신경 써야 하는지 궁금합니다
else: cur = self.head # cur 포인터는 head가 가리키는 곳을 가리킴(현재는 1의 값을 가진 노드를 가리킴) while cur.next: # cur.next값은 곧 head가 가리키는 new_node의 next값인 Node이므로 False라서 while문 탈출 cur = cur.next cur.next = new_node # None값을 가지는 노드를 새로 들어온 노드와 연결 링크드 리스트부터 갑자기 이중 포인터가 사용되서 이해하기가 어려웠는데요, 결국에는 cur가 가리키는 값이 head이고, head가 가리키는 것이 new_node인데, 현재 new_node의 next값은 None이므로, 이것을 새로 추가된 노드를 가리키게 하기 위해 cur.next = new_node 로 작성한 것인가요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요, 강사님! 강의 잘 듣고있습니다. 정말 감사합니다 :) 아주 간단한...! 질문입니다!ㅎㅎ 섹션 2. List의 배열(Array) 강의에 @3:04부분에서 오른쪽 메모리 그림과 함께 '아직 할당이 되지 않은 메모리가 있다, 비어있기 때문에 어떤 데이터든 집어넣을 수 있다.'고 말씀하셨는데, 메모리를 보면 01001 이렇게 2진수 값이 들어있는것같은데 이것도 아직 할당되지않은 메모리로 보면 되는건가요~? 감사합니다~~!
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); M = Integer.parseInt(br.readLine()); graph = new boolean[N][N]; visited = new boolean[N]; int x, y; for (int i=0; i<=M; i++) { StringTokenizer tokenizer = new StringTokenizer(br.readLine()); x = Integer.parseInt(tokenizer.nextToken())-1; y = Integer.parseInt(tokenizer.nextToken())-1; graph[x][y] = true; graph[y][x] = true; } dfs(0); System.out.println(answer - 1); br.close(); } void dfs(int index) { visited[index] = true; IntStream.range(0, M).forEach(i -> { if (!visited[i] && graph[index][i]) dfs(i); }); answer++; } 위에처럼 저는 +1을하지않고(그래프에 0인덱스들은 사용을 안한다고 생각해서요.) 대신 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수를 입력받을 때 -1을해줘서 처리했는데요. 예제입력은 정상처리 되나 실제 제출해보면 런타임 에러 (ArrayIndexOutOfBounds)가 발생합니다. +1을 해줘야하는거같은데... 제가 생각한 배열사이즈, -1로 입력받기가 잘못된걸까요?
강의에서는 "뒤의 원소들을 한칸씩 옮겨준 다음에, 1번 인덱스에 원소를 삽입한다" 라고 되어있는데, 강사님께서 공유해주신 pdf에는 "리스트의 중간에 원소를 삽입하는 경우, 원소를 삽입한 후 뒤의 원소들을 한 칸 씩 미루어야기에 O(n)의 시간복잡도를 갖습니다." 라고 나와있습니다. 강의 내용이 맞는거죠?
