문제   문제를 보자마자 딱 투포인터를 활용해서 풀어야겠다는 생각이 들었다.  시작점과 끝점을 두어 s보다 커지면 시작점을 옮기고 작을땐 끝점을 옮겨주면서 확인 해주었다.  정답코드 n, s = map(int,input().split())arr = list(map(int,input().split()))end = 0inf = float('inf')ans = infcount = 0for i in range(n): while count = s: ans = min(ans,end-i) #다음 시작점으로 이동위해 현재 시작점의 값 빼줌 count -= arr[i]if ans == inf: ans = 0print(ans)   처음에#while문 수행 이후에도 count가 s보다 작을..

문제   이 문제를 보고 처음 생각이 든 알고리즘은 LIS이다.그러나 문제는 최장 증가 부분수열이 아니라 바이토닉수열로 어떤 수를 기준으로 오른쪽 부분은 감소하는 부분수열도 찾아주어야한다.  그래서 생각한 방법은 최장증가 부분수열을 구하고 최장감소 부분수열을 구해서 이 둘의 합이 최대가 되는 지점을 찾아주는 것이다.   정답코드n = int(input())a = list(map(int,input().split()))ans = 0dp1 = [0] * ndp2 = [0] * n#최장 증가 부분수열for i in range(n): dp1[i] = 1 for j in range(i): if a[i] > a[j]: dp1[i] = max(dp1[i],dp1[j]+1)#최..

문제  이 문제는 미로찾기 문제의 꽤 까다로운 응용 버전이였다.벽을 무조건 3개 세우는데 어디다 세워야 안전영역 크기가 최대가 될지 감이 전혀 안잡혔다.  그래서 생각한 것은 범위가 그렇게 크지 않기 때문에 벽을 3개 세우는 모든 경우의 수에서의 안전 영역을 확인해주면 된다.이때 주의 해야할 것은 2차원 배열은 단순 copy가 아닌 deepcopy라는 것을 해주어야 기존의 배열의 값에 영향을 주지 않으면서 복사를 할 수 있다.  import copytmp = deepcopy(graph)  안전영역의 개수를 확인하는 것은 기존에 BFS 미로찾기 방식과 동일하다.바이러스가 퍼질 수 있는 곳을 확인해서 퍼진 후에 안전영역의 개수를 세주면 된다. def bfs(): tmp = deepcopy(graph) ..

문제   설명  처음에는 문제의 해석이 잘 되지 않아서 푸는데 애를 먹은 문제이다.주어진 문제를 쉽게 해석하는 능력이 아직 부족한 것 같다.   일단 이 문제는 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 ..

"스프링 핵심 원리- 기본편 " 강의를 진행하던 중 spring initializr을 활용해 파일을 다운 받고 이를 inteli J에서 open만 해주면 된다는데나는 계속해서 아래와 같은 오류가 발생하며 제대로 진행이 안되었다. Unknown host 'root'. Please ensure the host name is correct. If you are behind an HTTP proxy, please configure the proxy settings either in IDE or Gradle.  이를 해결하기 위해 여러가지를 시도해봤는데 먼저,IntelliJ에서 프로젝트 설정을 열기:메뉴에서 File > Project Structure로 이동.Project Settings > Project에서 다..

문제  처음 이 문제를 접했을 때는 감이 전혀 안잡혔다.. 범위가 너무 커서 하나하나 구하는 방식으로는 무조건 시간초과가 날 것 같은데 딱히 다른 방법이 생각나질 않았다 그래서 구글링의 도움을 받은 결과 "조합" 을 사용해서 풀 수 있다는 것을 알게 되었다.  조합이면 더 시간 초과 나는거 아냐?? 할 수도 있지만 사실 최대 감소하는 수는 정해져있다 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미터 이하의 간격일때만 해당 노드를 큐에 추가해주는 방식으로 구현한다고 생각하면 된다.