Seung_story

정리내용은 [이것이 취업을 위한 코딩 테스트다 with 파이썬] 책을 기반으로 작성하였습니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고 취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드 | 이런 독자에게 권합니다.■ IT 직군의 취업 준비생 / 예비 개발자■ 이직을 준비하는 개발자■ 알고리즘 대회를 준비하는 학생[특징]코딩 www.kyobobook.co.kr 복잡도 성능을 나타내는 척도를 말한다. 시간복잡도와 공간복잡도로 나뉜다. 복잡도가 낮을수록 좋은 알고리즘이다. 과거에는 메모리의 가격이 비싸고, 하드웨어 성능에 한계가 있었기 때문에 얼마나 더 적은 공간을 사용하는 지가 중요했지만, 시간이지나면서 하드웨어의 성능이 크게 증가했고, 현재는 공간 복잡도보단 시간 복잡도가 조금 더 ..

재귀함수 자기 자신을 다시 호출하는 함수를 말한다. 같은 행위를 반복하는 경우 재귀함수를 사용하면 훨씬 코드가 간결해진다. 예시: factorial(팩토리얼), 피보나치수열, 하노이의 탑, 유클리드 호제법 def recursive_test(): print("Hello World") recursive_test() recursive_test() 재귀함수의 종료조건을 넣지 않으면? 만약 재귀함수의 종료 조건을 넣지 않으면 함수를 무한히 호출한다. 따라서 아래와 같은 에러 문구를 만나게 된다. 이유는 보통 인터프리터는 호출횟수 제한이 있는데 이 한계를 벗어났기 때문이다. RecursionError: maximum recursion depth exceeded while calling a Python object ..

그래프(Graph) 데이터들 사이의 연결관계를 표현해주는 자료구조 [ex] 지하철 노선도 정점과 간선을 이용하여 만들어진다. 정점(Vertex): node를 나타냄 / 간선(Edge): 정점을 이어주는 선 그래프의 종류 간선의 방향 여부: 무방향 그래프 / 방향 그래프 간선에 가중치 존재여부: 비가중치 그래프 / 가중치 그래프 그래프의 용어 인접 정점(Adjacent vertex): 하나의 정점에서 간선으로 연결되어 있는 정점 차수(degree); 연결된 간선의 개수, 방향그래프의 경우 정점으로 들어오는 간선의 수를 진입차수, 정점에서 나가는 간선의 수는 진출자수라고 한다. 경로(Path): 간선을 타고 갈 수 있는 길 경로의 길이: 경로를 구성하는데 사용된 간선의 수. 최단경로를 구하는 알고리즘에서는 ..

완전 이진 트리 이진트리 중 노드 왼쪽부터 차례대로 채워져 있는 트리를 말한다. 무조건 왼쪽부터 데이터를 채우기 때문에 데이터를어떻게 넣는지에 관계없이 동일한 구조를 가진다. 배열을 사용한 코드 구현이 가능해진다. 코드가 짧아지고, 가독성도 좋아진다. 왼쪽 자식의 Index = 부모 노드의 index * 2 오른쪽 자식의 Index = 부모 노드의 index * 2+1 힙 완전 이진트리이고, 자식 노드들이 특정한 성질을 가지고 정렬되어 있는 구조 최소힙: 부모노드가 항상 자식 노드보다 작은 완전이진트리 형태(부모노드자식노드) 우선수위 큐에 사용된다. ※ 최소힙을 구현에 대해 공부할 예정입니다. 힙의 데이터 삽입 과정 1. 새로운 데이터를 힙의 마지막 노드에 이어서 삽입한다. 2. 새로운 노드와 부모 노드..

이진 탐색 트리(Binary Search Tree) 이진 탐색과 Linked List를 결합한 자료구조의 일종이다. 이진탐색은 시간복잡도가 O(lg n)으로 괴장히 빠르지만, 배열이기 때문에 자료의 삽입과 삭제가 불가능하다. Linked List 같은 경우 자료입력/삭제에 대한 시간복잡도는 O(1)이지만, 자료 탐색을 위해서는 O(n)의 시간복잡도가 필요했었다. 부모 노드가 왼쪽 자식보다 크고, 오른쪽 자식보다 작다는 특성이 있다. 이진 탐색 트리의 조건 1. 한 노드 A의 왼쪽 서브 트리에는 A보다 값이 작은 노드로만 이루어져 있다. 2. 한 노드 A의 오른쪽 서브 트리에는 A보다 큰 값이 큰 노드로만 이루어져 있다. 3. 중복된 노드가 없다. 4. 왼쪽 서브 트리, 오른쪽 서브 트리 역시 이진 탐색 ..

트리란? 계층 구조를 표현하기 위한 비선형 자료구조 (선형 자료 구조: 스택, 큐) 트리 용어 Node(노드): 트리를 구성하는 요소들 Edge(간선): 노드와 노드를 잇는 연결선 Root Node: 최상단의 노드 Level: 트리의 각 층별로 숫자를 매김. Root Node는 Level 0. Height: 최하단 노드까지 거쳐야 하는 Edge의 수 노드들 간의 관계 부모-자식 관계: 윗 레벨에 존재하는 노드를 Parent Node(부모 노드)라고 하고, Parent Node와 연결된 노드는 Child Node(자식 노드)라고 한다. 형제 관계: 같은 Parent Node를 갖는 여러 자식 노드를 Sibling Node라고 한다. 이진트리 자식의 수가 2개로 제한된 이진 트리를 말한다. 자식의 수가 2개..

Linked List(링크드 리스트)란? 연결 리스트로, 데이터와 포인터로 구성된 노드를 한 줄로 연결하여 저장하는 자료구조이다. Node에는 데이터(Node에 저장할 데이터)와, 포인터(다음 Node를 가리키는 주소 값)을 저장하고 있다. Head를 통해 첫 번째 Node에 접근할 수 있다. 포인터에 값이 없을 경우에는 종단점을 의미한다. Linked List의 장단점 1) 장점 - Linked List의 크기를 미리 할당할 필요가 없다. - Linked List를 수정 시, 시간 복잡도가 O(1)이다. 2) 단점 - 추가적인 저장공간이 필요하다. - 정보를 가져오기 위한 시간복잡도가 O(n)이다. ※ C언어 장단점 (Python의 리스트 지료형은 Linked List의 모든 기능을 지원함) Linke..

pandas 라이브러리란? panel datas(패널 자료)의 약자로 DB처럼 테이블 형식의 데이터를 쉽게 처리할 수 있는 라이브러리이다. 데이터가 테이블 형식으로 이루어진 경우가 많아 데이터 분석 시 자주 사용하게 될 Python 패키지이다. pandas 설치하기 pip install pandas pip 명령어를 사용하여 pandas 라이브러리를 설치한다. pandas 모듈 가져오기 import numpy as np import pandas as pd pandas 라이브러리를 pd라는 약자로 불러와 사용될 수 있도록 선언한다. numpy는 벡터와 행렬연산에 있어 편리한 기능을 제공하는 라이브러리인데, pandas와 함께 데이터 분석에 사용하면 효과적이다. Object 생성하기 pandas에는 2가지 오..

Deque(덱,데크)이란? 덱(deque)은 double-ended queue의 줄임말이다. 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 앞(front)과 뒤(rear)에서 모두 삽입과 삭제가 가능한 큐를 말한다. Deque는 언제 사용하는가? 데크(deque)는 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다. 스택과 큐의 장점을 모두 채택하였기 때문에 데이터를 넣고 빼는 것이 List 자료형에 비해 효율적이고, 속도도 빠르다. queue라이브러리를 이용하는 것보다 간단하다. 따라서 데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다. Deque 사용하기 from collections import deque deque 자료구조..

Queue(큐)란? 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식 큐는 데이터가 쌓이고 가장 먼저 들어간 데이터가 먼저 나온다. ( Stack과 반대 ) 데이터를 넣는 enqueue()와 데이터를 꺼내는 dequeue() 가 있다. 예시 프린터의 출력 처리 윈도 시스템의 메시지 처리기 프로세스 관리 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용 용어설명 Enqueue : 큐 맨 뒤에 데이터를 넣는다. Dequeue : 큐 맨 앞쪽의 데이터를 꺼내온다. Peek : front에 위치한 데이터를 읽음 (데이터 꺼내오지 않음) front : 큐의 맨 앞의 위치 rear : 큐의 맨 뒤의 위치 선형 큐 선형 큐는 위와 같이 1차원 배열..