전체 글265 백준(BOJ) 1854 k번째 최단경로 # 다익스트라 # priority queue 기본적인 다익스트라 알고리즘에서는 1에서 출발하여 i도시 까지 도착한 최단거리 하나만 저장하면 되지만,이 문제는 조금 응용하여 버려지는 거리(최단 거리가 아닌)값 들도 나중에 사용될 수 있기 때문에 저장한다. 즉, update부분에서 모든 경로의 거리에 대해서 저장해야한다.저장할때 매 k번쨰 최단거리 즉 가장 최소값만 알면되기 때문에 priority_queue를 이용한다. # 실수 했던 점순환을 할 수 있다는 것을 생각하지 못했다.(4% 쯤에서 터짐^^) #include #include #include #include #include #include #include #include #include #include #define MAX 1005 #define I.. 2018. 7. 31. 백준(BOJ) 2213 트리의 독립집합 ** # 다이나믹 프로그래밍 너무 만만하게 생각했는데 생각보다 까다로운 디피 문제였다... 이 문제가 다른 디피들과 다른 이유에 대해서 간단하게 보자. 기본적인 하나의 디피라고 생각한다면 5개중 2개이상 연속으로 선택할 수 없을때 최대 값을 구하는 문제이다. 이 문제는 이런 기본 디피가 여러개가 연결되었을때 어떻게 해결하냐를 물어보는것 같다. # arr : 노드의 가중치 # dp[i].first : 선택 하는 경우 # dp[i].second : 선택 안하는 경우 잘 생각해 보면 다음과 같이 연결된 부분의 디피를 해결할 수 있다. dp[선택 하는 경우] = dp1[선택 안한 경우]+dp2[선택 안한 경우] ... dp[선택 하는경우] = max(dp1[선택 한 경우],dp1[선택 안한 경우]) + max(dp2.. 2018. 7. 25. 백준(BOJ) 5626 제단 ** #DP재미 있었던 문제 #풀이점화식은 생각보다 간단하다 높이가 1이 높아지거나,낮아지거나,그대로이거나 3가지 경우이기 때문에dp[i][k]=dp[i-1][k-1]+dp[i-1][k]+dp[i-1][k+1]인데문제는 이 문제의 경우 배열로 모든 높이에 대해서 만들어 주게된다면 메모리 초과가 발생한다.따라서 현재 i의 경우와 바로이전 i-1인 경우에 대해서만 저장해야한다.dp[1][k]=dp[0][k-1]+dp[0][k]+dp[0][k+1]로 해결했다. 마지막으로 처음과 끝이 무조건 0이기 때문에,dp[0][0]을 출력해주면 된다. # 실수 했던 점첫 입력이 불가능한 경우에 대해서 처리 하지 않았다. #include #include #include #include #include #include #inclu.. 2018. 7. 22. [Python_OpenCV] Templete Matching(템플릿 매칭) 매칭이란 작은 템플릿 이미지가 전체 이미지를 돌면서 가장 유사한 부분을 찾는 것을 말한다. - 템플릿 이미지 - 전체 이미지 - 코드 import numpy as np import cv2 img = cv2.imread("ori.jpg") imgray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY) w, h = imgray.shape[:2] templ = cv2.imread("templ.jpg", cv2.IMREAD_GRAYSCALE) templ_h, templ_w = templ.shape[:2] res = cv2.matchTemplate(imgray, templ, cv2.TM_CCOEFF_NORMED) loc = np.where(res >= 0.5) for pt in zip(*lo.. 2018. 7. 22. 이전 1 ··· 25 26 27 28 29 30 31 ··· 67 다음
