전체 글 (32) 썸네일형 리스트형 백준 10075 친구 (IOI 2014 Day 2 2번) (2023-08-29 수정 : 제 블로그 코드를 치팅하는(그대로 배껴서 내는) 경우가 너무 많아서 코드를 삭제했습니다.) 문제 설명(링크): https://www.acmicpc.net/problem/10075 10075번: 친구 0, ... , n-1로 번호가 매겨진 n명의 사람으로 구성된 소셜 네트워크를 만들자. 이 네트워크에 있는 사람들 중 어떤 쌍은 서로 친구가 된다. 즉, 사람 x가 사람 y의 친구가 되면, 사람 y도 사람 x의 친 www.acmicpc.net 문제 요약 특이한 그래프가 주어지고, 정점마다 가중치가 있어서 최대 독립 집합을 찾아야 한다. 풀이 우선 그냥 최대 독립 집합을 구하는 문제는 매우 어려운 문제고, NP라 다항시간 풀이도 없다. 그러나, 트리의 경우라면 매우 쉬워진다. $d.. 백준 21794 Navigation 2 (JOISC 2020/2021 Day 4 2번) 문제 설명(링크) https://www.acmicpc.net/problem/21794 21794번: Navigation 2 C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net 풀이 14는 조금 어렵고, 13은 어렵고, 12는 더 어렵다. 14 풀이 x좌표, y좌표가 3의 배수인 칸마다 14를 쓴다. 하나의 14 주위의 8개의 칸을 다음과 같이 번호를 붙이자. 0 1 2 3 14 4 5 6 7 7번 칸은 현재는 사용하지 않는다. 아무 수나 채우자. 14가 가운데에 위치한 3*3의 영역을 블럭이라 하자. 한 블럭의 14를 기준으로, 그 블럭과 $i$번째 도착점의 상대적인 위치관계를 아래 표와 같이 표시하자. 14가 .. 백준 15776 New Home (APIO 2018 A번) 문제 설명(링크) https://www.acmicpc.net/problem/15766 15766번: New Home Wu-Fu Street is an incredibly straight street that can be described as a one-dimensional number line, and each building’s location on the street can be represented with just one number. Xiao-Ming the Time Traveler knows that there are n stores of k store www.acmicpc.net 문제 요약 1차원 직선에 여러 가게가 있고 종류는 1부터 $K$이다. 각 가게는 $[a_i, b_i]$시간동안 .. 이전 1 ··· 5 6 7 8 9 10 11 다음
