귀류법 검색 결과

해당 글 2건
귀류법 : 명제가 거짓임을 가정한다.

수학적으로 잘 설명된 포스팅은 많으니, 저는 ps 문제를 풀도록 하겠습니다. 백준 1649번 문제를 보겠습니다. 문제를 간단하게 요약하면 다음과 같습니다. 도시가 1000개 있습니다. 일방통행이 되는 도로 M개가 주어집니다. 중간 지점은 k개, C(1), ... , C(k)가 있다고 하겠습니다. A에서 출발해서 중간 지점들을 모두 거쳐서 B로 가고자 할 때, 가능한 경로의 가짓수를 구하는 것이 문제입니다. a에서 b까지 가는 도로는 최대 1개만 존재하고, 어떠한 교차로에서 출발해서, 다시 그 교차로로 돌아올 수 없다는 조건이 주어졌는데, 왜 이런 조건이 주어졌는지는 잘 모르겠습니다. 중간 지점들을 방문하는 순서는 정해진다는 관찰을 하면, 이 문제는 난이도가 상당히 쉬워 집니다. 이 관찰이 유효한 것인지 ..
자료알고/알고리즘 2020. 4. 27. 21:16
이진 검색 (binary search) : 정렬이 되어 있어야 한다.

어떠한 수가 배열 내에 있는지를 빠르게 찾고 싶습니다. 그럴 때, 이진 검색, binary search를 이용할 수 있습니다. 그런데, 전제 조건은 정렬이 되어 있어야 한다는 것입니다. 왜 그럴까요? 정렬이 되어 있지 않다고 해 봅시다. 중앙에 있는 3을 기준으로 9는 왼쪽에 있고 오른쪽에 없을 수도 있어요. 그러면 3을 기준으로 왼쪽에서 찾아야 합니다. 그런데, 이런 경우도 있을 수가 있어요. 중앙에 있는 3을 기준으로 좌측에 없고, 우측에 있다. 이런 경우는 또 어떤가요? 내가 있는 위치를 기준으로 9가 왼쪽에 있을 수도 있고, 오른쪽에 있을 수도 있고, 없을 수도 있기 때문에, 현재 탐색하는 위치를 기준으로 절반씩 해를 좁혀나갈 수가 없어요. 따라서, 선형 탐색으로 해결을 할 수 밖에 없을 거에요...
자료알고/알고리즘 2019. 7. 19. 00:10