space of spadework

알고리즘 문제를 풀다보면 흔히 list보다 deque(double ended queue)가 훨씬 빠르다고 한다. deque의 popleft()는 배열의 첫번째 데이터를 꺼내는 것으로 O(1)의 시간복잡도가 걸린다. 그 이유가 무엇인지 궁금하여 찾아보았다. deque는 원형 큐를 확장하여 손쉽게 구현할 수 있다. 다음과 같이 초기화 가능하다. class Deque: rear = 0 front = 0 MAX_SIZE = 100 deq = list() def __init__(self): self.rear = 0 self.front = 0 self.deq = [0 for i in range(self.MAXSIZE)] 이렇게 rear, front 변수를 활용하여 linkedlist와 비슷한 방식으로 삽입, 삭제시..

queue인 것에서 알 수 있듯이 push, top, pop 메소드가 있으며, 일반 queue에서는 FIFO 구조로 저장하는 선형 자료구조인데 반해, prioirty queue의 비선형 자료구조로 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 우선순위는 MAX, MIN으로 지정하기 나름이다. 구현 방식으로는 배열, 연결 리스트, 힙 등이 있다. 보통 최악의 경우라도 가장 나은 성능을 보이는 heap이라는 자료구조로 구현된다. 원소들을 넣고 정렬할 때 heap sort를 사용한다. heap은 완전 이진 트리 구조인데, BST(Binary Search Tree)와 달리 중복된 값이 허용된다. Enqueue(삽입) 예시로 15라는 데이터가 들어왔을때 동작 순서이다. Dequeue(삭제) 20이라는 데이터..

문자열 압축 https://programmers.co.kr/learn/courses/30/lessons/60057 기타 레슨 https://www.acmicpc.net/problem/2343 가스관 https://www.acmicpc.net/problem/2931 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 외판원문제

소수는 1과 자기자신만을 약수로 갖는다. 그 외에 나눠지는 경우가 있다면 False를 return 한다. def is_prime(x): i = 2 while i*i

1. hackerrank https://www.hackerrank.com/interview/interview-preparation-kit 문제가 영어이고, 짧은 영어강의도 있다. input 코드는 이미 생성되어있어 함수만 작성하면 된다. 포인트로 틀린 케이스를 확인할 수 있다. https://www.hackerrank.com/dashboard 새로운 언어를 배울때도 좋을 것 같다. 코딩테스트 : 카카오계열 2. 프로그래머스 https://programmers.co.kr/learn/challenges 문제가 깔끔하다. 틀린 케이스를 확인할 수 없어 질문하기를 많이 이용하는 편이다. 코딩테스트 : 라인 3. leetcode https://leetcode.com/problemset/all/ 여기꺼 100문제 ..

5가지 sort python으로 구현 SelectionSort, InsertionSort, BubbleSort, MergeSort, QuickSort #-*- coding: utf-8 -*- def selectionSort(arr): """ 시간 O(n^2) 공간 O(n) (현재위치에 값을 찾음) 정렬되지 않은 리스트를 첫번째 index에서부터 시작 해당 index값을 포함하여 그 뒤 값들과 비교하고 최소값과 위치를 바꾼다. (swap) """ for i in range(len(arr) - 1): min_idx = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx..