그래프에서 역방향 간선을 놓아 노드들의 크기 순서를 찾는 테크닉(도달 가능성)

1. 문제 2458번: 키 순서  1번부터 n번까지 번호가 붙여진 학생들의 키 순서가 주어진다. 예를 들어 1번  이 결과로 모든 학생중 키가 가장 작은 학생부터 자신이 몇번째 학생인지 알 수 있는 학생도 있고,  그렇지 못한 학생들도 있다. 이러한 결과가 주어질때 자신의 키가 몇번째 학생인지 정확히 알 수 있는 학생 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------------ 상식적으로? 먼저 생각해보면 i번이 몇번째 순서인지 알고 싶다면 i번보다 키가 큰 학생의 수, 키가 작은 학생의 수를 찾..

• format_list_bulleted 그래프 이론 정복기
• · 2025. 3. 29.
• textsms

트리에서 임의의 노드에서 모든 노드를 적어도 1번 이상 방문하는데 걸리는 최소 거리

E - Tree and Hamilton Path 2 (atcoder.jp) E - Tree and Hamilton Path 2AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  트리의 어떤 정점 A에서 출발하여 모든 정점을 1번 이상 방문하고, 다시 정점 A로 돌아온다고 생각해보면, 만약 트리의 어떤 변을 제거하면 다음과 같이 2개의 연결성분이 생기고 출발점에서 다시 출발점으로 돌아올려면 두 연결성분을 서로 왔다갔다 해야하므로, 정확히 각 변을 2번 지나면 출발점에서 모든 노드를 1번 이상 방문하여 출발점으로 돌아올 수 있다..

• format_list_bulleted DFS BFS 정복기
• · 2024. 7. 11.
• textsms

DFS로 사이클 탐지하는 알고리즘 탐구하기2 -사이클의 길이-

1. 연습문제1 9466번: 텀 프로젝트 (acmicpc.net) 문제를 보면 u가 A[u]를 향하는 그래프이고 이 그래프에서 사이클을 모두 찾아 각 사이클에 속하는 노드의 개수를 구하고 전체 노드 수에서 사이클에 속하는 노드의 개수를 빼면 된다 dfs로 사이클을 탐지할 수는 있는데... 사이클에 속하는 노드의 개수는 어떻게 알 수 있을까? 노드 u1부터 u2,u3,...,un을 차례대로 방문한다고 생각해보자 u1 > u2 > u3 > .... > un 그러다가 다시 un에서 u1으로 온다면? u1 > u2 > u3 > ... > un > u1으로 오면 (u1,u2,.u3,...,un)이 하나의 사이클이 된다. 따라서 dfs로 노드를 방문할때마다, 방문한 노드의 번호를 1,2,3,.. 순서대로 매겨준다...

• format_list_bulleted 그래프 이론 정복기
• · 2024. 6. 15.
• textsms

DFS로 사이클 탐지하는 알고리즘 탐구하기1 -기본 이론-

1. 무향 그래프에서 사이클 union find 알고리즘을 이용해서 쉽게 판단할 수 있다 https://deepdata.tistory.com/432 union find 알고리즘 활용 - 사이클을 판별하는 방법 -1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에deepdata.tistory.com  간선을 확인하면서, 간선을 연결하는 두 노드의 대표자가 서로 같다면 사이클이 발생하는것이고, 서로 다르다면 union을 수행하면 된다  2. 유향 그래프에서 사이클 한 노드에서 출발했다가, 다른 노드들을 거쳐 이동하다보니 출발 노드로 돌아오면 사이클이 존재한다고 한..

• format_list_bulleted 그래프 이론 정복기
• · 2024. 6. 14.
• textsms

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