Algorithm (30) 썸네일형 리스트형 [SWEA] 3000. 중간값 구하기 (with JAVA) 문제 3000 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 중간값을 구하는 방법 중에서 우선순위 큐 (Priority Queue)를 사용해보겠습니다. 삽입할 때마다 중간값을 구하는 문제로, Heap 으로 구성된 Priority Queue 를 사용합니다. 시간 복잡도는 O(nlogn) 입니다. 중간값을 구하기 위해서는 아래와 같은 규칙을 따라야 합니다. 1. 제일 처음에는 최대 힙에 삽입 2. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 큼 3. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같음. 즉, 최대 힙의 루트 노드 [SWEA] 4006. 고속도로 건설 2 (with JAVA) 문제 4006 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [ 접근 과정 ] 문제에서 이미 '최소 비용' 이라는 말이 나와있어서, 가중치를 계산하는 문제라는 것을 알 수 있었습니다. '최소 비용으로 모든 도시 간을 이동할 수 있게' 라는 부분에서 크루스칼 알고리즘을 사용하면 좋을 것 같다는 생각을 했습니다. 여기서의 간선은 도로이기 때문에 무향 그래프로 이해했고, 도로를 기준으로 최소 비용의 도로들을 선택해서 모든 도시를 이을 수 있어야 하기 때문에, 사이클이 없어야 하는 크루스칼 알고리즘으로 해결했습니다. 크루스칼 알고리즘을 공부하기에 앞서 서로소 집합을 트리로 표현하는 부분에 대해 먼저 알고 있어야 합니.. [SWEA] 1251. 하나로 (with JAVA) 문제 1251 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [ 접근 과정 ] 문제를 보면, 섬들 간의 거리를 간선의 가중치로 볼 수 있습니다. 가중치 하면 기본적으로 떠오르는 알고리즘이 다익스트라였기에 다익스트라 알고리즘을 이용해서 풀었습니다. 다만, 이전까지 다익스트라 알고리즘 기본 문제들을 풀었을 때는 간선들의 가중치가 주어졌었지만, 이번 문제는 가중치도 직접 구해야 했습니다. [ 고민했던 부분 ] 1. 각 섬들의 위치를 어떻게 저장할 것인가? 각 섬들의 위치를 저장할 때 ArrayList() 를 써야하나 고민했지만, 문제에 나온 x, y 의 범위를 고려했을 때 2차원 배열로 해도 충분할 것이라 생각해서.. [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘에서 이용되는 서로소 집합과 연산에 대해 정리해보겠습니다. 일단, 서로소는 공통으로 포함하는 원소가 없는 두 집합의 관계입니다. 아래와 같이 A, B 집합이 있을 때, 두 집합에서 공통되는 원소가 없다면 'A와 B는 서로소이다' 라고 말할 수 있습니다. 서로소 집합에서 연산은 크게 3가지가 있습니다. [ Make-Set 연산 ] >> 자기 자신인 집합을 하나 만듭니다. 즉, 자기자신이 대표원소가 됩니다. 여기서 대표원소는 부모노드가 자기자신일 때입니다. 예를 들어, 0부터 5까지 Make-Set 연산을 하게 되면 아래 그림과 같습니다. Make-Set(0) ~ Make-Set(5) [ Union-Set 연산 ] .. [Baekjoon] 백준 알고리즘(Python) 1620 - 나는야 포켓몬 마스터 이다솜 문제 1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제를 풀기 위해 알아야 할 개념은 다음과 같습니다. > dictionary 자료형 > sys.stdin.readline() 1. 문제 풀이 1) 잘못된 문제 풀이 (시간 초과) 이 문제는 딕셔너리의 키와 값을 이용해서 푸는 것이 더 효율적입니다. 아래와 같이 리스트로 접근하게 되면 시간 초과가 발생합니다. n, m = map(int, input().split()) list1 = [] res = [] for _ in.. [Baekjoon] 백준 알고리즘(Python) 10815 - 숫자 카드 문제 10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이 문제를 풀기 위해 알아야 할 개념은 다음과 같습니다. > set() > 이진탐색 이 문제는 크게 두 가지 방법으로 풀 수 있습니다. set() 을 이용하여 풀거나 이진탐색을 이용하여 풀 수 있는데, set() 을 이용하는 것이 더 간단합니다. 1. 문제 풀이 이 문제를 set() 을 이용해서 풀 때 유의해야 할 점이 있습니다. 첫 번째로 받는 숫자들은 중복을 제거해도 상관 없지만, 두 번째로 받는 숫자들은 중복을 .. 이전 1 2 3 4 다음
