물론 시간복잡도 측정 방식 중 대표적인 빅오 표기법 자체가 n이 점점 커져서 무한대로 커지는 걸 가정하니까 1회 연산량이 몇 배 차이 난다 해도 aN+b에서 a나 다름 없으므로 제거하는 것 같긴 합니다. 하지만 같은 O(n)이면 n이 절반만 줄어도 (n이 무한히 커진다고 가정할 때) 그 효과가 무시할 만한 수치가 아닐 것 같아서 여쭤 봅니다. (ChatGPT 답변은 뭔가 신통치 않고, 근거자료 달라고 해도 못 가져오길래 질문드립니다.)

여기서 기존 head(2)가 가리키던 노드는 3이므로, 그 이전 노드는 2인 거죠? 맞다면 설명이 잘못된 게 아닐까 해서요...ㅠㅠ 코드는 기존 head의 이전 노드로 잘 써 있고, 도식도 잘 표시되었는데 설명이 다소 헷갈려서 확인 차 여쭤 봅니다.

 학습하는 분들께 도움이 되고, 더 좋은 답변을 드릴 수 있도록 질문전에 다음을 꼭 확인해주세요.1. 강의 내용과 관련된 질문을 남겨주세요.2. 인프런의 질문 게시판과 자주 하는 질문(링크)을 먼저 확인해주세요.(자주 하는 질문 링크: https://bit.ly/3fX6ygx)3. 질문 잘하기 메뉴얼(링크)을 먼저 읽어주세요.(질문 잘하기 메뉴얼 링크: https://bit.ly/2UfeqCG)질문 시에는 위 내용은 삭제하고 다음 내용을 남겨주세요.=========================================[질문 템플릿]1. 강의 내용과 관련된 질문인가요? (예)2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예)3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예)[질문 내용]여기에 질문 내용을 남겨주세요.HashSet과 HashMap의 주요 메소드의 시간복잡도에 대해 정리한 내용인데, 제대로 이해했는지 올려봅니다. 1. HashMap은 hash table 역할을 하는 배열을 내부적으로 갖는데 기본 크기는 16이며, 저장되는 요소가 배열 크기의 75%를 초과하면 크기가 두배로 늘어나며 요소들은 re-hashing된다.2. 특정 인덱스에 저장되는 데이터가 8개 이상이 되면, 이 데이터들은 red-black tree 형태로 변환되어 add(), get(), remove()와 같은 메소드를 호출할 때 O(log N)의 접근 효율을 제공한다.3. 하지만 인덱스에 8개 이상이 아닌 2~7개의 데이터가 저장되는 경우 강의에서 설명한대로 데이터 접근에 대한 O(N)의 효율이 나온다. (해시 충돌 설명 인용)4. 그리고 HashSet은 HashMap을 기반으로 하기 때문에 위 1~3번 역시 HashSet에 동일하게 적용된다. (HashSet의 경우 각각 add(), contains(), remove()) 위 정리가 맞다고 가정해도, 특정 인덱스에 8개 이상의 요소가 저장되는 경우가 드물기 때문에 경우에 따른 시간 복잡도를 저렇게까지 깊게 구분할 필요가 없는걸까요..?

선생님의 맵 강의에서 시간복잡도에서 궁금한 점이 생겼습니다맵을 사용할 때 조회, 삽입, 삭제 시 O(log N)이 걸린다고 설명해주셨는데 이건 일반적인 경우를 말하는건가요?자바 HashMap은 조회나 삽입 삭제 시 시간복잡도 O(1)로 알고 있어서요최악의 경우에는 충돌때문에 O(N)까지 걸린다고 알고있습니다.  자바 HashMap은 내부적으로 해시테이블로 구현되어있어서 그렇지만 일반적으로는 O(log N)이라고 말해야 하나요?

안녕하세요 로또번호 셔플 구현 설명에서 로또번호에 필요한 로직은 "탐색"과 스왑이라고 되어있고,플로우에서도 탐색이 O(1)인 배열을 사용해야한다고 설명이 되어있더라구요근데 배열으 탐색이 O(n)이고, 구현 코드를 봐도 배열값을 참조해서 스왑핑 하는 내용이더라구요그래서 설명이 탐색이 아닌 참조가 맞지않을까 생각했습니다.혹시 제가 잘못이해한거라면 답변 부탁드립니다!

 혹시 비선형 자료구조 강의를 만드실 생각이 있으신가요? 있으면 듣고 싶네요 ㅎㅎ

저는 37번 LRU 문제를 Deque랑 삽입 정렬로 풀었습니다.삽입 정렬은 강사님 설명대로 반복된 입력값을 정렬시킬 때 사용했습니다. deque는 캐시메모리 크기를 초과할 때 pop(제거)를 위해 사용했습니다. 처음에는 vector로 풀었는데, 이럴 경우입력값 : 1 2 3 2 6 2 3 5 7index :0 1 2 3 4vector<int> v :1 6 2 3 5에서 처음 입력됐던 1이 삭제돼야하는데, vector는 pop_back()만 있어서 앞쪽인 1이 아니라 뒤쪽인 5가 삭제됩니다. 그래서 pop_front() 혹은 pop_back()랑 push_front가 동시에 컨테이너가 없을까 찾아보다가, 양방향 입력/제거 가능한 deque를 사용했습니다!(queue도 앞으로 들어오고 뒤로 나가는 거지만 정렬하기 힘드니까 패스!) 아래 코드 첨부합니다!최근에 해시 공부하면서 익힌 iterator(반복자)도 사용했는데, iterator가 처음이신 분들은 대충 index처럼 요소 접근하는걸로 이해해주시면 됩니다!(정확히는 주소 접근이지만!) #include<iostream> #include<deque> #include<algorithm> using namespace std; int main() { int S{}, N{}; deque<int> dq; // 중복 값 정렬 cin >> S >> N; for (int i = 0; i < N; i++) { int tmp{}; cin >> tmp; // 중복값 찾기 deque<int>::iterator it = find(dq.begin(), dq.end(), tmp); if (it == dq.end()) dq.push_front(tmp); // 중복 없으면 그냥 앞에서 삽입 else { // 중복값 있다면 // (tmp = *it을 할 필요없음 : 그 값이 그 값이니까) // 하나씩 뒤로 밀기. 제일 앞쪽에 도착하면 it-1을 못하니까 반복 종료 for (it; it != dq.begin(); it--) { *it = *(it - 1); } *it = tmp; } // 제일 뒤쪽 삭제 if (dq.size() > S) dq.pop_back(); } for (int i = 0; i < dq.size(); i++) cout << dq[i] << " "; } 

선생님 안녕하세요. Linked list의 시간 복잡도에서 질문이 있습니다. Linked list는 이론상 삽입 삭제가 O(1)이고, 실제 구현해보면 조회의 과정이 필요하기 때문에 O(n) 이라는 점 잘 이해했습니다.그러면 Array가 Linked list에 비해조회는 빠르고 (O(1) vs O(n))삽입 삭제는 동일하며 (O(n))주소를 저장 할 필요가 없어 동일한 양의 데이터를 저장시 필요한 메모리도 적습니다. (Array가 꽉 찼다고 가정)이러면 결국 Linked list를 써야하는 경우가 얼마만큼의 데이터가 들어올지 예측을 할 수 없을 때 말고 다른 경우가 있나요??감사합니다.

첫 번째 사진에 있는 1번 문제를 풀려고 하는데요.오늘 처음으로 '쉽게 배우는 자료구조 with 파이썬' 교재로입문을 했습니다. 그리고 문제를 풀으려고 하는데,여기서 어떤 방식을 써야할까 보다가 두 번째 사진에 있는등차수열을 이용한 재귀 알고리즘과 사진에는 없지만피보나치 수열을 이용한 알고리즘 구하기도 있습니다.그런데 해당 문제는 등차,등비수열 어느것에도 해당되지 않아서어떻게 풀어야할지 감이 1도 안 잡히네요ㅠㅠ도와주세요 고수님들!!!

안녕하세요, 강사님. 강의 들으면서 코딩테스트 정말 잘 준비하고 있습니다. 리스트를 생성하는 방법에 대한 질문이 있습니다.   강사님께서 리스트를 생성하실 때, 가끔은 arr = [] for _ in range(10):     arr.append(int(input()) 이런 식으로 빈 리스트를 생성한 후에 그 안에 요소들을 차곡차곡 채워 넣는 방식으로 생성하시고,   n = 10 arr = [0]*n for i in range(10):     arr[i] = int(input()) 가끔은 이런 식으로 0을 채워넣은 리스트를 생성한 후에 각각의 index를 활용하여 list의 요소를 바꿔주는 방식을 이용하시는 것을 보았는데, 두 가지 방식에 따른 효율성(시간복잡도의 유의미한 차이가 있다 등) 및 논리성(두 번째 경우 C에서  Array를 구성하듯 리스트의 공간을 미리 확보해 놓고, 그 안에 값을 채워넣는 방식이다)의 차이가 있을까요? 또, 강사님이 선호하시는 방식은 무엇인지, 그에 대한 특별한 이유가 있는지 궁금합니다!

강사님, 안녕하세요.  토마토문제 testcase 4, 5에서 시간초과 오류가 발생하고 있습니다. 정답코드를 넣어봐도 같은 문제가 발생합니다. 다른 학생분들이 올린 질문에 답변하신 것을 찾아보니, 정답코드를 넣어도 시간초과가 발생하는 것은 컴퓨터 성능문제라고 하셨습니다. 그런데 다른 문제에서는 안그러는데 자꾸 queue를 사용하는 경우에만 이런 성능문제로 인한 시간초과가 발생하는데 이유가 뭔가요? queue가 다른 자료구조보다 사용하는데 시간이 많이 걸리나요?   감사합니다. 

안녕하세요 강사님 알고리즘 강의 덕분에 수월하게 공부하고 있습니다. 두 배열 합치기 강의에서  간단한 Two Pointers Algorithm 알려주셨는데  그렇다면 앞으로 다른 유형의 문제들에서도 오름차순으로 정렬을 해야할 경우에 Two Pointers Algorithm을 사용할 수 있다면 sort를 사용하는 것 보다 Two Pointers Algorithm을 사용하는 것이 효율성 측면에서 조금 더 좋은 방법인가요???

질문도 대충 했으니까, 그냥 힌트만 대충 주세요. 적당히 알아먹을만큼요. 나머진 제가 고민해볼게요