본문 바로가기
반응형

패스트캠퍼스 챌린지

 (17)
패스트캠퍼스 챌린지 9일차 Ch 08. 알고리즘 복잡도 표현 기법 - 시간복잡도-2 3. 대문자 O표기법 - 빅오 표기법, Big-O 표기법이라고도 부름 - O(입력) - 입력 n에 따라 결정되는 시간 복잡도 함수 - O(1), O(𝑙𝑜𝑔𝑛), O(n), O(n𝑙𝑜𝑔𝑛), O(𝑛제곱), O(2의𝑛제곱), O(n!)등으로 표기함 - 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음 - O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(n제곱) < O(2의n제곱) < O(n!) - 참고: log n 의 베이스는 2, (일반적으로는 10) - 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 된다. - **표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다. - n이 1이든 100이든, 100..
패스트캠퍼스 챌린지 8일차 Ch 08. 알고리즘 복잡도 표현 기법 - 시간복잡도 알고리즘 복잡도 표현 방법 - 일부 자료구조들은 시간복잡도를 검토해봐야한다. 1. 알고리즘 복잡도 계산이 필요한 이유 - 하나의 문제를 푸는 알고리즘은 다양할 수 있다. - 정수의 절대값 구하기 - 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 - 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 --> 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산함. 2. 알고리즘 복잡도 계산 항목 - 시간 복잡도: 알고리즘 실행 속도 - 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 --> 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 한다. * 알고리즘 시간 복잡도의 주요 요소: 반복분이 지배..
패스트캠퍼스 챌린지 7일차 Ch 07. 자료구조 - 링크드 리스트-3 4. 링크드 리스트의 복잡한 기능1(링크드 리스트 데이터 사이에 데이터를 추가) - 링크드 리스트는 유지 관리에 부가적인 구현이 필요함 6. 링크드 리스트의 복잡한 기능2(특정 노드를 삭제) - 경우의 수를 나누어 주어야한다. - 첫번째 노드를 삭제할 때는 다음 노드를 헤드로 설정을 해주어야함. - 마지막 노드를 삭제할 때는 그 전 노드의 주소를 null로 바꿔주어야함. - 중간 노드를 삭제할 때는 전 노드의 주소를 중간 다음 노드의 주소로 바꾸어 주어야함. def delete(self, data): if self.head=='': print("해당값을 가진 노드가 없습니다") return # 1 head 삭제 if self.head.data ==data: te..
패스트캠퍼스 챌린지 6일차 Ch 07. 자료구조 - 링크드 리스트-2 3. 링크드 리스트의 장단점(전통적인 C언어에서의 배열과 링크드 리스트) - 장점 - 미리 데이터 공간을 할당하지 않아도 됨. - cf) 배열은 미리 공간을 할당해야 한다. - 단점 - 연결을 위한 별도의 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음. - 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 - 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요 *정리 1. 링크드 리스트는 연결리스트라고도 불리며 떨어진 곳에 존재하는 데이터를 화살표로 연결하여 관리하는 데이터 구조라고 할 수 있다. 2. 배열의 단점을 극복한 자료구조라고도 볼 수 있다. 3. 링크드 리스트는 노드와 포인터로 이루어져 있다. 4. 배열과 달리 미..
패스트캠퍼스 챌린지 5일차 Ch 07. 자료구조 - 링크드 리스트 1. 링크드 리스트(Linked List) 구조 - 연결 리스트 : - 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 - cf) 배열: 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조가 - 배열의 단점을 극복한 자료구조 - 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 - 링크드 리스트의 기본 구조와 용어 - 노드(Node): 데이터 저장 단위 (데이터값, 포인터)로 구성 - 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 - 일반적인 링크드 리스트 형태 - [ 12, *(99) ] --> [99, *(37) ] --> [37, * ] --> [] - [ A,..
패스트캠퍼스 챌린지 4일차 Ch 06. 자료구조 - 스택 스택 -데이터를 제한적으로 접근할 수 있는 구조 -한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 1. 스택 구조 - 스택은 LIFO(Last-in, First-out) or FILO(First-in, Last-out) 데이터 관리 방식을 따름 - LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책 - FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 - 대표적인 스택의 활용 - 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 - 주요기능 - push(): 데이터를 스택에 넣기 - pop() : 데이터를 스택에서 꺼내기 2. 스택 구조와 프로세스 스택 - 스택 구조..
패스트캠퍼스 챌린지 3일차 Ch 05. 자료구조 - 큐 1. 큐 구조 - 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 - FIFO (First-in, First-out) or LILO (Last-in, Last-out) ex) 먼저 줄을 선 사람이 먼저 들어가는 것과 동일 2. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기 - queue 라이브러리) Queue(), LifoQueue(), PriorityQueue() - Queue() : 가장 일반적인 큐 자료 구조 - LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(스택 구조) - PriorityQueue() : 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력 참고: 어디에 큐가 많이 쓰일까? - 멀티태스킹을 위한 프..
패스트캠퍼스 챌린지 2일차 Ch 04. 자료구조 - 배열 1. 배열이란? 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 파이썬에서는 리스트 타입이 배열 기능을 제공하고 있다. 2. 배열의 필요성 같은 종류의 데이터를 효율적으로 관리하기 위해서 사용 같은 종류의 데이터를 순차적으로 저장 3. 배열의 장점과 단점 장점 -빠른 접근 가능 : 인덱스를 활용하여 빠른 접근 가능 단점 -추가/삭제가 쉽지 않음. -미리 최대 길이를 지정해야 함. 4. 파이썬과 배열 -파이썬 리스트 활용 -파이썬은 배열 길이를 지정하지 않아도 된다. 5. 느낀점 - 배열을 모르는 것은 아니었지만 처음부터 기초를 다잡는 기분이 들어서 좋았다. 대본을 읽는 형식이 아닌 수업 형식이라 전달이 좋아 이해가 더 잘되는 것 같다. - 기술 면접을..
반응형

티스토리툴바