일직선 상에서 특정 위치에서 거리 합이 최소가 되도록 집을 짓는 문제

18513번: 샘터 N개의 샘터가 주어질때 K채의 집을 지을려고 한다 각 집에서 가장 가까운 샘터까지의 거리를 불행도라고 정의할때 K채의 집의 모든 불행도의 합이 최소가 되도록 집을 짓는다 그 불행도의 합의 최소를 구하는 문제 ------------------------------------------------------------------------------------------------------------------- BFS로 풀 수 있다는데 생각해봐도 감이 잘 안오더라고... 평소 BFS문제랑 조금 달라서 그런지 샘터 위치 x에서 왼쪽 오른쪽으로 -1,1만큼 봐서 비어있으면 x-1, x+1에 집을 짓고 다시 x-1에서 왼쪽 오른쪽으로 -1,1만큼 x-1,x에서 비어있으면 집을 짓고 x+1에..

• format_list_bulleted DFS BFS 정복기
• · 2025. 4. 5.
• textsms

flood fill 핵심 트릭 - 사각형으로 둘러쌓인 연결요소의 둘레의 길이(연결요소 내부 영역을 찾는 방법)

5850번: Perimeter  100*100 들판에 1*1 건초를 n개 두는데 이 건초 n개는 연결되어있다. 즉 임의의 건초에서 상하좌우로 출발하면 다른 모든 건초로 도달할 수 있다 이 연결된 영역의 둘레를 구하고 싶다. 이때 건초 더미들이 감싸고 있는 내부 구멍이 있을 수 있는데 이 구멍들의 둘레는 계산하지 않는다 예를 들어 아래 그림은 둘레가 14이다. X부분의 둘레는 계산하지 않는다   --------------------------------------------------------------------------------------------------------------------------------- 건초더미 둘레를 구해야하는데 건초더미가 감싸는 내부 구멍을 어떻게 찾아야하느냐가 관..

• format_list_bulleted DFS BFS 정복기
• · 2025. 2. 16.
• textsms

해밍거리 + BFS 경로 역추적하기

2479번: 경로 찾기 이진 코드들이 주어질때, A 이진코드에서 B 이진코드로 가는 경로를 찾을려고 한다 이때 경로를 구성한 노드간 서로 인접한 코드끼리의 해밍거리가 1이어야한다 해밍거리는 길이가 같은 두 이진코드들에서 왼쪽부터 오른쪽으로 차례로 비교할 때 서로 다른 값을 가진 비트의 수이다 예를 들어 010과 110은 서로 다른 비트가 0번째 비트로 1개이므로 해밍 거리가 1이다 코드 번호 A,B가 주어질때 가장 짧은 해밍 경로를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------- 두 코..

• format_list_bulleted DFS BFS 정복기
• · 2025. 2. 3.
• textsms

BFS로 어떤 정수의 0과 1로만 이루어진 배수 찾기

4994번: 배수 찾기 정수 N이 주어질때, N의 배수 중에 0과 1로만 이루어진 배수 M을 찾는다 1보다 큰 M의 길이는 100이 넘지 않아야하고 가능한 경우가 여러가지 있으면 아무거나 찾는다 ---------------------------------------------------------------------------------------------------------------------------------------- 100000000000000000000000000000000 해서 0인거 하나씩 1로 바꿔보고 11000000000000000000000, 101000000000000000000.... 근데 하나만 바꾸는게 아니라 문제는 2개 이상 바꿔야할수도 있잖아 11100000000..

• format_list_bulleted DFS BFS 정복기
• · 2025. 1. 28.
• textsms

퍼져나갈 수 있는지를 묻고 있지만 도달할 수 있는지를 계산해야하는 BFS

19538번: 루머 최초 루머 유포자에서 시작해서 매분마다 주변인에게 루머를 퍼뜨리는데 해당 사람은 주변인의 절반 이상이 루머를 믿고 있다면 루머를 믿게 된다 충분한 시간이 지난 후 각 사람들이 처음 루머를 믿기 시작하는 시간을 모두 구한다 ------------------------------------------------------------------------------------------------------------------------------------------- 단순하게 생각해서 유포자부터 큐에 넣어서 BFS를 수행해가지고, 방문가능한 정점에 방문해서 해당 정점의 주변 정점들 중 루머를 믿고 있는 정점 수를 찾고 그 정점 수가 주변 정점들 수의 절반 이상이면 해당 정점은 루머를 ..

• format_list_bulleted DFS BFS 정복기
• · 2025. 1. 25.
• textsms

ABC 350 D번 복기 - 직접 연결되어있지는 않지만 도달할 수 있는 경로의 개수 구하는법

D - New Friends (atcoder.jp) D - New Friends AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제를 요약하자면... 어떤 노드 X에서 직접적으로 연결되어 있지는 않지만, 다른 노드들을 거쳐서 도달할 수 있는 노드 Z가 존재한다면 그러한 경로의 개수를 구하는 문제 예를 들어 위 그래프에서 1번 노드에서 2,4번은 직접 연결되어 있고, 3번 노드는 직접 연결되어 있지 않은데, 1 > 2 > 3으로 갈 수 있으므로 1개 2번 노드에서 1,3번은 직접 연결되어 있는데 4번은 직접 연결되어 있지..

• format_list_bulleted Atcoder
• · 2024. 4. 21.
• textsms