python 썸네일형 리스트형 Posts/CS [Python 자료구조] 큐 (Queue) 💡 Goal - 큐를 이해한다. - 큐를 파이썬으로 구현한다. - 큐 특징 2가지 이상 말하기. 개념 FIFO(First In First Out)으로 동작하며 데이터간 순서를 약속하는 추상자료형을 말한다. 가장 먼저 들어온 데이터가 가장 먼저 삭제 대기열과 같은 개념 (ATM기 줄서있는 사람들 모습) 특징 deque를 사용해 큐 자료구조 구현 (doubly-ended-queue의 약자) deque는 내부적으로 doubly linked list로 구현 맨 앞, 뒤에 데이터를 삭제하고 삭제할 수 있게 하는 자료형 enqueue: 끝에 삽입 peek: 시작 개체값 리턴 dequeue: 시작 개체값 제거 큐의 활용 스케줄링 동시에 실행되는 여러 프로세스의 자원을 배정을 적절히 조절해 성능 개선 어떤 작업이 병렬.. 2022. 1. 9. 20:39 Posts/CS [Python 자료구조] 스택 (Stack) 💡 Goal - 스택을 이해한다. - 스택을 파이썬으로 구현한다. - 스택 특징 2가지 이상 말하기. 개념 LIFO(Last In First Out)으로 동작하며 데이터간 순서를 약속하는 추상자료형 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 마치 스시를 다 먹고 접시를 쌓아 올리는 형태와 같은 개념으로 처음 쌓은 접시가 가장 나중에 제거 특징 스택의 활용 컴퓨터 내부 프로세스 실행 구조의 함수 동작 함수는 가장 나중에 호출된 것이 가장 먼저 종료 웹 브라우저 방문 기록 역순 문자열 생성 구조가 단순해 구현이 쉬움 데이터를 삽입, 삭제, 접근이 가능한 자료형 파이썬으로 코드를 구현할때 deque를 사용하거나 list를 사용 스택은 단순히 빠른 성능을 위해 사용되기에 배열 구조를 활용해 구현 deque .. 2022. 1. 9. 17:42 Posts/Algorithm [boj] 더하기 사이클 - 1110 (python) 1. 문제 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자. 26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다. 위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다. N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오. 2. .. 2021. 12. 12. 23:36 Posts/Algorithm [누구나 자료구조 알고리즘] Python 삽입정렬 💡 Goal - 삽입정렬 알고리즘을 이해한다. - 삽입정렬 알고리즘을 파이썬으로 구현한다. - 삽입정렬 알고리즘 특징을 2가지 이상 말하기. 개념 데이터를 앞에서 하나씩 확인 후 특정 조건에 부합하는 위치(좌 or 우)에 삽입 왼쪽은 이미 정렬되어 있는 가정으로 접근 선택정렬에 비해 실행시간 측면으로 조금 효율적 처음 key값은 두번째(index 1)부터 시작 비교, 시프트(이동), 삽입등이 사용되는 알고리즘 순서(오름차순 기준) 1번 인덱스부터 시작하는 반복문을 만든다. 임시로 1번 인덱스값과 데이터를 가지고 ← 방향으로 반복 비교한다. 왼쪽은 이미 정렬되어 있다는 가정 왼쪽 값이 크다면 큰 값을 현재 position으로 변경해주고 position을 -1 해준다. (왼쪽 순회) 2,3단계가 끝나면 현재.. 2021. 12. 11. 20:43 Posts/Algorithm [누구나 자료구조 알고리즘] Python 버블정렬 💡 Goal - 버블정렬 알고리즘을 이해하기. - 버블정렬 알고리즘을 파이썬으로 구현하기. - 버블정렬 알고리즘 특징을 2가지 이상 말하기. 개념 서로 인접한(연속된) 두 원소를 확인해 정렬하는 알고리즘 인접한 2개의 원소를 확인하여 조건에 맞는 순서로 교환 비교와 교환으로 이루어진 알고리즘 순서(오름차순 기준) 연속된 두 항목을 가리킨 후 비교한다. 두 항목의 값의 크기가 뒤바뀌어 있으면 값을 교환한다. 비교 포인터를 오른쪽 한칸씩 이동한다. 배열의 끝까지 또는 정렬된 항목까지 1~2단계를 반복한다. 특징 장점 구현이 간단하다 단점 순차적으로 확인하기 때문에 크기에 맞지 않는 비교가 일어남 순차적으로 확인하기 때문에 N개의 길이가 있다면 N번 교환이 발생 코드 def bubble_sort(input_l.. 2021. 12. 11. 17:32 Posts/CS [Python 자료구조] 해시테이블 (Hash Table) 해시 테이블 CodeIt 자료구조 수업을 정리한 내용입니다. 1. Key-Value 데이터 110호: "제임스" 하나의 key와 그 key에 해당하는 value를 말합니다. 하나의 key에는 하나의 value만 존재 2. Direct Access Table 배열 인덱스를 키로 이용해서 데이터를 저장하거나 가져오는 것을 Direct Access Table이라 말합니다. 하지만 위에 사진에서 볼 수 있듯이 사용하는 데이터의 갯수는 5개이지만 인덱스의 가장 큰 값으로 인해 총 길이가 942개중 937개가 낭비되는 현상이 발생합니다. 3. Hash Table 해시 함수와 배열을 함께 사용하는 자료구조를 말합니다. 원하는 크기의 배열을 생성 해시 함수를 이용해 저장할 key:value 데이터의 키를 배열 inde.. 2021. 12. 7. 00:19 Posts/CS [Python 자료구조] 링크드 리스트 (Linked List) 링크드 리스트란? CodeIt 자료구조 수업을 정리한 내용입니다. 링크드 리스트 배열이나 동적 배열처럼 데이터를 순서대로 저장 동적 배열처럼 요소를 계속 추가 가능 노드 노드 객체는 2가지의 속성을 가지고 있습니다. data와 next로 이루어져 있는데 data는 저장하고자 하는 정보를 말하며, next는 다음 노드의 레퍼런스를 말합니다. 첫번째 노드 객체는 head 노드라고 하며 head 노드의 메모리주소만 알고 있으면 연결되어 있는 모든 노드를 접근할 수 있습니다. (실제 메모리에선 여기저기 흝어져있음) class Node: def __init__(self, data): # 인스턴스 변수들의 초기값 setting self.data = data # 노드 저장 데이터 self.next = None # 다.. 2021. 11. 25. 23:55 Posts/CS [Python 자료구조] 배열 (Array) 배열이란? CodeIt 자료구조 수업을 정리한 내용입니다. 배열 파이썬은 C를 기반으로 만들어졌고 C의 배열을 이용해서 만들어진게 파이썬 리스트 C 배열은 크기 고정, 같은 데이터 타입만 가능 C 배열의 경우 데이터가 메모리에 연속적으로 저장 파이썬은 데이터가 연속적일수도 있고 아닌 아예 다른 곳에 저장될 수도 있음 파이썬의 경우 메모리에 데이터의 주소값을 저장 아무리 큰 값이어도 가리키기만 하는 역할이므로 C배열과 다르게 다양한 값 저장 가능 item_list = [10, "데이터", True, -4] 배열 인덱스 접근 찾고자 하는 위치의 주소(index)를 알고 있기에 시간복잡도는 O(1) 입니다. 배열 탐색 배열의 탐색은 특정 조건을 만족하는 값을 찾는 것을 말합니다. 예를 들어 하나의 배열에 특정.. 2021. 11. 23. 00:00 < 1 2 >