문제   설명  처음에는 문제의 해석이 잘 되지 않아서 푸는데 애를 먹은 문제이다.주어진 문제를 쉽게 해석하는 능력이 아직 부족한 것 같다.   일단 이 문제는 N개의 센서의 정보를 수집하는 최대 K개의 집중국을 세울 때 수신 가능 영역 길이의 합의 최솟값을 구하는 문제이다.  이게 대체 무슨 소리지? 싶겠지만 이를 쉽게 해석해보면 N개를 K개의 구간으로 나눌 때 구간 내의 간격의 합이 최소가 되도록 하는 값을 구하면 된다.    예제1번의 센서를 좌표위치에 따라 오름차순 정렬을 하였을 때의 센서간의 간격을 나타낸 그림이다. 이때 2개의 구간으로 나누려면 센서는 2개가 필요하고 (집중국 하나 = 해당 집중국 담당하는 하나의 구간)2개의 구간으로 나누게 되면  센서간의 간격중 1개가 사라지게 된다.  즉,..

문제    처음 이 문제를 접했을 때는 dfs로 풀어주려고 했지만 범위를 자세히 보면 dfs로 구현할 시 시간초과가 발생한다는 것을 알 수 있다. 그래서 이를 해결하고자 DP를 사용해서 문제를 해결 해주었다. 2차원 배열의 dp를 통해서 i번째 인덱스에서 0~20 사이의 숫자중 가능한 경우의 수를 dp[i-1]에 저장된 수를 더해서 작성해주면 된다.      따라서 i번째 인덱스에서 j라는 숫자를 만드는 경우의 수를 구해 나가는 방식으로 생각하면 된다   코드n = int(input())nums = list(map(int,input().split()))dp = [[0]*21 for _ in range(n-1)]dp[0][nums[0]] = 1for i in range(1,n-1): for j in ..

문제  처음 이 문제를 접했을 때는 감이 전혀 안잡혔다.. 범위가 너무 커서 하나하나 구하는 방식으로는 무조건 시간초과가 날 것 같은데 딱히 다른 방법이 생각나질 않았다 그래서 구글링의 도움을 받은 결과 "조합" 을 사용해서 풀 수 있다는 것을 알게 되었다.  조합이면 더 시간 초과 나는거 아냐?? 할 수도 있지만 사실 최대 감소하는 수는 정해져있다 9876543210 으로 10자리 숫자이다.그러므로 10자리 숫자까지의 조합을 구해주면 되는데 여기서 중요한건 감소하는 수  = 서로 다른 숫자의 모임 이라는 것이다. 동일한 숫자가 있는 경우는 감소하는 수가 아니기때문에 감소하는 수는 각 자리의 숫자가 모두 다르다.그리고 각 자리의 숫자가 내림차순으로 정렬된 것으로 보면 된다.  결론은 1자리 숫자부터 10..

문제 이 문제의 key point는 빗물이 고이기 위해서는 양옆이 블록으로 막혀있어야 한다는 것이다. 그렇기 때문에 for문으로 반복문을 돌면서 현재 좌표를 기준으로 양옆에 막아주는 블록이 있어서 현재좌표에 빗물이 고일 수 있는지 여부를 체크해주었다. left_max = max(arr[:i+1])right_max = max(arr[i:])compare = min(left_max,right_max) 현재 좌표 i의 양옆에서 각각의 max를 구한후 둘 중 작은 값을 구해준다. (현재 좌표에 빗물이 고이는 경우 더 작은 값과 비교를 해서 빗물이 얼마나 고였는지 판단해야되기 때문) 그 후 현재 좌표보다 높은지 (그래야 현재 좌표에 빗물이 고일 수 있음) , 그리고 양옆 블록이 0보다 높은지 (0이면 비가 고일 ..

문제   이 문제를 보았을 때 딱히 어떤 알고리즘을 사용해야겠다는 생각은 안들고 단순 구현인 것 같았다.  이 문제는 다각형의 넓이를 구하는 공식을 이용해서 풀어주면 되는데 이 공식을 모른다면 풀기가 까다로운 문제인 것 같다...(구글링 해보고 알게됨)  공식 참고 : https://darkpgmr.tistory.com/86 다각형 도형의 면적(넓이) 구하기프로그래밍 등을 할 때 알아두면 유용한 다각형의 면적 구하는 방법입니다.(오랜만에 수학관련 포스팅을 합니다 ^^) 1. 2차원 평면에서 세 점의 좌표를 알 때 삼각형 면적 구하기 세 점의 좌표를 (darkpgmr.tistory.com  이 내용을 참고하면 다각형의 넓이를 구하는 공식은   이렇게 된다는 것을 알 수 있다.  이를 코드로 구현하면  n ..

문제   박스에 20개가 들어갈 수 잇고 50미터당 한 병이기때문에 노드별 최대 간격은 1000미터이다. 따라서 노드간의 간격이 1000를 넘는다면 sad가 되고 전부 1000미터 이하라면 happy를 출력하면된다. 사용할 알고리즘은 인접한 노드부터 간격을 체크하면 되므로 BFS를 사용해주었다.  나의 풀이from collections import dequedef bfs(): q = deque() q.append((home[0],home[1])) while(q): x,y = q.popleft() if abs(x-dest[0]) + abs(y-dest[1]) 기존의 bfs에서 1000미터 이하의 간격일때만 해당 노드를 큐에 추가해주는 방식으로 구현한다고 생각하면 된다.

문제   이 문제를 처음 봤을때는 쓸 수 있을 법한 알고리즘이 쉽게 생각나지는 않았다. 그나마 생각난게 스택 또는 큐를 활용하면 될려나 하는 생각만 들었다. 그래서 일단 주어진 예시대로 차근차근 계산해가면서 규칙을 찾아보았다.   이 예시를 기준으로 생각해보자 앞에 시작 부분은 막대기가 주어지지 않은채 () 레이저가 왔으므로 0 그다음에 ((( 이렇게 막대기가 3개가 오는 것을 알 수 있다. 그리고 그 후에 () 레이저가 와서 기존에 있던 3개의 막대기를 자른 다는 것을 알 수 있다. 그리고 또 레이저가 와서 현재 기준 3개인 막대기를 또 자른다 그러고 ) 가 와서 이 이후에는 막대기가 두개가 된다. 결론은 () 이렇게 오는 레이저 말고 ((( 이런식으로 여는 괄호만 올 때 =  막대기가 시작될 때 이므..