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

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

유사도(similarity)와 거리(distance)는 무슨 차이가 있을까?(+ cosine distance vs. euclidean distance)

유사도와 거리는 밀접한 관계가 있다고 생각할 수 있다. 거리가 클 수록 유사도는 떨어진다. 비교하는 특징은 같으나 측량하는 관점에서는 서로 반대라는 것이다. 두 데이터 X,Y의 거리함수(distance function) d는 수학적으로 다음과 같이 정의한다. 위 식을 모두 만족하는 d가 거리함수다 유사도함수 s(X,Y)는 실수값을 출력하는 함수로 특별한 정의는 없다. 그래서 조금 더 일반적이다(general) 유사도함수가 특별히 [0,1]내에서 값을 가진다고 하면 두 함수 의미의 서로 반대의미와 identity-discening에 주목하여 유사도함수가 위의 거리함수의 공리를 모두 만족한다면 완벽하게 혼용해서 사용할 수 있다. 그런데 모든 유사도함수가 위의 조건을 만족할까? 그렇지도 않다. 지금 당장 생각..

• format_list_bulleted 딥러닝 기초
• · 2022. 2. 7.
• textsms

두 벡터 사이의 거리와 각도

1. 두 벡터 사이의 거리 벡터의 뺄셈을 이용 두 벡터 $x$ , $y$의 거리는 두 벡터의 뺄셈 $x-y$의 norm과 같다 2. 두 벡터 사이의 각도 L2 norm 에서만 정의됨 2-1) n차원에서 정의한 the law of cosines 위 그림에서 아래 등식이 성립하는데 코사인 법칙이라고 부른다. 참고로 우리나라만 제1,2코사인법칙을 나눈다 세계적으로는 위와 같은 등식을 코사인법칙이라 한다 2-2) 두 벡터의 내적(dot product) 대응하는 성분의 곱의 합 cosine을 이용하여 구할 수도 있다. 그림2에서 c의 값은 두 벡터 a와 b의 뺄셈 a-b의 norm으로 구할 수 있고 코사인법칙과 \[a\cdot b = \left\| a \right\|\left\| b \right\|cos\thet..

• format_list_bulleted 선형대수학
• · 2022. 1. 6.
• textsms