자료구조

(JAVA) 길 찾기 게임

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이진트리를 사용한 기본적인 문제이다. 아래와 같은 순서로 구현해나가며 문제를 풀 수 있었다. 트리에 사용할 Node 클래스 구현 nodes라는 node들을 담을 리스트에 node를 삽입 nodes를 y의 내림차순으로, y가 동일하다면 x의 오름차순으로 정렬 (트리에 올바른 순서대로 담기 위함) 정렬된 리스트에서 node를 하나씩 꺼내면서 트리 만들기 완성된 트리를 전위 순회한 값..

(CS) 트리 & 트라이

트리 트리는 계층적 구조를 가지며, 각 노드들이 서로 연결되어 있는 자료구조이다. 트리는 하나의 루트(root) 노드에서 시작하여 다양한 자식 노드들로 확장된다. 각 노드는 부모와 자식 노드 간의 관계를 가진다. 트리는 순환 구조를 갖지 않으며, 각 노드는 정확히 하나의 부모를 가진다. 트리를 이루는 구조를 하나씩 알아보자. Node(정점, Vertex) 트리의 기본 단위로, 정보를 저장하는 단일한 항목 노드는 데이터 필드(Key)와 하나 이상의 포인터를 가짐 Key 노드를 구분하거나 정렬하는데 사용하는 값 노드의 데이터 필드에 저장되는 값 Edge(간선) 노드 간의 연결 관계를 나타내는 선으로, 트리의 구조를 형성 두 노드 간의 간선은 부모-자식 관계를 나타냄 Root 트리의 최상위 노드로, 모든 다른..

(C++) 우선순위 큐(Priority Queue)

우선순위 큐란? 우선순위를 가지는 데이터들을 저장하는 큐(Queue)를 말한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우리가 흔히 말하는 큐(Queue)와의 차이는 일반적인 큐는 아래 그림과 같이 선형적인 구조를 가지는 반면 우선순위 큐는 트리 구조로 생각할 수 있다. 우선순위 큐의 동작 원리 일반적으로 우선순위 큐는 최대 힙(Max Heap)을 이용해 구현한다. 그래서 우선순위 큐의 동작 원리를 알아보기 전에 먼저 최대 힙에 대해 알아보자. 최대 힙은 부모 노드가 자식 노드 보다 값이 큰 완전 이진트리를 의미한다. 그렇기에 루트 노드는 전체 트리에서 가장 큰 값을 가진다. 이제 우선..

(Python) Deque

파이썬에는 List라는 데이터를 담을 수 있는 자료형이 존재한다. 하지만 다양한 알고리즘 문제를 풀이하다보면, List 대신 Deque를 사용하는 경우가 있는데 과연 Deque란 무엇이고, 왜 이것을 사용하는걸까? Deque란? Deque는 Double-ended queue의 줄임말로써 큐의 앞과 뒤, 즉 양방향으로 삽입과 삭제가 가능한 큐이다. Deque 사용하기 Deque 자료형은 collection에서 불러와야하기 때문에 다음과 같은 선언문이 필요하다. from collections import deque 이후에 다음과 같이 선언하여 하나의 새로운 Deque를 만들 수 있다. arr = deque() Deque 메소드 Deque에도 List와 마찬가지로 내부의 데이터들을 관리하기 위한 다양한 메소드..

(Python) 백준 2164번 - 카드 2

문제 링크 : https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 처음에는 단순히 list를 사용하여 풀이를 진행하였으나, 시간제한이 2초로 매우 짧아서 log(N)으로 삽입과 삭제를 진행하는 list로는 시간 초과가 발생할 수밖에 없었다. 그래서 상수 시간으로 조회, 삽입, 삭제가 가능한 deque를 사용하여 풀이를 진행하였다. import sys from collections import deque # 1부터 n까지의 카드들을 deque를..

(Python) 백준 11866번 - 요세푸스 문제 0

문제 링크 : https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 오랜만에 정렬이 아닌 다른 유형의 문제를 풀다보니 조금 헤메었다. 리스트를 사용해 간단한 원형 큐와 원형 큐에서의 삭제를 구현하면 되는 문제였다. import sys def josephus(arr, k, order): # N명의 사람이 저장된 arr에서 (N, K)-요세푸스 순열을 order에 저장 arrow = 0 # 제거될 사람의 번호 while len(arr) != 0: # 모든 사람이 제거될 때까지 arrow += (k-1) # 다음 K번쨰 사람을 지목 ..