위상정렬 재활치료하기 - 그래프에 사이클이 존재하여 정렬이 불가능한경우

1. 위상정렬 가볍게 복습 그래프의 노드를 정렬하는 위상정렬 정복하기 (tistory.com) 그래프의 노드를 정렬하는 위상정렬 정복하기 1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 deepdata.tistory.com 1) 그래프를 만들면서, 각 노드의 진입차수(indegree)를 세준다. 2) 진입차수가 0인 노드를 큐에 모두 넣는다. 3) 큐가 빌때까지 다음을 반복 3-1) 큐에서 노드를 하나 빼고, 결과 리스트에 넣어준다. 3-2) 3-1)에서 뺀 노드에서 출발하는 모든 간선을 제거 3-3) 3-2) 후에 노드의 진입차수가 0이 된 노드는..

• format_list_bulleted 위상정렬
• · 2023. 3. 17.
• textsms

문자열 비교 응용 - 다시 처음부터 되돌아가면서 비교해야할때

1. 문제 5555번: 반지 (acmicpc.net) 5555번: 반지 당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 www.acmicpc.net 2. 풀이 보통 target 문자열 찾을때는 한줄 안에서 똑같이 있는지 찾았지만 이 문제는 target 문자열이 뒤로 넘어가면 다시 처음부터 되돌아가야한다 ZAAAAAAAXY에서 XYZ를 찾고자 할때, Z XY 하면 하나를 찾을 수 있다는 뜻 어떻게 할 수 있을까 찾고자 하는 문자열 XYZ의 길이가 3이고 처음부터 끝까지 순회하는데... ZAAAAAAAXY XYZ에 도달하면 끝인데.. 여기서 YZ는 다시 처음 2글자 Z..

• format_list_bulleted 문자열 알고리즘
• · 2023. 3. 14.
• textsms

파이썬으로 두 행렬 곱하기 구현하는 방법

1. 문제 2740번: 행렬 곱셈 (acmicpc.net) 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 2. 풀이 n*m행렬과 m*k 행렬을 곱하면, n*k행렬이 되며, n*k 행렬의 원소 $c_{ij}$는 다음과 같이 정의될 것이다 $$c_{ij} = \sum_{w = 0}^{k-1} a_{iw}b_{wj}$$ 이차원 리스트를 적절히 정의하고, i,j,w의 3중 for문으로 행렬 곱셈을 만들 수 있다 from sys import stdin n,m = map(int,stdin.readli..

• format_list_bulleted 선형대수학 알고리즘
• · 2023. 3. 13.
• textsms

삼각형의 내접원의 반지름과 방접원의 반지름의 관계식

방접원과 내접원의 반지름을 이용한 관계식과 헤론의 공식 유도 : 네이버 블로그 (naver.com) 방접원과 내접원의 반지름을 이용한 관계식과 헤론의 공식 유도 안녕하세요 월조입니다 :) 오늘은 방접원의 반지름과 내접원의 반지름 사이의 관계식에 대해서 포스팅해보... blog.naver.com 1. 방접원의 성질 접선의 길이는 서로 같기 때문에 CE = CH이고 BH = BD이고 AD = AE이다. 그러므로 삼각형 ABC의 둘레는 2(x+y+z)가 된다. 여기서 BP = y'이고 CQ = z'이라고 하자. 원의 접선, 원의 접선의 길이 – 수학방 (mathbang.net) 원의 접선, 원의 접선의 길이 현에 대한 두 번째로 현의 길이에 대한 내용입니다. 원에 대해서 계속하고 있는데, 생각보다 어렵지 않죠..

• format_list_bulleted 기하학
• · 2023. 3. 10.
• textsms

컴퓨터로 원의 둘레를 추적하면서 개수를 세는 방법

1. 문제 1709번: 타일 위의 원 (acmicpc.net) 1709번: 타일 위의 원 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들이 큰 정사각형을 빈틈없이 채우고 있는데, 정사각형의 한 변의 길이는 짝수이다. 이 한 변의 길이를 Ncm이라고 하자. 큰 정사각형에 www.acmicpc.net 2. 풀이 규칙이 있나 했는데 논리로 개수를 셀 수 있는 문제였다 위 그림과 같이 1*1 타일에 대하여, 좌측 하단의 점까지 거리와 우측 상단의 점까지 거리를 구해보고.. 그 거리와 원의 반지름을 비교해본다. 타일 위에 원의 둘레가 존재한다는 것은, "좌측 하단의 점까지 거리 = 우측 상단의 점까지 거리" 이거나 "원의 반지름

• format_list_bulleted 기하학
• · 2023. 3. 10.
• textsms

삼각형의 내각의 이등분선과 외각의 이등분선 정리

1. 내각의 이등분선 삼각형의 한 내각을 이등분한 경우 다음과 같을때, a:b = c:d가 성립한다 다음과 같이 선분 AD에 평행하게 EC를 긋고, BA의 연장선과 EC의 교점이 E라고 한다면... 각 BAD = 각 BEC이다. 그러므로 그림과 같이 ACE가 이등변삼각형이고, AC = AE가 된다. 이 때, 삼각형 BAD와 삼각형 BEC는 서로 닮았다. 따라서 BA: AE = BD: DC이다. 그러므로 a:b = c:d 2. 외각의 이등분선 삼각형의 한 외각의 이등분선에 대해 다음 상황에서 a:b = c:d이다. 다음과 같이 삼각형 ABC의 각 A의 외각의 이등분선과 BC의 연장선의 교점을 D라 하고 AD에 평행한 선분을 C에서 그어 AB와 만나는 점이 E라고 한다면... 각 FAD는 FEC와 같다. 각..

• format_list_bulleted 기하학
• · 2023. 3. 9.
• textsms