반응형 전체 글311 다이나믹 프로그래밍(Dynamic Programming) : 동적 계획법 DP란? : 답을 재활용해서 다시 사용해 비효율적인 계산을 줄인다. 한 번의 계산을 통해 답을 구한다. 현재의 답을 구하기 위해서 전에 구해놨던 답을 이용해서 구한다. 피보나치 수열이 대표적인 예 2가지 방법이 있다. 1. Top-down 위에서 아래로 내려오는 것, 큰 문제를 작은 문제로 나누어 푸는 것이다. 피보나치 수열을 예로 들어 설명하자면 네 번째 피보나치 수열을 구하기 위해서는 두 번째 피보나치 수열과 세 번째 피보나치 수열이 필요하다. 또 세 번째 피보나치 수열을 구하기 위해서는 첫 번째 피보나치 수열과 두 번째 피보나치 수열이 필요하다. 이렇게 큰 문제를 작은 문제로 나눌 수 있다. 2. Bottom-up 아래에서 위로 올라가는 것, 작은 문제부터 시작해 점점 큰 문제를 풀어나가는 것이다... 2020. 4. 19. 백준 2003 수들의 합 2 [투 포인터] https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터 첨 푸는 거라 보고했다 어쩔?? 굉장히 상세하게 설명 해줬으니 밑에 참고 하시길.. https://m.blog.naver.com/kks227/220795165570 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09) 조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 .. 2020. 4. 18. 투 포인터(Two Pointers) 투 포인터는 두 곳을 가르켜서 투 포인터이다. O(n^2)의 시간복잡도가 걸리는 작업을 O(n)만에 해결해준다. 2개의 포인터를 조작해가며 원한느 작업을 수행하는 방식이다. 연속된 값들을 이용하여 풀어나가는 문제에 한정적으로 사용 가능하다. 연속성이 없다면 투 포인터 사용하기 어렵다. https://blog.naver.com/kdr06006/221803321164 투 포인터(Two Pointers) 안녕하세요.오늘은 투 포인터 알고리즘에 대해 알아보겠습니다.투 포인터 알고리즘은 시간복잡도를 크게 줄... blog.naver.com 2020. 4. 18. 플러드 필(Flood Fill) - BFS , DFS 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다. 플러드 필 문제는 BFS/DFS 알고리즘으로 해결할 수 있다. BFS는 큐로 , DFS는 스택으로 구현 할 수 있다. BFS, DFS는 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘으로, 다차원 배열이 그래프 자료구조의 특수한 형태이기 때문에 다차원 배열에서도 BFS와 DFS를 사용할 수 있다. BFS 과정 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 3번 행동을 한다. 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸.. 2020. 4. 18. 최단 경로 문제 : 플로이드-워셜 알고리즘 https://blog.encrypted.gg/917 [실전 알고리즘] 0x13강 - 플로이드 알고리즘_구버전 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 현재 보고있는 강.. blog.encrypted.gg 2020. 4. 18. BFS , DFS 란...? BFS 랑 DFS의 차이점은 BFS는 큐를 , DFS는 스택을 이용한 다는 차이 밖에 없다 또한 BFS는 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 가중치가 없는 그래프[2][3]에서는' 시작점에서 끝점까지의 최단경로를 알아낼 수 있다. 위 움짤의 BFS의 탐색 순서를 살펴볼 때 1번 노드에서 직접 연결된 곳은 2번, 3번, 4번 노드이다. 여기 있는 모든 경로의 길이를 1이라고 한다면, 1번에서 2번, 3번, 4번 노드까지의 길이는 1이다. 똑같은 방법으로 모든 노드 사이의 거리를 구할 수 있다. 따라서 시작점과 끝점이 주어진다면 주어진 그래프(네트위크)에서 최단 경로를 알아낼 수 있다. dfs 는?? https://blog.encrypted.gg/729[실전 알고리즘] 0x05강 - B.. 2020. 4. 17. 이전 1 ··· 33 34 35 36 37 38 39 ··· 52 다음 반응형