포시코딩

개요 자료구조를 공부할 때 파이썬이 다루기 쉽다해서 자료구조, 알고리즘은 파이썬으로만 해왔는데 얼마전, 토스 코딩테스트에서 node.js 부문에 대해 문제를 봤을 때 오로지 JavaScript로만 풀 수 있게 되있는걸 볼 수 있었다. 문제를 풀 수 있고 없고를 떠나, 앞으로 node.js 관련 개발을 베이스로 깔고 갈텐데 자료구조나 알고리즘을 JavaScript로 다루지 않는다는게 좀 웃긴거 같아서 당분간은 죽이되든 JavaScript로 연습해볼 생각이다. Queue class Node { constructor(data) { this.data = data; this.next = null; } } class Queue { constructor() { this.head = null; this.tail = n..

개요 여러 개의 문자열 중 특정 문자열을 찾을 때 효과적인 트라이(Trie) 자료구조에 대해 알아보자 먼저, 이름은 retrieval(검색) tree에서 따왔다 정도의 유래가 있는듯하다. 위에서 말한바와 같이 여러 개의 문자열 중 특정 문자열을 찾을 때 하나하나 확인한다면 O(n) (n은 list의 길이)의 시간복잡도를 가지거나 정렬 후 이진 탐색을 사용한다면 O(nlog n)의 시간복잡도를 가지는 반면, 트라이의 경우 최선일 경우 O(1), 최악일 경우에도 O(m) (m은 문자열의 길이) 안에 할 수 있다고 한다. 따라서, 문자열이 아주 길거나 자동 완성 및 검색어 추천 기능 등에서 Trie 자료구조를 통해 효과를 볼 수 있다. 형태 문자열 집합 {'rebro', 'replay', 'hi', 'high..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 위 문제를 풀면서 나는 이진 탐색을 통해 문제를 해결했지만 간단하게 자료구조와 if not in 커맨드를 통해 해결하는 방법도 있어서 공부를 하던 중 N = int(input()) arr = list(map(int, input().split())) M = int(input()) target_arr = list(map(int, input().split..

Queue FIFO queue = [] def enqueue(data): queue.append(data) def dequeue(): data = queue[0] del queue[0] return data for i in range(1, 10): enqueue(i) print(queue) print('dequeue: ', dequeue()) print('dequeue: ', dequeue()) print(queue) Stack LIFO stack = [] def push(data): stack.append(data) def pop(): data = stack[-1] del stack[-1] return data for i in range(1, 10): push(i) print(stack) print('..

BFS란? 한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법. 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 BFS를 적용한다. BFS 구현 방법 1. 큐 BFS는 현재 인접한 노드들을 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. -> 처음에 넣은 노드를 꺼낸다. -> 큐를 쓰면 되겠구나 큐를 사용한다는 점 말고는 DFS에서 스택을 사용하는 방법과 매우 유사하다. 코드로 직접 살펴보자 graph = { 1: [2, 3, 4], 2: [1, 5], 3: [1, 6, 7], 4: [1, 8], 5: [2, 9], 6: [3, 10], 7: [3], 8: [4], 9:..

DFS란? 자료의 검색, 트리나 그래프를 탐색하는 방법으로 사용되며 한 노드를 시작으로 인접한 다른 노드를 통해 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS의 특징 DFS는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다. 따라서 공간을 적게쓰지만 최단 경로를 탐색하기가 쉽지 않다. DFS 구현 방법 1. 재귀함수 DFS는 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문 또 그 노드를 방문해서 깊이 우선으로 인접한 노드 방문 만약 끝에 도달했다면 리턴 -> 반복.. 반복하다가 갈 수 없게 되면 탈출 -> 재귀 함수를 쓰면 되겠구나 코드로 직접 살펴보자 graph = {..

그래프란? 연결되어있는 원소간의 관계를 표현한 자료구조 비선형 구조는 표현에 초점이 맞춰져있고 선형 구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있는 반면, 그래프 자료구조는 연결 관계에 초점이 맞춰져 있다. 그래프 용어 노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertax)이라고도 한다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 그래프의 종류 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다. 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다. 무방향 그래프의 표현방법 1...

소개 트리: 계층 구조의 데이터를 쉽게 표현 가능 힙: 최솟값과 최댓값을 쉽게 뽑을 수 있다. ex) Min Heap, Max Heap 트리(Tree) 스택(Stack), 큐(Queue)는 선형 구조인 반면, (선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미) 트리는 비선형 구조. 선형 구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다. 형태뿐만 아니라 용도에서도 차이점이 있는데, 선형 구조는 자료를 저장하고 꺼낼 때 좋고 비선형 구조는 표현에 초점이 맞춰져 있다. 트리를 다루는 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 ..

큐(Queue)란? FIFO(First In First Out)의 성격을 가진 자료구조. 처음으로 들어간 데이터가 처음으로 빠져 나오는 어찌보면 당연하고 합리적인 자료구조이다. 실생활에서도 많이 접할 수 있는 자료구조 중 하나이다. 사용예시 서버 접속 대기열 큐 롤에서 야 큐 돌려~ 하는것도 이 큐가 맞음 인쇄 대기열 큐 인쇄 하나가 오류로 안되면 그 뒤에 나와야할 인쇄물도 모조리 안나오는 경험이 있을 것이다. 이 때도 큐를 쓴다. 큐의 대표 기능 Peek(픽) 큐의 Top(맨 앞) 데이터를 보는 것 Enqueue(삽입) 큐에 원소를 삽입하는 행위. 원소는 Rear(맨 뒤)에 들어간다. Dequeue(뽑기) 큐에서 원소를 뽑아오는 행위. FIFO 자료구조라 Front에 위치한 원소를 뽑아온다. Peek,..

스택이란? LIFO(Last In First Out)의 성격을 가진 자료구조. 데이터를 쌓고나서 데이터를 빼낼 때 마지막으로 넣은 데이터부터 빼내는 자료구조이다. 참고로 반복문의 무한루프 등으로 메모리의 이 스택 영역이 쌓이고 쌓이다가 터지는 현상을 많이 들어본 스택오버플로우(StackOverflow)라고 한다. 사용예시 웹에서의 뒤로가기 버튼 Undo / Redo React의 Stack Navigator 스택의 대표 기능 Peek 스택의 Top(맨 위) 데이터를 보는 것 Push 스택의 Top에 원소를 삽입하는 행위 Pop 스택의 Top에서 원소를 가져오는 행위. Push로 넣었던 원소가 나오게 된다. Peek, Push, Pop 코드 구현 이전 포스팅에서 배웠던 링크드리스트를 통해 스택을 구현해보자 ..