브루트포스 알고리즘 (Brute force 알고리즘)
목차 브루트포스란? 복잡한 알고리즘을 굳이 생각하지않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 다 살펴보는 것을 의미합니다. brute force, BF, 완전탐색(exhaustive search), 완탐 정도로 불립니다. 설명을 위해 코딩테스트와 비슷한 형태의 문제로 예를들겠습니다. N개의 숫자를 입력받아 이 중 임의의 3개의 수를 골랐을 때, 세 수의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N과 S가 주어진다. (3 ≤ N ≤ 20, lSl ≤ 1,000,000) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초) 예를들어 만약 입력이 아래와 같이 주어졌다면, N=10, S=0이고 3개..
2023. 3. 15.
CCW를 이용한 선분 교차 여부 판정
목차 벡터의 외적과 CCW (Counter ClockWise)에서 이어지는 글 입니다. CCW가 어떤건지 이미 알고 있다면 이 글만 보셔도 이해에 문제는 없습니다. 이하 bold 처리된 대문자 $\textbf{A}, \textbf{B}$는 벡터를 뜻합니다. CCW 왜 이하와 같이 되는지 자세한 내용은 위에 링크된 '벡터의 외적과 CCW' 글을 참고해주세요. - 짧게 CCW에 대해 다시 얘기해보자. 점 $a=(x_1, y_1, 0), b=(x_2, y_2, 0), c=(x_3, y_3, 0)$ 이라할 때, $\textbf{A}=\vec{ab}=(x_2-x_1, y_2-y_1, 0), \textbf{B}=\vec{ac}=(x_3-x_1, y_3-y_1, 0)$ 이다. 따라서 $\textbf{A}\times\..
2022. 11. 22.
