본문 바로가기
반응형

전체 글282

백준 1058번 친구 - C++ 풀이 1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다. 2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다. 1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다. 어떤 사람 p의 2-친구수는 k(k != p)인 모든 사람에 대해 친구 여부를 판별해서 구할 수 있다. 두 사람 A, B가 2-친구 사이인지 구하려면 두 사람 모두와 친구인 사람 C가 있는지 찾아야 하므로 O(N)의 시간복잡도가 든다. 따라서 어떤 사람 p의 2-친구수를 구하는데는 O(N^2)의 시간복잡도가 들게 된다. 2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다. 모든 사람에 대해 2-친구수를.. 2022. 6. 1.
백준 5676번 음주 코딩 - C++(cpp) 풀이 1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다. 2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결과값도 음수, 짝수개이면 양수이다. 3. 주어진 쿼리의 구간에 0이 한 개 이상 있는 경우, 결과값은 0이다. 1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다. 값의 변경이 계속 이루어지는 상황에서 구간에 대한 쿼리를 수행해야 하므로 세그먼트 트리를 이용하여 해결할 수 있다. 구간곱이 양수인지, 음수인지, 0인지만 알면 되기 때문에 음수의 개수, 0의 개수를 기록하는 두 개의 세그먼트 트리를 만들어준다. 2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결.. 2022. 5. 31.
[iOS] SF Symbols에서 이미지 systemName 확인하기 SF Symbols에서 애플 플랫폼의 아이콘 이미지 컬렉션을 볼 수 있다. (아래 링크에서 다운로드 가능) Apple Developer There’s never been a better time to develop for Apple platforms. developer.apple.com 원하는 이미지의 systemName을 확인하고 사용. Image(systemName: "square.and.arrow.down") 2022. 5. 30.
백준 11376번 열혈강호 2 - C++(cpp) 풀이 1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다. 2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다. 1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다. 직원 그룹과 일 그룹 사이의 최대 매칭의 수를 구하는 문제이다. 2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다. 각 직원당 최대 2개의 일을 할 수 있으므로, 직원을 기준으로 하는 이분 매칭을 2번 진행하여 이루어진 총 매칭의 수를 구해주면 된다. #include #include #include using namespace std; const int MAX = 1001; int N, M; vector works[MAX]; int owner[MAX]; bool visit[.. 2022. 5. 27.
백준 11375번 열혈강호 - C++(cpp) 풀이 1. 직원과 일 사이의 관계를 이분 그래프로 만든다. 2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다. 1. 직원과 일 사이의 관계를 이분 그래프로 만든다. 각 직원과 일을 정점으로 생각하고, 각 직원과 그 직원이 할 수 있는 일들을 간선으로 이어 이분 그래프를 만든다. 2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다. 최대로 할 수 있는 일의 개수는, 완성된 이분 그래프에서 직원 그룹과 일 그룹 사이의 최대 매칭의 수와 같다. 따라서 이분 매칭 알고리즘을 사용해 최대 매칭 수를 구해주면 된다. #include #include #include using namespace std; const int MAX = .. 2022. 5. 23.
반응형

티스토리툴바