생각정리

백준 7576번: 토마토 (파이썬, BFS)

개인적으로 좀 어려웠던 문제였다. 왜냐하면 쉬운 BFS문제들은 보통 탐색을 한 회 할 때마다 카운트를 늘리면 되는데, 이 문제는 한 계층을 다 탐색한후에 카운트를 늘려야 했기 때문이다. 왜냐하면 1초가 지날때, 익은 토마토 주변의 토마토들이 모두 익기때문이다. 따라서 1초마다 익은 토마토 주변의 모든 토마토가 익는다는것을 구현하기 위해 입력받은 값에서 값이 1인 값들을 새로운 배열에 저장하고, 그 배열을 BFS의 입력으로 썼다. 그리고 while문 안에도 빈 배열을 선언하였는데, 입력받은 값들 중 값이 1인값들 주변을 탐색하였을 때 1초후에 값이 1이 되는 값들(0)을 배열에 모아 덱에 저장하기 위함이다. 이렇게 덱에 있는 원소(배열)를 다 탐색한 후에 카운트를 늘리면 통과한다. 또한 모두 익지는 못했을..

백준 1654번: 랜선 자르기 (파이썬, 이분탐색)

랜선을 잘라서 N개의 랜선을 만들어야 한다. 시작값을 1로 설정하고, N이 1일때는 랜선중에 가장 큰값을 써야하기때문에 max(랜선)을 끝값으로 설정하였다. 그 후 입력으로 받은 랜선들을 각각 중간값으로 나누어 그 몫을 더하고, 그 값이 N보다 크면 시작값을 중간값으로 하여 몫들의 합이 더 작아지게 한다. import sys K, N = map(int, sys.stdin.readline().split()) wires = [] for i in range(K): wires.append(int(sys.stdin.readline())) start, end = 1, max(wires) while start = N: start = mid + 1 else: end = mid - 1 print(end)

백준 1931번: 회의실 배정 (파이썬, 그리디 알고리즘)

그리디 알고리즘 문제의 유명한 예시이다. 그리디 알고리즘을 풀기 위해서는 최적해를 구해야하는데, 최적해라는것을 증명하기가 쉽지 않아 대부분 풀이를 떠올리고 반례를 생각해보는것 같다. 반례가 없으면 최적해라고 생각하는 것이다. 나도 처음에는 단순하게 끝나는 시간을 기준으로 정렬하였다. 그러나 끝나는 시간순으로 답을 골랐을때는 틀렸었다. 왜인지를 계속 고민했는데 예시에만 집중하여 끝나는시간에 중복이 있을수도 있다는 생각을 간과한 것이다. 따라서 lambda식으로 끝나는시간으로 먼저 정렬 후 그다음 정렬 순위로 시작하는 시간을 주었다. 그렇게 정렬 후 첫번째 끝나는 시간보다 큰 시간이 있으면 그 시간을 고르는 식으로 알고리즘을 짜주었더니 맞았다. import sys num = int(sys.stdin.read..

백준 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..