자료구조5 [백준 1158번] 요세푸스 문제 문제 링크 >> https://www.acmicpc.net/problem/1158 📋 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 👉 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 👈출력 예제와 같이.. 2022. 4. 12. [12주차] 우선순위 큐와 힙 4월 6일 자 학습 내용 정리입니다. ✅ 우선순위 큐 우선순위 큐는 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형이다. 우선순위 큐를 단순히 배열로 구현할 경우 입력은 O(1)이지만 출력은 O(n)이다. 우선순위가 가장 높은 원소를 찾는 과정과 그 원소를 제거하는 과정이 비효율적이라고 할 수 있다. ✅ 힙 힙(Heap)은 최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리이다. 힙은 최대 힙과 최소 힙의 두 가지 종류로 나뉜다. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 큰 값을 가지고 있다는 특징이 있다. 반대로 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작은 값을 가지고 있다는 특징이 있다. 파이썬에서는 heapq 모듈로 최소 힙을 사용할 수 있다... 2022. 4. 7. [12주차] 트리의 표현과 트리 순회 4월 6일 자 학습 내용 정리입니다. ✅ 트리의 표현 방법 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 다음 코드와 같이 표현할 수 있다. class TreeNode : def __init__(self) : self.left = None self.right = None 완전 이진 트리는 배열을 이용해 간단하게 구현할 수 있다. 루트 노드부터 깊이를 더해가며 각 정점에 번호를 붙였을 때 어쩐 정점의 번호가 n이라면 왼쪽 자식은 2n, 오른쪽 자식은 2n+1의 인덱스를 가진다. 따라서 이를 배열로 표현하면 아래와 같다. ✅ 트리 순회 트리 순회란 트리의 모든 노드를 방문하는 순서이다. 트리는 비선형 구조로 자료 사이에 정해진 순서가 없기 때문에 각 노드를 방문하고 값을 가져오기 위해 트리 .. 2022. 4. 7. [12주차] 트리의 개념 4월 6일 자 학습 내용 정리입니다. ✅ 비선형 구조 앞서 포스팅에서 스택과 큐를 배우며 선형 구조와 비선형 구조에 대해 언급했었다. 선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미하며 비선형 구조는 자료를 일렬로 나열하기 힘들고 자료의 순서가 불규칙해 연결 관계가 복잡한 구조를 의미한다. 바로 이 비선형 구조의 대표적인 예가 트리(Tree)와 그래프(Graph)이다. ✅ 그래프 트리는 사실 그래프의 특수한 형태 중 하나이다. 따라서 트리를 이해하기 위해서는 그래프의 정의부터 알 필요가 있다. 그래프(Graph)는 정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조이다. 정점(vertex)은 자료, 상태 등 값을 담고있는 것을 의미하며 노드라고 부르기도 한다. 간선(edge)은 정.. 2022. 4. 7. [11주차] 자료구조의 의미와 배열, 연결리스트 4월 2일 자 학습 내용 정리입니다. ✅ 자료구조 자료구조는 말 그대로 자료를 저장하는 구조이다. 자료구조에는 배열, 트리 등 여러 종류가 있으며 저장된 자료에 대해 접근하는 방법이 약간씩 다르다. ✅ 추상적 자료형 자료형이란 어떤 자료가 식별되는 방법을 정의하고 그 자료에 대한 여러가지 연산(동작)을 제공한다. 여기서 연산이란 그 자료에 어떻게 접근할 것인지, 그 자료를 어떻게 사용할 것인지 등 다양한 동작을 말한다. 추상적 자료형은 어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다. 하지만 이 정의를 구현하는 방법은 명시되어 있지 않다. 따라서 추상적 자료형은 자료들과 그 자료들에 대한 연산들을 개념적으로 정의만 한 것을 말하며 자료구조는 추상적 자료형을 구체적으로 구현해 자료를 .. 2022. 4. 5. 이전 1 다음
