Algorithm

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 분석 우선 문제를 보았을 때 든 생각은 친구관계 입력을 받아 이 둘을 Union 해주어 나가면 친구관계를 연결시킬 수 있을 것 같았습니다. 여기서 문제는 친구관계를 모두 연결하고 난 후 연결되어 있는 무리 중 가장 친구비가 적은 경우를 어떻게 찾느냐! 입니다. union-find 자료구조를 처음 배울 때 두 요소를 합칠 때 ..

서로소 집합 ( union-find 자료구조) 서로소 집합이란 공통원소가 없는 두 집합을 말합니다. union (합집합) 합집합은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산을 말합니다. union으로 서로 연결된 두 노드 A, B를 확인합니다. A와 B의 루트 노드인 A', B'를 찾아 A'를 B'의 부모 노드로 설정합니다. (더 번호가 작은 원소가 부모노드가 됩니다. A' < B') 모든 union연산을 처리할 때까지 1번과 2번을 반복합니다. find (찾기) 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산으로 해당 원소의 부모노드를 알려주게 됩니다. 그림과 함께 과정을 보겠습니다! 동작과정 Step 0. 우선 노드 개수(V) 크기의 부모 테이블에 자기 자신을 부모로 가지도록 초..

여기저기서 블랙 프라이데이 행사를 하고 있으니 오늘은 블랙 프라이데이 문제를 풀어보겠습니다 : ) https://www.acmicpc.net/problem/18114 18114번: 블랙 프라이데이 첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진 www.acmicpc.net 문제 분석 선택할 수 있는 물건은 최대 3개까지이고, 같은 물건을 중복 선택하는 것은 불가능하다. 그리고 백화점에서 판매하는 물건들의 무게는 모두 다르다. 이 부분이 중요해보였습니다. 중복 선택이 불가능하고 무게가 모두 다르다고 해서 Set을 사용하여 문제를 풀었..

이진탐색이란 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 탐색 기법입니다. 이진탐색은 배열의 내부 데이터가 정렬되어 있을 때 사용할 수 있다는 특징이 있고, 시작점, 끝점, 중간점의 3가지 변수가 사용됩니다. - 시작점, 끝점 : 탐색하고자 하는 범위를 표현합니다. - 중간점 : 중간점의 데이터와 목표 데이터를 비교하기 위해 사용합니다. 이진탐색을 보기 전 순차탐색을 먼저 보겠습니다. 순차탐색 Sequential Search 💡 특정 데이터를 찾기 위해 앞에서부터 순서대로 확인하는 방법으로 정렬되지 않은 데이터에서 탐색할 때 사용합니다. 장점 : 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있습니다. 단점 : 시간복잡도가 O(N)으로 데이터가 많을 수록 비효율적입니..