본문 바로가기
반응형

전체 글282

백준 20303번 할로윈의 양아치 - C++ 풀이 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 3. 배낭의 최대 용량이 K-1인 냅색 문제로 바꾸어 푼다. 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 친구끼리는 모두 한꺼번에 사탕을 빼앗기게 되므로 개인이 아니라 친구집합 단위로만 의미가 있다. 각 아이를 노드, 친구관계를 간선으로 생각하면 친구집합은 그래프의 각 연결요소가 된다. 이제 DFS/BFS 혹은 유니온파인드를 사용하여 모든 연결요소를 구해주자. 이때 각 연결요소에 속하는 노드(아이)의 개수와 각 노드에 걸린 사탕의 총합도 구한다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 이.. 2023. 7. 14.
백준 27172번 수 나누기 게임 - C++ 풀이 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 3. 각 xi에 대해 xi의 모든 약수들과 결투한다. 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 두 수가 서로 약수와 배수 관계인 경우에만 점수에 변화가 생긴다. 따라서 주어진 수들의 약수&배수 관계에만 집중하자. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 어떤 수 x의 모든 약수는 1부터 sqrt(x)까지로 모두 나누어떨어지는지 확인하는 방식으로 구할 수 있다. 만약 x가 i로 나누어 떨어진다면, i와 x/i는 x의 약수이다. 이때 i = x/i인 경우는 주의하여 처리하여야 한다. 2. 각 xi에 대해 xi의 모든 약수들과.. 2023. 7. 9.
백준 21736번 헌내기는 친구가 필요해 - C++ 풀이 1. 현재 상황을 그래프로 나타낸다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 3. 방문한 노드가 'P'인 경우 카운트한다. 1. 현재 상황을 그래프로 나타낸다. 주어진 상황은 그래프로 변환할 수 있다. 벽이 아닌 칸을 노드로 생각하고, 상하좌우로 인접한 칸들을 간선으로 잇는다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 도연이와 A라는 노드가 연결되어 있다면, 도연이는 A를 만날 수 있다는 뜻이다. 도연이와 연결된 노드를 모두 찾기 위해 'I' 노드에서 시작하는 BFS/DFS로 그래프를 탐색하자. 3. 방문한 노드가 'P'인 경우 카운트한다. 각 노드를 방문하면서 해당 노드가 'P', 즉 사람인 경우 도연이가 해당 사람을 만날 수 있음을 의미하므로 카운트 + 1.. 2023. 7. 9.
백준 20529번 가장 가까운 세 사람의 심리적 거리 - C++ 풀이 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다. 3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다. 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 비둘기집의 원리란 "n+1 마리의 비둘기가 n개의 비둘기 집에 나누어들어간다면, 적어도 한 집에는 반드시 두 마리 이상의 비둘기가 들어가게 된다"는 원리이다. 이것을 현재 문제에도 적용할 수 있다. 사람 = 비둘기, mbti 종류 = 비둘기집으로 생각하면 된다. mbti가 16종류가 있으므로, 만약 사람이 16+1=17명 있다면, 적어도 한 mbti에는 .. 2023. 7. 6.
백준 14940번 쉬운 최단 거리 - C++ 풀이 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 2. BFS의 출발 노드를 목표지점으로 설정하여 모든 칸까지의 거리를 한번에 계산한다. 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 각 칸을 노드로 생각하고 갈 수 있는 땅끼리는 연결하여 그래프를 만든다. 이제 BFS를 사용하면 두 지점 사이의 거리를 구할 수 있다. 2. BFS를 사용하여 목표지점에서 모든 칸까지의 거리를 한번에 계산한다. 각 칸에서 출발하여 목표지점까지 도달하는 BFS를 수행한다면, 총 n^2개의 칸에 대해 O(n^2)의 시간복잡도가 소요되므로 총 시간복잡도는 O(n^4)가 되어 시간초과를 받을 수 있다. 거꾸로 목표지점에서 출발하여 모든 칸을 방문하는 BFS를 진행하면 한번에 계산이 가능하다. 각 노드를.. 2023. 7. 6.
반응형

티스토리툴바