해당강의 : 2주차;2-10. 2주차 끝&숙제 설명 강사님 안녕하세요. 강의 중 두 번째 문제인 ‘배달의 민족 - 배달 가능 여부’ 문제를 풀이하며, 아래와 같이 코드를 작성해보았습니다. def is_available_to_order(menus, orders): for order in orders: if order not in menus: return "주문 불가능" return "주문 가능" 강의에서 설명하신 set() 을 활용한 방식이 탐색 효율이 높다는 점은 잘 이해했습니다. 이에 대해 생각해보며 , 제가 작성한 방식도 리스트 탐색만으로 충분히 동작하여 데이터 규모가 크지 않은 상황에서는 큰 성능 차이가 없을 것 같다는 생각이 들었습니다. 두 방식 모두 평균적인 입력 크기에서는 큰 차이가 없을 것 같은데, 혹시 제가 사용한 방법도 일정 규모 이하의 데이터에서는 효율적인 접근으로 볼 수 있을지 궁금합니다. 또한, 실제 서비스 코드에서는 어떤 기준으로 set() 변환을 적용하는 것이 바람직한지 알고 싶습니다.
[질문 템플릿] 1. 강의 내용과 관련된 질문인가요? (예) 2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예) 3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예) [질문 내용] 17:10에서 전체 합을 private void로 따로 만들어 주셨습니다. 위의 사진이 제가 짠 코드입니다. 해당 사진은 선생님께서 짜주신 코드입니다. 두 사진에 있어 차이점은 totalPrice에 대해서 캡슐화를 하였는가 안하였는가에 대한 차이 뿐인데요. 최근 알고리즘 공부를 하다가 시간복잡도에 대한것을 공부하고 있습니다. 선생님과 제가 짠 코드에서 차이점이 있다면 저는 "displayItems에 직접 int total을 넣어서 for문에 입력한 것"이고, 선생님은 "calculateTotalPrice 생성자를 만드신 뒤에 int totalPrice를 선언"해 주셨는데요. 혹시 두 코드에 있어 시간복잡도는 어떤 코드가 더 오래 걸리는지 알 수 있을까요???
function solution(scores) { let scoreGroup = {}; let result = []; scores.forEach((score, i) => { if (scoreGroup[score] === undefined) { scoreGroup[score] = []; } scoreGroup[score].push(i); }); let rank = scores.length; // 아래 부분 시간 복잡도 질문합니다. Object.keys(scoreGroup).forEach((key) => { rank -= scoreGroup[key].length - 1; scoreGroup[key].forEach((index) => { result[index] = rank; }); rank -= 1; }); return result; } 제가 짠 코드는 다음과 같습니다. Q) 여기서 이 부분 시간 복잡도가 O(n)인가요 O(n^2)인가요?? Object.keys(scoreGroup).forEach((key) => { rank -= scoreGroup[key].length - 1; scoreGroup[key].forEach((index) => { result[index] = rank; }); rank -= 1; }); forEach가 이중으로 실행되지만 key가 n개면 각 value 길이는 1이 되고, key가 1개이면 각 value 길이가 n이 되는 상황이라서 O(n)인거 같은데... 정확하게 알려주시면 감사하겠습니다😭
안녕하세요 선생님. 문제를 풀다 이런 비트마스킹을 이용한 조합 문제에서 1억이 넘는지 확인을 어떻게 해야 할지 궁금해서 질문 남깁니다. 제 생각으로는 비트를 20개를 사용하니 2^20 - 1 만큼 연산을 하지만 비트가 N /2 만큼 켜진 것이 아니면 다음 연산으로 넘어가니 20C10 으로 보는것이 맞는건가? 라고 추측을 하는데 혹시 이게 맞을까요? 만약 이게 맞다면 20!이나 되는 큰 숫자를 시험도중에 대략적인 계산을 해보기에는 너무 크다는 생각이 드는데 TLE가 날지 어떻게 계산을 해봐야 할지 막막한데 방법이 있을까요?
https://www.acmicpc.net/source/share/5b5feb84a65f44c19188df5fbe697fe6 위 모범답안의 소스코드 라인과 시간복잡도 계산을 대응해보고싶어 강의내용과 연결을 지어봤습니다. 강의시간 02:58 에 설명한 조합 13C6 으로 나올 수 있는 경우의 수는 29라인 for문의 최대 반복횟수를 결정합니다. 집의 최대 갯수 100개가 31라인 for문의 최대 반복횟수는 결정합니다. 궁금한 점은 , 33라인 for문도 최대 반복횟수는 6 이 될 것이고 6라인 재귀함수 내부 for문에도 연산이 이뤄질 것인데 시간복잡도의 연산횟수계산에는 생략이 되었습니다. 위 두 라인의 연산은 크기가 작아 미미하기 때문에 무시하신 것인지 궁금합니다.
안녕하세요 6강까지 듣고 질문드립니다 강의를 통해 동적배열과 연결리스트에 대해서 1. add 2. 특정 인덱스 접근 3. remove 에 대해 각각 시간복잡도를 구하셨는데 일반 배열에 대해서는 1. 2. 3.에 대해 시간복잡도를 따로 알려주지 않으셔서 각각 복잡도가 어떻게 되는지 지적호기심이 차올라서 질문드립니다! 계산과정은 필요없더라도 결과만이라도 궁금하네요~^^
안녕하세요! 선생님 덕분에 많이 배우고 있습니다. 질문이 굉장히 많은데 모든 질문에 답변해주셔서 매우 놀라고 기뻤습니다..! const solution = function (arr, m) { let cnt = 0; for (let lt = 0; lt < arr.length; lt++) { let sum = arr[lt], rt = lt; while (sum <= m) { cnt++; sum += arr[++rt]; } } return cnt; } console.log(solution([1, 3, 1, 2, 3], 5)); // 10 console.log(solution([1, 1, 1, 1], 5)); // 10 console.log(solution([10, 5, 2, 6], 100)); // 10 강의 듣기 전에 풀어본 것인데 혹시 반례가 있을까요? 그리고 제가 생각했을 때 이 코드의 반복문 실행 횟수가 가장 많아지는 경우는 입력된 수열이 [1, 1, 1, 1] 처럼 모든 요소를 다 더해도 m을 넘어가지 않는 경우에 for문의 lt가 0 일 때 : while문 반복 실행 횟수 4 (sum = 1일때, 2일때, 3일때, 4일때) lt가 1일 때: while문 반복 횟수 3 (sum = 1, 2, 3) lt가 2일 때: while문 반복 횟수 2 (sum = 1, 2) lt가 3일 때: while문 반복 횟수 1 (sum = 1) 이렇게 되니까 입력된 수열의 길이가 n이라 하면 최악에 경우에 실행 횟수는 n + n - 1 + n - 2 + ... + 1 n + n - 1 + n - 2 + ... + 1 (lt = 0일떄 while실행횟수 ~ 마지막) 1 + 2 + 3 + ... + n (lt = arr.length-1일때 while ~ 처음) ------------------------- n * (n + 1) 이니까 총 실행 횟수는 (n^2 + n) / 2 여기서 최고차항 뺴고 다 없애고 계수도 없애면 n^2이니까 시간복잡도는 O(n^2) 이라고 생각했는데 제가 시간복잡도를 맞게 구한걸까요? 반면에 선생님의 코드는 가장 반복 횟수가 많아지는 경우가 제가 고민해봤을 떄 입력된 수열의 길이가 n일때, n -1 번째까지는 다 더해도 m을 안 넘는데 마지막꺼 더했을 때 m을 넘어가는 경우일 것 같은데.. 잘 모르겠어요. 이 경우가 맞을까요? 그럼 이 경우는 for문의 rt가 0에서 마지막 요소까지 쭉 가다가 (실행횟수 = 요소의 갯수 = n번) 마지막 요소에서 와일문이 rt = 0부터 마지막 요소까지 실행되니까 총 2n번 실행되는게 최대 반복 횟수일거같은데 제가 생각한 것이 맞는지 궁금합니다. 그리고 선생님처럼 이렇게 푸는 방법은 솔직히 제 머리론 죽었다 꺠어나도 못떠올릴거같은데 문제를 많이 풀다보면 머리가 좋아질까요..?
def DFS (x , l , r): if x == k: if tmp[ abs (l - r)] == 0 : tmp[ abs (l - r)] = 1 else : DFS(x + 1 , l , r) DFS(x + 1 , l + a[x] , r) DFS(x + 1 , l , r + a[x]) k = int ( input ()) a = list ( map ( int , input ().split())) tmp = [ 0 ] * ( sum (a) + 1 ) DFS( 0 , 0 , 0 ) count = 0 for x in tmp: if x == 0 : count += 1 print (count) 저는 이런식으로 리스트 만들고 그 값에 해당하는 값을 1로 만들어서 푸는 방식으로 코드를 짰습니다. 채첨 프로그램으로는 100점이 나왔지만 list보다는 set를 사용하는게 시간복잡도상 좋다고 들었습니다 인터넷 검색해보니까 set 과 list 둘다 n번쨰에 element 할당이 O(1)었습니다 제코드랑 선생님의 코드랑 비교하면 set쪽이 더 빠를까요?? 이런 문제를 풀떄는 list보다 set을 쓰는게 더 좋을까요??
n = int ( input ()) lst = [ list ( map ( int , input ().split())) for _ in range (n)] maximum = 0 mid = n // 2 for i in range (mid+ 1 ): maximum += sum (lst[mid-i][i:n-i]) for i in range ( 1 , mid+ 1 ): maximum += sum (lst[mid+i][i:n-i]) print (maximum)
import heapq def solution(N, road, K): n_road = [500001] * (N+1) n_road[1] = 0 sorted_road = [[] for i in range(N+1)] for road_num in road: sorted_road[road_num[0]].append([road_num[2], road_num[1]]) sorted_road[road_num[1]].append([road_num[2], road_num[0]]) # print(sorted_road) q = [] heapq.heappush(q, [0, 1]) while q: cur_node = q.pop() for dist, b in sorted_road[cur_node[1]]: if dist + n_road[cur_node[1]] < n_road[b]: # 1에서 cur로, cur에서 b로, 1에서 b로 n_road[b] = dist + n_road[cur_node[1]] q.append([n_road[b], b]) return len(list(filter(lambda x: x <=K, n_road))) 다익스트라 알고리즘을 구현하는데 의문점이 생겨서 여기 질문을 남깁니다. 1. 다익스트라 알고리즘에서 인접한 거리의 노드를 선택하기 위해서 heap 자료구조를 사용하는데 꼭 인접한 거리의 노드를 선택해야할 이유가 있을까요? 제가 원래 heap을 사용했던 python 코드를 단순히 배열로 바꿔서 가장 인접한 거리의 노드부터 선택하지 않음에도 불구하고 작동이 잘 되어서 질문을 남깁니다. - 제가 구현한 코드에서는 인접한 거리를 방문하든 안하든 결국 모든 노드들을 방문하여서 차이가 없다고 생각되었습니다. 2. 위와 같은 방법의 시간 복잡도는 어떻게 되는것인가요? 아직 시간복잡도 계산이 미숙해서 그런지 잘 모르겠습니다.
시간 복잡도 질문인데요 첫번째 질문은 여기 답변중에 강사님 께서 작성하신코드가 o(n) 의 시간복잡도를 가지고 있다하신걸 보았는데 for문 안에 while문이 있는데도 그대로 o(n) 복잡도 인건가요?? 그리구 두번째 질문은 강사님 코드에서 for문 대신 while문을 써서 while문을 중첩해서 사용되게 할때에는 시간복잡도가 어떻게 되나요??
선생님 안녕하세요 아이디어를 코드로 구현하기 전에 시간복잡도를 생각해 시간초과가 발생할지 안할지 생각해보고 시간초과가 안날 것 같을 때 그 아이디어를 코드로 구현해야 시험에서 시간낭비가 없을 것 같은데 그 기준을 어떻게 잡아야 하나요? 왜냐면 지금 이 문제는 시간복잡도가 n제곱임에도 시간초과가 안나지만 어떤 문제는 시간초과가 나서 질문드립니다
