PinguiOS

안녕하세요 Pingu 입니다.🐧 Swift에는 Deque 자료구조가 따로 없어서 직접 만들어야합니다.😂 참고로 Deque는 앞뒤로 모두 삽입, 삭제가 가능한 자료구조입니다. 매번 만드는게 귀찮아서 이렇게 따로 글을 남기려고합니다. Deque를 만드는 방법에는 다양한 방법이 있지만 이번 글에서는 간단하게 배열 2개로 만든 Deque를 만들었어요. Swift에서는 배열을 뒤집는 reversed() 메서드의 시간복잡도가 O(1) 이므로 Deque와 같은 성능을 낼 수 있다고 봅니다. Deque의 가장 기본적인 기능들만 구현했습니다. 감사합니다. // Made by Pingu class Deque { var enqueue: [T] var dequeue: [T] = [] var count: Int { return..

안녕하세요 Pingu 입니다.🐧 Swift에는 Queue 자료구조가 따로 없어서 직접 만들어야합니다.😂 참고로 Queue는 FIFO(First In First Out)의 구조를 갖는 자료구조입니다. 매번 만드는게 귀찮아서 이렇게 따로 글을 남기려고합니다. Queue를 만드는 방법에는 다양한 방법이 있지만 이번 글에서는 간단하게 배열 2개로 만든 Queue를 만들었어요. Swift에서는 배열을 뒤집는 reversed() 메서드의 시간복잡도가 O(1) 이므로 Queue와 같은 성능을 낼 수 있다고 봅니다. Queue의 가장 기본적인 기능들만 구현했습니다. 감사합니다. // Mady By Pingu class Queue { var enqueue: [T] var dequeue: [T] = [] var count..

안녕하세요 Ick입니다. 오늘은 여러 정렬 알고리즘 중 힙 정렬에 대해 공부했고 그에 대한 내용을 정리해볼까 합니다! 힙 정렬 (Heap Sort) 우선 정렬 알고리즘에는 버블 정렬, 병합 정렬, 퀵 정렬 등 여러 방법이 있는데요, 힙 정렬은 그중 시간 복잡도 O(N*logN)의 성능을 보이는 정렬 알고리즘입니다! 이러한 힙 정렬을 이해하기 위해선 힙(Heap)이라는 개념을 이해하셔야 합니다. 가장 중요한 것은 완전이진트리구조를 갖는다는 것입니다. 힙에는 최대 힙, 최소 힙이 있는데 최대 힙은 부모 노드가 자식 노드보다 값이 큰 힙을 말하며, 최소힙은 부모 노드가 자식 노드보다 값이 작은 힙을 말합니다. 그림으로 힙을 살펴보면 위와 같습니다. 최대 힙같은 경우엔 부모 노드가 자식 노드보다 커야 하므로 자..

안녕하세요! Ick입니다. 최소 비용 신장 트리 - Minimum Cost Spanning Tree 오늘은 여러 알고리즘 중에서 최소 비용 신장 트리라고 불리는 알고리즘에 대해 알아보려고 합니다! 최소 비용 신장 트리, 최소 스패닝 트리라고 불리는 이 알고리즘은 가중치 무방향 그래프에서 모든 정점을 연결할 때 최소의 비용으로 연결할 수 있는 방법을 찾는 알고리즘입니다. 가중치 무방향 그래프는 무엇일까요? 위와 같이 그래프가 있을 때 정점 사이에 가중치가 있고 간선에 방향이 없는 그래프를 가중치 무방향 그래프라고 합니다. 예를 들어 위의 그래프에서 정점 1에서 정점 3으로 가고 싶다면 25의 가중치를 가진 간선을 사용하면 되는 것입니다. 이번 글에서 배울 최소 비용 신장 트리는 이러한 그래프에서 모든 정점..

문제 링크 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지..

문제 링크 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 ..

문제 링크 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 문제 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때,..

문제 링크 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai..