Algorithm/theory 7

[파이썬] 그래프, 트리 알고리즘 정리

파이썬 그래프, 트리 알고리즘 정리 알고리즘 선택 (최단거리) 가중치가 없는 경우 - BFS 가중치가 있는 경우 음의 가중치가 있을 때 - 벨만-포드 음의 가중치가 없을 때 - 다익스트라 전체 쌍 최단 경로 - 플로이드-워셜 ( n ≤ 100 ) 1. 벨만-포드 (Bellman-Ford Algorithm) 시간 복잡도: O(V * E) 모든 간선을 확인하며 최단 거리를 찾기 때문에 느리다. 음수 간선이 있어도 최단 거리를 찾을 수 있다. import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) edges = [] dist = [INF] * (n + 1) for _ in range(m): u, v, w = ma..

Algorithm/theory 2022.07.05

코딩테스트를 위한 python 문법

코딩테스트를 위한 python 문법 코테 언어를 고민하다 파이썬으로 정착하기로 생각하면서 필요한 문법 정리 출처: 이코테 숫자 자료형 ( Number ) 정수형 a = 1 b = 0 c = -1 print(a, b, c) # 1 0 -1 실수형 a = 1.23 b = 3. c = -13.2 print(a, b, c) # 1.23 3.0 -13.2 # 지수형 d = 1e4 e = 3000e-2 print(d, e) # 10000.0 30.0 컴퓨터의 시스템은 수 데이터를 처리할 때 2진수를 이용하며, 실수를 처리할 때 부동 소수점 방식을 이용한다. 2진수 체계 소수계산의 오차가 발생하는 대표적인 예시로는 0.3 + 0.6 이 0.8999999999999999 이 나오는 경우이다. 파이썬에서 이를 처리하는 ..

Algorithm/theory 2021.09.01

4. 덱 ( Deque, JavaScript 구현 )

덱 ( Deque ) 덱이란? double-ended queue은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 구조 덱은 앞, 뒤에서 각각 put, get을 할 수 있는 구조이다. put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다. front와 rear는 데이터의 앞과, 뒤를 가리키며 각각의 노드는 next와 prev로 연결돼있다. 언제 사용하는가? 저장할 데이터 개수가 가변적일 때 검색을 할 일이 거의 없을 때 데이터 접근을 랜덤하게 하고 싶을 때 구현 기본적인 덱의 구현 const Deque = (() => { class Deque { ..

Algorithm/theory 2021.07.25

3. 큐 ( Queue, JavaScript 구현 )

큐 ( Queue ) 스택은 보통 큐와 비교해서 알아보는데 스택에 대해 알아봤고, 이번엔 큐에 대해 알아보자. Queue 란? 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. 구조 큐는 put(insert)와 get(dele..

Algorithm/theory 2021.07.21

2. 스택 ( Stack, JavaScript 구현 )

스택 ( Stack ) 스택은 보통 큐와 비교해서 알아보는데 우선 스택에 대해 알아보자. stack 이란? 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 쉽게 한쪽이 막힌 통이라고 생각하면 된다. 개발자라면 한번쯤 들어가봤을 사이트 stack overflow에서 그 스택이 이 스택이다. 의미는 스택이 꽉차있는데 push로 삽입하려 하는 것을 stack overflow, 스택이 비어있는데 pop으로 제거하려 하는 것을 stack underflow 라 부르며, 스택을 만들 때는 위의 두가지를 예외처리 해줘야 한다. 구조 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIF..

Algorithm/theory 2021.07.21

1. Linked List ( 링크드 리스트, JavaScript 구현 )

Linked List ( 연결 리스트 ) linked list란? 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. 구조 노드(Node)와 링크(Link)로 구성되며, 노드는 실제 정보를 담고 있는 하나의 단위이고, 링크는 노드간의 위치정보를 저장하..

Algorithm/theory 2021.07.21

0. 자료구조

자료구조 알고리즘 문제 해결 이전에 개발을 함에 있어 기본적으로 알고 있어야 하는 부분이라 생각 되어, 자바스크립트로 구현해보면서 공부하고 정리하려 함. 자료구조란? 자료구조(資料構造, 영어: data structure)는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. - 위키백과 - 분류 보통 형태에 따라서 자료구조를 나누는데 크게 두가지로 나뉜다. 아래 적은 대표적인 자료구조들을 공부할 예정. 선형..

Algorithm/theory 2021.07.21