자료구조 & 알고리즘/이론10 [자료구조] 링크드 리스트(linked list) 👨🏻🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원 패키지 - 이준희 강사님 1. 구조 연결 리스트 어떤 데이터를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구현 리스트 타입이 링크드 리스트의 기능 지원 기본 구조와 용어 노드(Node) : 데이터 저장 단위 (데이터 값, 포인터)로 구성 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 2. 장단점(전통적인 C언어에서의 배열과 링크드 리스트) 장점 미리 데이터 공간을 할당하지 않아도 됨 배열은 미리 데이터 공간을 할당 해야 함 단점 연결을 위한 별도 데이터 공간이 필요.. 2022. 9. 21. [자료구조] 트리(Tree) 👨🏻🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원패키지 - 이준희 강사님 1. 트리 구조 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탬색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 용어 정리 Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연.. 2022. 9. 19. [알고리즘] 동적 계획법 (Dynamic Programming) 👨🏻🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원패키지 - 이준희 강사님 1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함 Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예: 피보나치 수열 분할 정복 문제를 나눌 수 없을 때까지 .. 2022. 9. 8. [알고리즘] 정렬 알고리즘 👨🏼🏫 이준희 강사님 fastcampus(알고리즘 이론) 목록의 요소를 특정 순서대로 넣는 알고리즘, 대개 숫자식 순서와 사전식 순서로 정렬 정렬의 시간 복잡도 1. 버블 정렬 가장 느린 알고리즘 ### 수도코드(sudo) Bubblesort(A) for i from 1 to A.length for j from 0 to A.length -1 if A[j] > A[j+1] swap a[j] with a[j+1] def bubblesort(A): for i in range(1,len(A)): for j in range(0, len(A)-1): if A[j] > A[j+1]: A[j], A[j+1] = A[j+1], A[j] bubblesort([2,3,5,1]) 2. 병합 정렬 ‘존 폰 노이만(John v.. 2022. 9. 7. [자료구조] 큐(queue) 파이썬으로 구현하기 Queue (선입선출) 큐는 먼저 들어온 자료가 가장 먼저 처리되는 자료구조 FIFO(First In First Out) 기반의 매우 유명한 자료 구조 순서 보장 큐(Queue)의 종류 1. Enqueue : 큐 맨 뒤에 어떠한 요소를 추가 예) 마지막으로 온 손님에게 번호표 발부 2. Dequeue : 큐 맨 앞쪽의 요소를 삭제 예) 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제 3. Peek : front에 위치한 데이터를 읽음 예) 다음 서비스를 받을 손님이 누구인지 확인 4. Front : 큐의 맨 앞의 위치(인덱스) 예) 다음 서비스를 받을 손님의 번호 5. Rear : 큐의 맨 뒤의 위치(인덱스) 예) 마지막에 온 손님의 번호 구현 # colab from collections im.. 2022. 4. 8. [자료구조] 스택(stack) 파이썬으로 구현하기 stack (선입후출 or 후입선출) 스택은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-In-First-Out) 자료구조 사용법 1. push(삽입) : 아래 그림과 같이 데이터을 집어 넣는 것으로 먼저 들어온 값 차례대로 삽입 2. pop(삭제) : push와 반대로 값을 삭제 3. top(), peek(읽기, 확인) : 위치에 해당하는 데이터를 읽음, 값에 변화는 없음 구현 # colab # 값 추가하는 함수 생성 def push(stack, element): stack.append(element) # 맨 뒤부터 값을 빼는 함수 생성 def pop(stack): print(f'pop: {stack.pop()}') # 값을 확인하는 함수 def peek(stack): print(".. 2022. 4. 8. 이전 1 2 다음
