본문 바로가기

알고리즘

[알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java)
Dot Algo∙ DS/알고리즘 개념 2022. 1. 1. [알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java) 매칭 문제 (Matching Problem) N명의 유치원생이 소풍을 가는데, 단독 행동을 막기 위해 둘씩 짝을 이뤄 같이 다니게 하려고 한다. 단 서로 사이가 안 좋은 학생끼리 짝을 지어 주면 떨어져서 따로 다니기 때문에, 사이가 좋은 학생끼리만 짝을 지어 주고 싶다. 이런 규칙 하에서 모든 학생에게 짝을 지어 줄 수 있을까? 불가능하다면 최대 몇 쌍이나 만들 수 있을까? 그래프로 간단하게 표현할 수 있다. 각 학생을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 부른다. (a) 굵은 회색으로 표시한 간선들은 끝점..
[BOJ] 백준 9663번 N-Queen 백트래킹 (Java)
Dot Algo∙ DS/PS 2021. 5. 14. [BOJ] 백준 9663번 N-Queen 백트래킹 (Java) #9663 N-Queen 난이도 : 골드 5 유형 : DP / 백트래킹 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ▸ 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) ▸ 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 문제 풀이 백트래킹의 대표문제이다. DFS를 통해 모든 경우를 탐색하되 백트래킹을 사용..
[프로그래머스] 2021 카카오/ 매출 하락 최소화 (Java)
Dot Algo∙ DS/PS 2021. 5. 6. [프로그래머스] 2021 카카오/ 매출 하락 최소화 (Java) #7 매출 하락 최소화 2021 카카오 블라인드 난이도 : LEVEL 4 유형 : 트리 순회 / DP 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr [문제] 직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완..
[BOJ] 백준 1916번 최소비용 구하기 (Java)
Dot Algo∙ DS/PS 2021. 4. 29. [BOJ] 백준 1916번 최소비용 구하기 (Java) #1916 최소비용 구하기 난이도 : 골드 5 유형 : 그래프/ 최소비용(Dijkstra) / 우선순위 큐 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net ▸ 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. ▸ 입력 첫째 줄에 도시의 개수 ..
[알고리즘/ 그래프] 서로소 집합 자료구조 Union-find (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 21. [알고리즘/ 그래프] 서로소 집합 자료구조 Union-find (Java) 서로소 집합(Disjoint Sets)이란? 서로소 집합(Disjoint Sets)은 공통원소가 없는 두 집합을 뜻한다. 서로소 집합 자료구조 (Union-find) 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로, 합치기 찾기(Union-find) 자료구조라고도 불린다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다. Union(합집합) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 Find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 동작 과정 서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다. 합치기(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. A와 B의 루트 노드 A', B'를 ..

티스토리툴바

티스토리툴바