알고리즘/분류 (12) 썸네일형 리스트형 분할-정복 알고리즘(Divide-Conquer) [개념] data-make.tistory.com/232 [Algorithm] 분할 정복(Divide & Conquer) # Divide & Conquer ## about - 가장 유명한 알고리즘 디자인 패러다임 - 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이�� data-make.tistory.com [관련 문제 - 1] www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicp.. 유니온 - 파인드(Disjoint Set) 핵심코드 int Find(int x) { if (x == p[x]) return x; return p[x] = Find(p[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a != b) { p[b] = a; } } KMP https://bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을 bowbowbow.tistory.com https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 입력1 banana banana ana 입력2 ABC ABCDAB A.. 구간 합(prefix sum) (feat. 2차원 배열) *개념 https://eeasyy.tistory.com/16 [백준 2167] 2차원 배열의 합 문제 출처 : https://www.acmicpc.net/problem/2167 문제 요약 정보가 담긴 2차원 배열이 주어진다. 2차원 배열 내에 주어진 구간의 합을 구하는 문제이다. 문제 풀이 이 문제는 동적 계획법을 사용하여 부분(구간.. eeasyy.tistory.com *인덱스 주의 *관련 문제 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸.. DFS와 BFS 차이 한눈에 비교 0 1 2 3 [1] 2 3 [2] 1 3 4 5 [3] 1 2 6 7 [4] 2 5 [5] 2 4 [6] 3 7 [7] 3 6 DFS : 1 - 2 - 3 - 6 - 7 - 4 - 5 BFS : 1 - 2 - 3 - 4 - 5 - 6 - 7 https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230945092&proxyReferer=https:%2F%2Fwww.google.com%2F 16. 깊이 우선 탐색(DFS) 깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 ... blog.naver.com gamedevlog.tistory.com/49 백트래킹(back tracking) G.. 그리디 https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2Fa 34. 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘은 '당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'으로 가장 단순한 형태... blog.naver.com 완전탐색 완전탐색(= exhaustive search = 브루트포스) : 모든 경우의 수를 다 해보는 것 완전 탐색 방법 5가지 - 완탐(무식하게 모든 경우 다 탐색) - 그리디(당장 눈앞의 최적해를 좇으면 전체의 최적해가 나오는 알고리즘) - 순열과 조합 - BFS(큐로 구현) / DFS(재귀함수로 구현) /백트래킹(재귀 함수로 구현) ㄴ 그림 참조 : https://m.blog.naver.com/aver2933/221912056658 - 비트마스크 출처: https://rebro.kr/59 [Rebro의 코딩 일기장] 결론 : 완전탐색 문제는 여러 가지 풀이가 있기 때문에 사용하기 편하고, 딱 떠오르는 알고리즘을 사용하면 됩니다. 완전탐색 문풀 : https://brenden.tistory.com/10 [알고.. LC"S" 01. LCS(Longest Common "Substring", 가장 긴 공통 부분 "문자열") 02. LCS(Longest Common "Subsequence", 가장 긴 공통 부분 "수열") 이전 1 2 다음
