Queue (큐) 큐는 항목을 FIFO(선입 선출)하는 순서로 저장하는 자료구조 입니다. 예를 들어 음료수 선입 선출이나 마트에서의 대기열을 생각하시면 됩니다. 해당 이미지를 보게되면 Data6을 Push할 때는 맨뒤로 들어가거 Data1을 Pop할 때는 바로 처음에서 꺼내게 된다 이걸 deque라고 합니다. - deque란? double-ended queue의 줄임말 큐에서 양방향으로 데이터를 처리한다는 의미 double은 자료구조에서 양방향을 의미 from collections import deque queue = deque(["Eric", "John", "Michael"]) queue.append("Terry") queue.append("Graham") print('queue:', queue) pr..

그래프란? 노드 간에 연결될 수 있다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있다. 트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프 형성이 가능하기 때문에 다른 범위의 개념으로 필요한 자료구조이다. 예를 들어, object간의 관계를 표현을 할 때 유용하다.(SNS, 도로 상의 차량 검색, 운송 시스템) 그래프는 기본적으로 위 그림처럼 vert(노드 또는 정점)와 edge(간선)으로 연결되어있다. 그래프와 트리의 특징 그래프는 노드간의 관계, 트리는 노드간의 계층을 표현한다. 그래프와 트리는 서로 다른 개념이라는 것을 알아야 한다. 트리에는 그래프에는 없는 계층개념이 있기 때문이다. 도식화해서 상세히 둘의 관계를 확인해 보자. 그래프의 유형 그래프의 특성은 directed(..

퀵정렬과 병합정렬(Quick Sort and Merge Sort) 🔍 자세히보기 : 퀵정렬(퀵소트)과 병합정렬은 많이 활용되고 비교되는 것이다. 퀵 정렬의 시간복잡도는 최악의 경우 O(n²)이며 평균의 경우 O(nlogn)이다. 최악: 피벗에 의한 원소들의 부분집합이 1개와 n-1개로 분할되는 경우가 반복되는 경우 병합 정렬은 성능의 저하 없이 항상 O(nlogn)이다. 퀵 정렬은 불안전 정렬이고, 병합 정렬은 안정 정렬이다. 동일한 값에 대해 기존의 순서가 유지되는 것이 안정 정렬이다. 퀵 정렬이 사용 되는 이유 퀵 정렬은 피벗이라는 별도의 노드를 지정해두고 재귀적으로 수행을 하기 때문에 통상적으로 병합정렬보다 더 빠르다. 병합 정렬은 전체 데이터를 기준으로 처음과 끝을 계속해서 탐색하기 때문에 퀵소트..

Divide and Conquer(분할 정복) 방법 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법이다. 특징 : 병렬적으로 문제를 해결할 수 있다.(하지만, 문제를 해결하기위해 문제해결함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용될 수 있다.) 재귀호출은 같은 함수코드를 재호출하는 것(같은 함수코드 사용) 분할정복은 비슷한 작업을 재진행하는 것(같은 함수코드는 아닐 수 있음) 분할정복의 과정 본 문제를 서브문제로 분할(divide) 서브문제의 답을 구한 경우, 해당 답을 본 문제에 대한 답이 되도록 병합함(Merge) 문제를 분할할 수 없거나, 할 필요없는 경우에 대한 답을 구함(base case, 기본 케이스) 분할정복의 조건 본 문제를 서브문제로 분할할 수 있는가?(Divide) ..

사용하는 알고리즘은 서비스별로 다르다. 알고리즘의 기본이 되는 것은 무엇일까? 1-1 알고리즘이란 사전에서 알고리즘은 '산법'으로 어떤 문제를 해결하기 위해 입력된 자료를 토대로 원하는 출력을 유도하는 규칙의 집합을 뜻한다. 즉 알고리즘은 '문제를 푸는 절차'다 1) 알고리즘과 프로그램의 차이 알고리즘은 문제 해결을 위한 작업 절차 자체이며, 기본적으로 그 절차를 실행하는 수단은 언급하지 않으나 실제로 문제를 풀려면 어떤 수단으로 알고리즘을 실행해야 한다. 이 알고리즘을 실제로 실행할 수 있는 형태로 구현한 것이 프로그램이다. 즉 프로그램은 프로그래밍 언어로 쓰여진 알고지름의 작업지지서이며 알고리즘 그 자체가 아니다. 필요한 결과를 얻기 위해 사용할 수 있는 알고리즘이 하나만 있는 것은 아니다. 2) 알..

OOP(Object-Oriented Programming) 쉽게 생각해서 세상에 있는 실체가 있는 모든 물체를 클래스와 인스턴스, 함수, 변수라는 object로 변화 시켜서 프로그래을 구성한다고 생각하자 OOP의 기본 전제는 기능(함수, 변수) 재 사용이 가능하도록 설계 및 프로그래밍 했는지다. 프로그래밍에서 사용되는 대부분의 개념은 최소비용으로 최대효율을 얻기 위해 개발되었다. OOP도 그런 개념의 일부일 뿐이다 OOP에 대한 의견 중요한 것은 용어보다는, 현실에서 발생할 수 있는 특정 object를 컴퓨터라는 도구에 인식시키는 것이라 할 수 있다. 대부분의 분야에서 OOP의 개념을 적용하여 프로그래밍을 수행한다. 기본개념 : 설계(사람이 이해하는 방식)와 구현할 소스코드(컴퓨터가 이해하는 방식) 간의..