live the life you love

Union-Find Union-Find에 대해 알아보자 유니온 파인드는 자료구조 이므로 단독으로 쓰이기 보다, 알고리즘(크루스칼 등)에 활용된다 관련 문제 백준 1717번 집합의 표현 백준 1976번 여행 가자 기본 개념 유니온 파인드는 '집합'을 관리하는 자료구조이며 서로소 집합(Disjoint Set) 이라고도 불린다. 유니온 파인드를 활용하면 다음과 같은 작업을 할 수 있다. 원소 A와 원소 B가 같은 집합에 속하는지 확인 -- Find 함수 원소 A가 속한 집합과 원소 B가 속한 집합을 병합 -- Union 함수 방식 초기화 for (int i = 0; i n >> m; for (int i = 1; i n1 >> n2 >> cost; graph.push_back({cost,{n1,n..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 모든 경우의 수를 전부 확인해서 원하는 답을 구하는 전형적인 완전탐색 문제였다 숫자의 위치는 고정되어있고 모든 연산자를 사용해야 하므로 연산자의 순서만 정해주면된다. 사용 할 수 있는 연산자의 순서를 정할 때는 순열을 사용한다. 연산자가 최대 10개까지밖에 없으므로 파이썬 내장 라이브러리를 활용하여 풀었다. 주의할 점은 나누기 연산의 경우 음수로 나눠지는 ..

www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 조합을 구하는 문제이다. 순열과 달리, 사용했던 원소를 체크해주는게 관건이다. # 조합 n, m = map(int, input().split()) data = list(map(int, input().split())) data.sort() result = [] checked = [False]*n def dfs(idx, count): if count == m: print(*result) return for..

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 순열을 구하는 문제이다. N과 M(1)이 순열이었는데, 이와 다른점은 N과 M(5)의 경우 순열을 만들어야 할 숫자가 따로 주어진다는 점이다. 문제 조건에서 오름차순으로 출력하라고 했기 때문에 입력받은 숫자를 정렬해주기만 하면, 일반적인 순열을 구하는 것과 동일하다 이번에도 백트래킹으로 풀었다. n, m = map(int, input().split()) data = list(map(int, input(..

www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(4)는 중복 조합을 구하는 문제이다. 이번에도 내장 라이브러리를 사용하지 않고 백트래킹 방식으로 직접 구현하였다. n, m = map(int, input().split()) result = [] def dfs(idx, count): if count == m: print(*result) return for i in range(idx, n): result.append(i+1) dfs(i, count+1)..

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 연습하기 위해 내장 함수를 사용하지 않고 직접 함수를 구현해서 문제를 풀었다 N과 M(3)는 중복순열을 구하는 문제이다. 순열을 구하는 것과 크게 차이는 없고 중복된 값을 따로 체크하지 않기 때문에 따로 체크할 부분은 없다. 소스코드 n, m = map(int, input().split()) result = [] def dfs(count): if count == m: print(*result) re..

우선순위 큐 사용자 정의 비교함수 작성 우선순위 큐에 넣어서 비교해야할 요소가 3개 이상 있을 경우, 연산자 오버라이딩을 해야 한다. 이 때, 중요한 것은 단순히 리턴타입이 단순히 bool 인 함수를 만드는 것이 아닌 연산자 오버라이딩이다. struct INFO{ int y; int x; int z; }; struct cmp{ bool operator()(INFO a, INFO b){ if(a.y == b.y){ if(a.x == b.x){ return a.z b.x; // x는 오름차순 } return a.y < b.y; // y는 내림차순 } }; int main() { priority_queuepq; pq.push({1,2,3}); pq.p..

www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전의 문제 두 용액(paris-in-the-rain.tistory.com/59)에서는 절댓값 대소 비교로 문제를 풀었다. 두 문제의 차이는 정렬 여부인데, 두 용액 문제는 정렬이 안되어 있고, 이 문제는 정렬이 되어있다. 이 문제는 투포인터를 활용했다. 포인터의 시작점을 맨 처음 인덱스(p1), 맨 끝 인덱스(p2)로 두었다. 해당 인덱스의 숫자를 더하여 값을 확인한다. 두 숫자를 더해서 0에 가까운 값..

programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 해시 자료구조를 사용하는 문제였다. 해시의 특성상 key값을 기준으로 오름차순 정렬이 되는게 기본인데, 문제에서 요구하는 대로 정렬을 하기 위해서는 정렬 함수를 따로 만들어줘야 한다. 문제에서 제시하는 노래를 수록하는 기준은 다음과 같다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 ..

www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현사항만 잘 지키면 되는 전형적인 시뮬레이션 문제였다. 손님을 태우러 택시가 가는 것과, 손님을 태우고 목적지로 가는 것은 같은 방식으로 구현을 할 수 있으므로 flag 변수를 통해 1개의 함수로 처리했다. 문제해결 현재 손님의 위치, 목적지를 입력받고 각각 다른 배열에 저장한다. 비교함수를 만들어 문제의 조건을 처리한다. 가장 가까운 승객 / 행 번호 작은 승객 / 열..