파이썬

백준 1198번: 삼각형으로 자르기 (파이썬, 완전탐색)

완전탐색 알고리즘으로 최댓값을 구하기 위해 꼭지점을 하나씩 지워가며 그 값들을 배열에 넣고, max함수를 이용해서 최댓값을 구하였다. 삼각형의 넓이는 꼭지점들이 주어지므로 꼭지점 공식을 이용하였다. N각형에서 나올수 있는 삼각형의 경우의 수(갯수)는 nC3이므로 n(n-1)(n-2)/6이다. 완전탐색으로 풀기 위하여 N각형에서 시계방향으로 점을 하나씩 지워가며 계산하였다. 오각형을 예시로 들자면 다음과 같다. 물론 완전탐색문제는 파이썬 library인 combination을 이용하여 풀수도 있다. 완전탐색이나 조합이나 가능한 모든 경우의 수를 구하는 것이기 때문이다. 조합을 이용하여 푼 풀이는 다음과 같다. from itertools import combinations import sys def tria..

백준 14786번: Ax+Bsin(x)=C ② (파이썬, 이분탐색)

이번 주에는 이분탐색을 공부 하고있었고, 이분탐색으로 푼 문제중 난도가 가장 높았던 문제였다. 다항함수와 삼각함수의 합으로 이루어진 그래프와 상수와의 교점을 구하는 문제이기에 답이 정수로 떨어지지 않고, 오차를 허용하는 형태의 처음보는 문제였다. 구간을 정한후 이분탐색을 해야 할것 같았는데 구간을 어떻게 정할지를 구하기 위해서 그래프부터 살펴보았다. 구간을 최대한 좁게 잡아야 탐색시간을 줄일 수 있다고 생각했기 때문이다. 처음에는 탐색구간을 정하기 위해 함수의 최대값을 가지는 지점을 구하려 하였으나 y =x는 x가 무한대일때 발산하고, y=sinx는 진동하므로 x+sinx는 발산한다. 따라서 구간설정에 극대점, 최댓값등은 구간설정에 이용할 수 없을것 같았다. 다음으로 함수의 그래프를 그려보면서 A,B,C..