2부 3 부 4부 저는 개발자들이 "StringBuilder 작업"이라고 부르는 Java 멀티스레딩 퀘스트의 유해한 작업으로 인해 이 기사를 작성하게 되었습니다. 그녀의 조건의 본질은 일련의 단어(어린이의 단어 게임을 연상시키는 도시 이름이 주어진 조건에서)가 도미노 원리에 따라 배열되어야 하고, n' 단어의 마지막 문자가 배열되어야 한다는 것입니다. (n+1) go의 첫 글자와 동일하며, 주어진 (개별적으로) 모든 단어가 이러한 체인으로 추가되는 것으로 알려져 있습니다. 원하는 단어 체인에 대해 여러 옵션을 구성할 수 있다면 어느 것이든 솔루션으로 채택되었습니다. 조건이 단순하고 명쾌해 보임에도 불구하고 문제 해결은 결코 쉽지 않았으며 StringBuilder를 능숙하게 사용해도 상황이 해결되지 않았습니다. 문제의 개발자는 JavaRush 생도를 한 번 이상 겁에 질린 Linear Chaos 행성에서 동형체를 주문한 것으로 밝혀졌습니다. 예상대로, 피상적인 솔루션은 유효성 검사기에 적합하지 않았습니다. 왜냐하면 순진한 알고리즘이 단어를 건너뛰도록 강제하는 체인이 항상 있었기 때문입니다. 문제를 복잡하게 만드는 반면 일반적인 경우에 해결책을 더 가까이 가져오지 못하고 단순한 조건이 똑같이 간단한 해결책을 가져야 한다는 느낌을 점점 더 강화시키는 추가적인 "목발"을 쌓아야 했습니다. 나는 전술을 바꾸고 좀 더 근본적인 영역으로 들어가야 했습니다. 나는 어떤 경우에도 나 자신을 그래프 이론의 전문가라고 생각하지 않는다는 점을 즉시 예약하겠습니다. 내가 다룰 주제는 아마도 도미노 단어 문제를 해결하는 범위를 거의 벗어나지 않습니다. 이론적 성격의 몇 가지 일탈. 그래서, 그래프. 그래프란 무엇입니까? 그래프 는 서로 연결된 정점의 모음(집합, 집합, 목록 등 무엇이든)입니다 . 연결은 일반적으로 가장자리 라고 하며 정점은 노드 또는 노드 라고도 합니다 . 이것은 그래프입니다. 이것은 그래프이기도 합니다. 모서리에 대해 방향이 있다고 말할 수 있다면 이 그래프를 지향성 그래프라고 합니다 . 처음 두 그림의 그래프는 방향성이 없습니다 .. 우리는 모서리 (u, v)가 모서리 (v, u)와 동일하다고 말할 수 있습니다. 즉, 예를 들어 모서리 (0, 4)와 (4, 0)은 동일한 모서리입니다. 유향 그래프의 가장자리에 있는 화살표는 가장자리(u, v)가 정점 u에서 정점 v까지의 경로이고 가장자리(v, u)가 존재하지 않음을 의미합니다. 세 번째 그림에는 모서리(E, A)가 있습니다. 모서리(A, E)가 없습니다. 마지막 그림을 자세히 살펴보겠습니다. 정점 F에는 가장자리가 전혀 없다는 것을 알 수 있습니다. 이는 매우 가능합니다. 또한 정점 A 근처에 가장자리가 나타났습니다(루프). 정점 B와 D 사이에는 방향이 다른 두 개의 가장자리가 있습니다. 방향성 그래프는 이러한 아티팩트를 허용합니다. 그래프가 서로에게 선물을 주는 지인 그룹을 설명한다고 가정해 보겠습니다. 탐욕스러운 F는 아무에게도 아무것도 주지 않았고, B와 D는 선물을 교환했으며(각각 다른 사람에게 선물을 주었다는 사실을 제외하고), A는 자신에게 선물을 주었는데, 아마도 문제를 성공적으로 풀었을 때였을 것입니다. 행성 선형 혼돈에서 문제. 그런데 그래프의 정점은 숫자이거나 숫자를 포함할 필요가 없으며 오히려 컨테이너입니다. 어떤 물건이라도 저장할 수 있습니다. 그래프는 연결에 대한 설명입니다. 나중에 우리에게 유용할 중요한 용어인 정점에 연결된 가장자리의 수(또는 그에 부수되는 가장자리 수 ) 를 주어진 정점의 각도 라고 합니다 . 예를 들어, 첫 번째 그림에서 꼭지점 0의 차수는 2, 1의 차수는 4, 3의 차수는 3, 두 번째 그림의 꼭지점 0의 차수는 1입니다. 이 기사에서는 다양한 유형의 그래프에 대해 자세히 다루지 않겠습니다. 가중치 그래프도 있다는 점만 언급하겠습니다. 통과의 "가격"을 나타내는 특정 숫자가 각 가장자리에 부착되어 있습니다. 연결된 그래프에는 해당 속성으로 구별되는 여러 하위 유형이 있습니다. 예를 들어, 가장자리가 어느 곳에서도 순환을 형성하지 않는 그래프를 트리라고 하며(예를 들어 "레드-블랙 트리"와 같은 멋진 이름을 가진 흥미로운 계열이 있음) 다양한 중요한 알고리즘 및 데이터 구조에 널리 사용됩니다. 문제를 해결하기 위해 그래프를 사용하는 것 이 모든 것이 매우 흥미롭다고 말씀하시지만, 이 모든 것이 일련의 단어를 구성하는 것과 무슨 관련이 있습니까? 가장 직접적인 것이 밝혀졌습니다. { Amsterdam Melbourne New York Kyiv Vienna } 조건의 테스트 예를 살펴보겠습니다. 단어가 달라붙는 "노드" 문자({A, M, N, K, B})를 임의의 순서로 적고 이를 단어와 연결해 보겠습니다. 보시다시피 노드가 문자인 유향 그래프가 있습니다. 가장자리는 단어이며 연결됩니다. 정점에서 정점으로 모든 가장자리를 탐색하여 각 가장자리를 한 번만 방문하는 방법을 찾으면 문제가 해결될 것입니다. 다이어그램의 노드를 약간 다르게 배포해 보겠습니다. 이제 그래프가 닫힌 루프라는 것을 더 잘 알 수 있습니다. 어떤 단어로든 시퀀스를 시작할 수 있으며 이는 올바른 결정이 될 것입니다. 그러나 문제의 조건을 보면 어느 하나의 솔루션으로도 충분하다는 것을 알 수 있습니다. Vena를 Vladimir로 바꾸겠습니다. 두 가지 결과가 나타납니다. 첫째, 새 정점인 문자 P를 추가해야 했고, 둘째, 더 이상 그래프를 반복할 수 없다는 것을 알 수 있습니다. 위의 내용을 모두 요약하고 두 가지 새로운 용어를 소개하겠습니다. 1. 각 모서리를 한 번만 방문하여 모서리를 횡단할 수 있는 연결된 그래프를 "오일러 경로"를 포함하는 그래프라고 합니다 . 이러한 그래프의 특징(모서리가 없는 꼭지점이 없다는 점 제외)은 2개(그리고 단 2개만)를 제외한 모든 꼭지점의 차수가 짝수 라는 것입니다 . 2. 원래의 노드로의 복귀가 가능하다고 밝혀지면 그래프에 “오일러 순환” 이 있다고 말합니다 . 이러한 그래프의 특징(모서리가 없는 꼭지점이 없다는 점 제외)은 모든 꼭지점의 차수가 짝수라는 것입니다. 다음과 같은 도시 목록을 상상해 봅시다: {Moscow Anapa Adler Rostov-on-Don 무한}. 그래프를 만들어 봅시다. 다이어그램에서 이 그래프에 오일러 경로가 있음을 알 수 있습니다. 홀수 차수를 갖는 꼭짓점은 두 개뿐입니다. 이들은 M과 L이고 나머지는 짝수입니다. A의 차수는 4입니다. 루프는 두 번 계산되고 P와 Y의 차수는 2입니다. 이 체계를 기반으로 오일러 경로를 구축할 수 있는 알고리즘을 생각해 보면 예를 들어 목록 {M, A, A, P, Y , L}, 그러면 우리는 문제를 해결할 것입니다. 왜냐하면 주어진 순서대로 단어를 출력하는 것은 기술의 문제일 뿐입니다. 따라서 도미노 단어 문제에 대한 해결책은 유향 그래프에서 오일러 경로 (주기가 "자유"임)를 찾는 알고리즘을 구현하는 것입니다. 다음 ->
이것은 그래프이기도 합니다. 
모서리에 대해 방향이 있다고 말할 수 있다면 이 그래프를 지향성 그래프라고 합니다 . 
처음 두 그림의 그래프는 방향성이 없습니다 .. 우리는 모서리 (u, v)가 모서리 (v, u)와 동일하다고 말할 수 있습니다. 즉, 예를 들어 모서리 (0, 4)와 (4, 0)은 동일한 모서리입니다. 유향 그래프의 가장자리에 있는 화살표는 가장자리(u, v)가 정점 u에서 정점 v까지의 경로이고 가장자리(v, u)가 존재하지 않음을 의미합니다. 세 번째 그림에는 모서리(E, A)가 있습니다. 모서리(A, E)가 없습니다. 마지막 그림을 자세히 살펴보겠습니다. 정점 F에는 가장자리가 전혀 없다는 것을 알 수 있습니다. 이는 매우 가능합니다. 또한 정점 A 근처에 가장자리가 나타났습니다(루프). 정점 B와 D 사이에는 방향이 다른 두 개의 가장자리가 있습니다. 방향성 그래프는 이러한 아티팩트를 허용합니다. 그래프가 서로에게 선물을 주는 지인 그룹을 설명한다고 가정해 보겠습니다. 탐욕스러운 F는 아무에게도 아무것도 주지 않았고, B와 D는 선물을 교환했으며(각각 다른 사람에게 선물을 주었다는 사실을 제외하고), A는 자신에게 선물을 주었는데, 아마도 문제를 성공적으로 풀었을 때였을 것입니다. 행성 선형 혼돈에서 문제. 그런데 그래프의 정점은 숫자이거나 숫자를 포함할 필요가 없으며 오히려 컨테이너입니다. 어떤 물건이라도 저장할 수 있습니다. 그래프는 연결에 대한 설명입니다. 나중에 우리에게 유용할 중요한 용어인 정점에 연결된 가장자리의 수(또는 그에 부수되는 가장자리 수 ) 를 주어진 정점의 각도 라고 합니다 . 예를 들어, 첫 번째 그림에서 꼭지점 0의 차수는 2, 1의 차수는 4, 3의 차수는 3, 두 번째 그림의 꼭지점 0의 차수는 1입니다. 이 기사에서는 다양한 유형의 그래프에 대해 자세히 다루지 않겠습니다. 가중치 그래프도 있다는 점만 언급하겠습니다. 통과의 "가격"을 나타내는 특정 숫자가 각 가장자리에 부착되어 있습니다. 연결된 그래프에는 해당 속성으로 구별되는 여러 하위 유형이 있습니다. 예를 들어, 가장자리가 어느 곳에서도 순환을 형성하지 않는 그래프를 트리라고 하며(예를 들어 "레드-블랙 트리"와 같은 멋진 이름을 가진 흥미로운 계열이 있음) 다양한 중요한 알고리즘 및 데이터 구조에 널리 사용됩니다. 문제를 해결하기 위해 그래프를 사용하는 것 이 모든 것이 매우 흥미롭다고 말씀하시지만, 이 모든 것이 일련의 단어를 구성하는 것과 무슨 관련이 있습니까? 가장 직접적인 것이 밝혀졌습니다. { Amsterdam Melbourne New York Kyiv Vienna } 조건의 테스트 예를 살펴보겠습니다. 단어가 달라붙는 "노드" 문자({A, M, N, K, B})를 임의의 순서로 적고 
이를 단어와 연결해 보겠습니다. 
보시다시피 노드가 문자인 유향 그래프가 있습니다. 가장자리는 단어이며 연결됩니다. 정점에서 정점으로 모든 가장자리를 탐색하여 각 가장자리를 한 번만 방문하는 방법을 찾으면 문제가 해결될 것입니다. 다이어그램의 노드를 약간 다르게 배포해 보겠습니다. 
이제 그래프가 닫힌 루프라는 것을 더 잘 알 수 있습니다. 어떤 단어로든 시퀀스를 시작할 수 있으며 이는 올바른 결정이 될 것입니다. 그러나 문제의 조건을 보면 어느 하나의 솔루션으로도 충분하다는 것을 알 수 있습니다. Vena를 Vladimir로 바꾸겠습니다. 
두 가지 결과가 나타납니다. 첫째, 새 정점인 문자 P를 추가해야 했고, 둘째, 더 이상 그래프를 반복할 수 없다는 것을 알 수 있습니다. 위의 내용을 모두 요약하고 두 가지 새로운 용어를 소개하겠습니다. 1. 각 모서리를 한 번만 방문하여 모서리를 횡단할 수 있는 연결된 그래프를 "오일러 경로"를 포함하는 그래프라고 합니다 . 이러한 그래프의 특징(모서리가 없는 꼭지점이 없다는 점 제외)은 2개(그리고 단 2개만)를 제외한 모든 꼭지점의 차수가 짝수 라는 것입니다 . 2. 원래의 노드로의 복귀가 가능하다고 밝혀지면 그래프에 “오일러 순환” 이 있다고 말합니다 . 이러한 그래프의 특징(모서리가 없는 꼭지점이 없다는 점 제외)은 모든 꼭지점의 차수가 짝수라는 것입니다. 다음과 같은 도시 목록을 상상해 봅시다: {Moscow Anapa Adler Rostov-on-Don 무한}. 그래프를 만들어 봅시다. 
다이어그램에서 이 그래프에 오일러 경로가 있음을 알 수 있습니다. 홀수 차수를 갖는 꼭짓점은 두 개뿐입니다. 이들은 M과 L이고 나머지는 짝수입니다. A의 차수는 4입니다. 루프는 두 번 계산되고 P와 Y의 차수는 2입니다. 이 체계를 기반으로 오일러 경로를 구축할 수 있는 알고리즘을 생각해 보면 예를 들어 목록 {M, A, A, P, Y , L}, 그러면 우리는 문제를 해결할 것입니다. 왜냐하면 주어진 순서대로 단어를 출력하는 것은 기술의 문제일 뿐입니다. 따라서 도미노 단어 문제에 대한 해결책은 유향 그래프에서 오일러 경로 (주기가 "자유"임)를 찾는 알고리즘을 구현하는 것입니다. 다음 ->
GO TO FULL VERSION