트리에서 임의의 노드에서 모든 노드를 적어도 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

추천시스템 평가 방법

사용자별 상품에 대한 평점을 원소로 가지는 행렬데이터를 생각 평점을 주지 않거나 구매하지 않은 경우에 대해서는 원소가 비어있다.     주어진 데이터를 적절한 비율의 훈련데이터와 평가데이터로 나누고  평가데이터는 추천시스템 모형을 만드는데 사용하지 않는다. 주어지지 않았다고 가정하자.    훈련 데이터를 이용해 만든 추천 시스템으로 평가 데이터의 빈 곳을 추정함     실제 평가데이터와 추정된 평가데이터를 비교하여 모형의 성능을 평가  비교하는 지표로는 MSE,RMSE부터 여러가지를 사용함     추정한 평점으로 순위를 매긴 후 실제 평점으로 매긴 순위와의 상관계수 추천한 상품 중 실제 구매로 이루어진 것의 비율 추천의 순서나 다양성까지 고려한 여러 지표들

• format_list_bulleted recommendation system
• · 2024. 7. 5.
• 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

무방향 연결그래프에서 정점의 성질 관찰하기

18668번: Find the Vertex (acmicpc.net)   무방향 연결그래프가 주어지고, self-loop나 multiple edge가 없다. 정점의 번호가 1번부터 n번까지 되어있고, 시작정점 s번에서 다른 정점까지의 거리를 3으로 나눈 나머지가 배열로 주어진다. 여기서 s가 무엇인지 찾는 문제 n,m 제한이 50만이다보니, 하나하나 해보기는 어렵다. 일단 거리 배열에서 0인 값인 정점 번호가 일단 정답 후보가 될 것이다. 시작정점 s에서 거리가 3,6,9,... 3의 배수여도 0이기 때문에 정답이 아닌 정점이 있을 수도 있다. 또 하나 알 수 있는 점은, 시작정점 s라면 인접한 정점까지 거리는 무조건 1이다.   물론 위 그림과 같이 s에서 인접한 3개 정점과 똑같이 인접한 어떤 정점 A..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 5. 10.
• 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

Python 제곱근 연산 **(1/2)를 함부로 하면 안되는 이유

10216번: Count Circle Groups (acmicpc.net) 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 각 위치 A[i]가 (x,y)를 중심으로 가지고 반지름은 r인 원으로 주어지는데... 두 원이 서로 닿거나 겹친다면 두 원은 통신이 가능하다. 두 원이 서로 닿거나 겹칠려면 어떻게 해야하나? 두 원의 중심사이 거리 AB랑 r1+r2를 비교하면 된다. AB = (r1+r2)이면 두 원이 서로 닿는것이고 AB < (r1+r2)이면 두 원이 서로 겹치는 것이다. 원의 개수가 ..

• format_list_bulleted 알고리즘 일반
• · 2024. 4. 12.
• textsms