강의 제목 : 알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문 안녕하세요! 위 강의 10:14번에 나와있는 정리 노트 관련해서 하나 여쭤보고 싶은 것이 있어요! 5번 '방문 순서를 담기 위해서는 어떤 자료구조를 사용해야 될까?' 이거 답이 리스트(LIST) 인가요?? 혹시 이 정리 노트에 있는 질문 5개에 대한 답변이 적혀있는 PDF 같은 게 있을까요?? 나중에 자격증 공부할 때 도움될 것 같아서 여쭤봅니다 감사합니다! 강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요 ! 질문할 때 가장 정확하게 이해할 수 있습니다. 해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다! 취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :( 이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요! 이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등) 에 관련한 질문을 주시면 답변 드리겠습니다 :) "이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요. 강사님 강의 너무 잘 보고 있습니다. 교재 공유 요청 했는데 확인 한번 부탁드리겠습니다~!
안녕하세요 강사님, Daily temperatures 문제 시간 복잡도에 의문이 생겨서 질문 드립니다. 강의에서 말씀해주신 코드가 아래와 같은데요 def daily_temperatures(temperatures): ans = [0] * len(temperatures) stack = [] for day, temp in enumerate(temperatures): while stack and stack[-1][1] < temp: prev_day = stack.pop()[0] ans[prev_day] = day - prev_day stack.append((day, temp)) return ans 첫번째 for 부분에서 시간 복잡도가 O(n)이고, 두번째 while문이 왜 시간복잡도가 O(1)인지 좀 헷갈립니다. list의 pop의 시간복잡도가 O(1)이긴 한데, 이것도 n번 반복하면 O(n)이지 않나요? while문에서 최대한 pop이 일어날수 있는 수가 n번 ? 같아서 질문 드립니다. 감사합니다.
안녕하십니까 코딩센세님! 잘 와닿지 않는 부분이 있어서 3일 정도 곱씹어보다가, 제가 생각한 바가 맞는지 검토가 필요해서 추가로 질문을 작성해봅니다. ===================================== [활용 (바텀업DP)] 강의에서 10:34초 쯤에, 냅색 문제의 탑다운DP 코드 일부분을 가리키며 이렇게 말씀하십니다. "이 재귀함수는 뒤에서부터 채워주는 형태죠?" Q1. 여기서, 뒤에서 채워준다는게 dp의 값을 idx==N부터 0을 리턴하며 dp[idx]에 값이 채워지기 때문이라고 이해하면 맞을까요? Q1-1. 위의 질문을 다르게도 표현하자면, 탑다운DP 방식으로 접근했기 때문에 엣지에서 시작하므로 끝에서부터 채워진다고 볼 수 있기 때문일가요? Q1-3. Q1.에서 이해한 바가 맞다면, 그와 같은 논리를 바탕으로, [활용 (바텀업 DP)] 강의 10:26초에서 설명하신 다음 코드에서 idx 부분을 빼줘야 하는 이유를 이해했지만, weight에서 item만큼의 무게를 빼줘야 하는 이유가 아직까지 이해가 되 지 않습니다.. dp[idx][weight] = max(dp[idx - 1][weight - items[idx][0]] + items[idx][1], dp[idx-1][weight] ===================================== [활용 (바텀업DP)] 강의에서 07:22~07:39초인덱스를 초과한 경우에 대한 연산을 설명하시는데요. Q2. if idx + interview[idx][0] > N: dp[idx] = dp[idx+1] 위 코드를 가리키시며, "인덱스가 넘는 경우는 그냥 뒤에걸, 선택 안하는거를 추가해준다고 하고.." 라고 설명하셨습니다. 저는 이게 어떤 부분을 의도하시는건지 와닿지가 않았습니다. 바텀업 dp는 코드를 따라가며 종이에 dp테이블을 적어보려 노력해봐도, 이해를 다 못해서 그런지 그려지지가 않더라구요. dp테이블 그리면서 생각을 추적하는 방법을 곁들여서 설명을 또 한번 부탁드려도 될지요? Q2-1. dp 인덱싱 부분을 제 입맛대로 조금 조작을 해봤는데요. 무슨 이유 때문에 아래의 코드는 90%에서 오류가 나는지 분석이 어렵습니다. 제가 첨부한 코드를 예시로 사용해서 설명을 Q2.에 대한 설명을 비교해주시면 감사드리겠습니다! # 바텀업DP 풀이 # 물건의 수, 배낭의 무게 # 4, 7 N, B = map(int, input().split()) # col_idx: 0, 1 # row_idx: 0, 1~3 # [idx][0]: Weight, [idx][1]: Value items = [list(map(int, input().split())) for _ in range(N)] # bag_wigth(col_idx): 0, 1~7 # item_idx(row_idx): 0, 1~3 dp = [[0 for _ in range(B+1)] for _ in range(N)] # idx: 0~3 # bag_weight: 0~7 for idx in range(N): item_weight = items[idx][0] item_value = items[idx][1] for bag_weight in range(B+1): if item_weight > bag_weight: dp[idx][bag_weight] = dp[idx-1][bag_weight] else: dp[idx][bag_weight] = max( dp[idx-1][bag_weight - item_weight] + item_value, dp[idx-1][bag_weight]) print(items) print(dp) print(dp[N-1][B]) 늘 친절한 답변에 감사드리며..! 저도 더욱 발전해서 코딩센세처럼 지식을 나누는 기쁨을 누릴수있도록 노력하겠습니다! p.s. 사실 솔직히 말씀드리면 print(dp[N-1][B]) 에서 N-1을 해야 하는 이유도 완벽하게 이해하지 못햇슴당 ㅎㅎ..
안녕하십니까 코딩센세! 늘 친절한 답변을 달아주심에 감사의 말씀 드립니다. 문제를 복습하다가 오늘은 도저히 진도가 나가지 않아서 힌트를 요청드리고자 이렇게 질문글을 남깁니다. 백준 15650을 풀려고 노력중에 있었습니다. 그런데 선생님의 코드를 적용해서 문제를 해결하려 했으나, 중복되는 수열을 거르는 것에서 어려움이 있습니다. 원래 백준 15649는 4 2로 N M의 입력이 주어진 경우 출력은 아래와 같아야 하는데요. 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 여기서 백준 15650은 4 2로 N M의 입력이 주어졌을 때, 1 2 1 3 1 4 2 3 2 4 3 4 이 둘의 차이를 구현하려고 2시간을 넘게 고민해봐도, [1,1] [2,1], [2,2] [3,1], [3,2], [3,3] [4,1], [4,2], [4,3], [4,4] 를 걸러내는 방법을 모르겠습니다. 선생님이 한 번 봐주시면서 피드백 좀 주시면 감사하겠습니다!
이 문제의 재귀는 이해가 됬지만, 다른 문제들에서 마주치는 재귀함수들은 손이 잘 안가고, 항상 남의코드를 봐야만 이해가 되더라구요. 여기서 dfs함수를 스택으로 구현하면 라인이 더 길어져 재귀보다는 깔끔하지가 않은데, 이해 및 구현이 쉬운거 보다 명확한거 같은데, 코딩테스트의 재귀들은 모두 스택으로 구현하면 어떨지 궁금합니다.
안녕하십니까 코딩센세! 이번에도 어김없이 질문 드리고 싶은 부분이 있어서 질문글을 남겨봅니다. 활용(바텀업 DP) 수업에서, 8:08초와 10:55초 에서 작성하신 if문이 잘 와닿지가 않습니다. 8:08초의 경우, if idx+ interview[idx][0] > N 으로 작성하셨는데요. 설명 역시 논리적으로 다가왔습니다. 당연히 문제에서 주어진 N의 범위보다 크다면 인덱싱이 불가능할테니 idx보다 더 뒤에 있는 dp[idx+1]의 값으로 할당하는 거라고 이해했습니다. 문제는 10:55초 입니다. 작성하신 코드는 if weight < B 인데요. 부연 설명은 "가방의 무게보다 작으면 예외 처리를 한다"라고 이해했습니다. 문제의 요구사항에 따르면 가방의 무게보를 초과했을 때 예외처리를 해야 하지 않나? 라는 의문이 들었는데요. 아직 의문을 해결하지 못하여 선생님의 코드가 잘 이해가 되지 않는 상태에 있습니다... 저의 질문을 읽어주신다면, if weight < B 라고 조건을 걸어야 하는 부분에 대해 조금 더 상세한 설명을 부탁드립니다! p.s. 선생님 혹시 7강에 대한 정답 코드는 볼 수 없는건가요? 수업자료에 작성되어 있지 않아서 문의드립니다.
#include <iostream> #include <vector> #include <queue> using namespace std; #define ll long long #define endl "\n" void merge(int a, int b); int find(int a); vector<int> parent; vector<int> paths; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n; cin >> m; parent.resize(n + 1); for (int i = 0; i <= n; ++i) { parent[i] = i; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { int v; cin >> v; if (v == 1) { merge(i, j); } } } for (int i = 1; i <= n; ++i) { int n; cin >> n; paths.push_back(n); } int prevPath = find(paths[0]); for (int path : paths) { int curPath = find(path); if (curPath != prevPath) { cout << "NO"; return 0; } prevPath = curPath; } cout << "YES"; return 0; } void merge(int a, int b) { a = find(a); b = find(b); if (a != b) parent[b] = a; } int find(int a) { if (a == parent[a]) return a; return parent[a] = find(parent[a]); } 왜맞틀인거같은 느낌이 듭니다. 책에 있는 내용 분석해서 이해는 하였는데 제가 짠 코드가 왜 틀린것인지 모르겠습니다. 의심되는 부분은 처음에 merge하는 for문인거같은데 책처럼 인접리스트를 사용하지 않고 v가 1이라면(i행과 j열이 연결되어 있다면) 그냥 바로 merge하여 병합하였는데 이부분에 예외가 있는것인지 아니면 다른 부분에서 예외가 있는것인지 감이 안 잡히는데 어디가 잘 못된것인지 한번 봐주실 수 있나요? 감사합니다 :)
문제 1. 수열 (#2259) 오타 혹은 백준 문제번호가 바뀐 것 같습니다. 2259 -> 2559 문제 2. 수열 가장 크게 만들기 (#1912) 모든 수열이 음수인 경우 0번째 index의 값이 가장 크게 되므로 print(max(prefix[1:])) 로 해주면 좋을 것 같습니다
해당 강의가 없어 직접 질문 하게 되었습니다. 2251번 책을 보면 이동 가능한 경로가 A -> B, A ->C, B -> A, B -> C, C -> A, C ->B 로 총 6개인것은 이해를 했습니다. 근데 최초의 물이 C에만 담겨있는데 왜 sender, receiver를 6크기의 배열로 선언해주고 아래처럼 for문을 돌리고 없는 물을 처음에 6개의 경로에 따라 퍼다 나르는지 이해가 잘 가지 않습니다. for (int k = 0; k < 6; ++k) { // next[0] = a, next[1] = b, next[2] = c int next[] = { a, b, c }; next[Receiver[k]] += next[Sender[k]]; next[Sender[k]] = 0; // 대상 물통의 용량보다 물이 많아 넘칠 때 if (next[Receiver[k]] > now[Receiver[k]]) { // 초과하는 만큼 다시 이전 물통에 넣음 next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]]; // 대상 물통은 최대로 채움 next[Receiver[k]] = now[Receiver[k]]; } // A와 B의 물의 양을 통하여 방문 배열 체크 if (visit[next[0]][next[1]] == false) { visit[next[0]][next[1]] = true; q.push(make_pair(next[0], next[1])); // A의 물의 양이 0일 때 C의 물의 용량을 정답 변수에 저장 if (next[0] == 0) { ret[next[2]] = true; } } }
start 메서드의 경우 부모 클래스와 다르게 출력하는 것들이 있잖아요. 그런데 '__init__'의 경우 사실 부모 클래스에서 하는 기능과 똑같은데 ElectricCar와 CombustionEngineCar에서 모두 init을 오버라이딩 해주는 건 관례 같은 건가요? replit에서 init 오버라이딩 코드를 지우고 작동해도 똑같길래 궁금해져서 질문 드립니다! 수업 너무 좋아요 잘 듣고 따라 하는 중입니다:)
class Solution(object): def twoSum(self, nums, target): def backtrack(start, curr): # base case : 2개의 합을 더해서 target과 같으면 if len(curr) == 2 and sum(nums[i] for i in curr) == target: return curr # recursion : for i in range(start, len(nums)): curr.append(i) res = backtrack(i + 1, curr) if res: return res curr.pop() return None return backtrack(0, []) https://leetcode.com/problems/two-sum/submissions/1130560186/ 이 코드로 작성해서 leet-code의 two sum 문제에 제출해봤을 때 Memory Limit Exceeded 에러가 나는건 어떻게 해결해야 할까요?
안녕하세요! 강의영상과 백준 문제에서 입력 순서를 x1,y1,x2,y2 형식으로 입력을 받는데 이렇게 입력할 경우 결과가 반대로 나오는거 같습니다. ex. 1,2,1,2일 경우 2,1,2,1의 결과가 출력 인덱싱을 graph[y][x] 형태로 진행하여 파생된 문제 같습니다. 그러므로 입력을 y1,x1,y2,x2로 변경하거나 2차원 배열 인덱싱을 graph[x][y] 형태로 변경해야할 것 같습니다. 제가 이해한게 맞나요? 항상 좋은 강의해주셔서 감사드립니다.
