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,.. 순서대로 매겨준다...
1. 무향 그래프에서 사이클 union find 알고리즘을 이용해서 쉽게 판단할 수 있다 https://deepdata.tistory.com/432 union find 알고리즘 활용 - 사이클을 판별하는 방법 -1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에deepdata.tistory.com 간선을 확인하면서, 간선을 연결하는 두 노드의 대표자가 서로 같다면 사이클이 발생하는것이고, 서로 다르다면 union을 수행하면 된다 2. 유향 그래프에서 사이클 한 노드에서 출발했다가, 다른 노드들을 거쳐 이동하다보니 출발 노드로 돌아오면 사이클이 존재한다고 한..
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..
1. 문제 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 핵심은 눈치 잘 챘는데.. 시간의 압박에 못이겨서 그런건지 시간초과에서 못벗어났다.. 다시 풀어보니까 시간복잡도를 생각해서 기본에 충실하게 DFS 그래프 탐색을 구현한다면 생각보다 쉽게 풀 수 있더라고 평면에 도넛, 막대, 8자모양 그래프가 여러개 있는데.. 이 그래프와 무관한 하나의 정점을 생성하고 이 정점과 각 그래프의 임의의 정점 중 하나에 연결시켰다 무관한 하나의 정점 번호와 도넛, 막..
1. 문제 11429번: Tree (acmicpc.net) 11429번: Tree The input file contains the description of the tree. The first line of the input file contains one integer N, 2
1. 문제 D - Erase Leaves (atcoder.jp) D - Erase Leaves AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가? 평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라 리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까, 1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는 다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
