ABC 348 D번 복기 - 그래프를 재구성하고 BFS/DFS를 해야하는 문제

https://atcoder.jp/contests/abc348/tasks/abc348_d D - Medicines on Grid AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 자체는 어디서나 많이 보던 기본적인 BFS/DFS 셋팅이다 2차원 맵에 특정 위치에 약이 있는데, 이 약을 먹으면 에너지가 E로 된다. 이동할때마다 에너지가 1씩 감소한다 약은 먹어도 되고 먹지 않아도 되는데, 단 1번만 먹을 수 있고 먹으면 사라진다 에너지 0부터 시작한다고 할때, 목표로 하는 지점에 도착할 수 있는가? 그냥 기본적인 BFS..

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

코딩테스트 복기 - 복잡한 그래프 생각하면서 효율적으로 탐색 하기

1. 문제 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 핵심은 눈치 잘 챘는데.. 시간의 압박에 못이겨서 그런건지 시간초과에서 못벗어났다.. 다시 풀어보니까 시간복잡도를 생각해서 기본에 충실하게 DFS 그래프 탐색을 구현한다면 생각보다 쉽게 풀 수 있더라고 평면에 도넛, 막대, 8자모양 그래프가 여러개 있는데.. 이 그래프와 무관한 하나의 정점을 생성하고 이 정점과 각 그래프의 임의의 정점 중 하나에 연결시켰다 무관한 하나의 정점 번호와 도넛, 막..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 2. 3.
• textsms

트리 탐색 테크닉2 - 현재 노드에서 가장 먼 자식 노드까지의 거리

1. 문제 19542번: 전단지 돌리기 (acmicpc.net) 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 2. 풀이 트리로 구성된 그래프에서 모든 노드에 전단지를 돌려야하는데, 현재 노드에서 거리가 D이하인 모든 노드에 전단지를 한번에 돌릴 수 있다고 한다 트리 구조이기 때문에 부모 > 자식으로 내려가면서 각 노드마다 가장 먼 자식 노드까지의 거리를 안다면, 어디 노드까지만 방문해도 되는지를 파악할 수 있을 것이다. 10만개의 노드가 있어서 한번의 DFS로 각 노드마다 가장 먼 자식 노드까지의 거리를 구해야..

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 15.
• textsms

트리 자료구조에 대한 개념과 트리에서의 다이나믹 프로그래밍 기본기(+트리를 만들지 않고 트리를 탐색하는 방법)

1. 그래프와 트리 그래프(graph)란 정점들과 정점 둘을 잇는 간선들로 이루어진 집합 위는 9개의 정점(원)과 10개의 간선(실선)들로 이루어진 그래프이다. 각 원의 내부에 쓰여 있는 숫자는 편의상 정점에 매긴 번호를 의미한다. 간선(edge)은 항상 두 정점을 잇게 된다. 그래프의 간선에는 가중치가 있을 수 있다. 특별한 언급이 없다면 간선의 가중치는 1로 간주할 수 있다. 가중치가 존재한다면, 예를 들어 1-3 간선의 가중치가 3이라면 1번 정점에서 3번 정점으로 가기 위해선 길이 3인 간선을 지나야한다고 표현한다. 그래프의 간선에는 방향성이 있을 수 있다. 예를 들어 1번 정점과 3번 정점사이 놓인 1-3 간선의 경우 1 > 3 또는 3 > 1 방향성을 가지는 것이 가능하다. 방향성 간선을 갖고..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 11. 29.
• textsms

ABC 328 E번 복기 cost를 modulo로 나눈 최소 스패닝 트리 구하는법

1. 문제 E - Modulo MST (atcoder.jp) E - Modulo MST AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 단순하게 최소 스패닝 트리를 바로 찾으면, cost 자체는 최소일지 몰라도 그것을 modulo로 나눈 값이 최소라는 보장은 없다 다행히 정점 N

• format_list_bulleted Atcoder
• · 2023. 11. 12.
• textsms

저울의 무게 비교를 그래프로 바꿔서 최단 거리 알고리즘으로 해결(플로이드 워셜, 그래프 탐색)

1. 문제 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 풀이 그냥 보면 어떻게 해야할지 감 잡기가 쉽지 않다.. 하지만 "2 > 3, 3 > 4로부터 2 > 4라는 것을 알 수 있다"를 봤을때, 1 > 2, 2 > 3, 3 > 4, 5 > 4, 6 > 5를 마치 방향 그래프에서 간선으로 보면 2에서 4로 도달할 수 있는가? 아닌가를 체크하면 되는 문제이다. 사실 뭐 최단 거리를 묻는 것은 아니므로 BFS나 DFS로 탐색하면 해결할 수..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 9. 7.
• textsms