Algorithm (36) 썸네일형 리스트형 분할 정복법(Divide and Conquer)(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트(병합 정렬))(Binary Search, Quick Sort, Quick Select, Merge Sort) 1. 분할 정복법이란? 2. 분할 정복법의 속성 3. 대표적인 분할 정복 알고리즘(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트) 4. 분할 정복 문제 풀이 1. 분할 정복법이란? 분할 정복 :Divide and Conquer 작은 문제로 분할하여 문제를 해결하는 방법 헝가리 출신 미국인 수학자인 폰 노이만이 병합 정렬을 통해 분할 정복을 설명한 것은 1945년이다. 엄청나게 큰 문제를 조금씩 나눠가면서 풀기 용이한 문제로 나눈 다음 다시 합쳐서 해결하자는 개념에서 출발하였다. 2. 분할 정복법의 속성 분할 정복법은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화할 수 있다. 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.. 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘(Greedy Algorithm)어떤 걸 결정해야 될 때, 그 순간 가장 좋다고 생각하는 것을 계속 선택해나가는 알고리즘 그때그때는 최적일지도 있지만, 최종적으로는 답이 최적이 아닐 수도 있다.동적 프로그래밍과 같이 쓰이며 서로를 보완한다. 그리디 알고리즘의 정의그리디 알고리즘의 특징그리디 알고리즘 문제 풀이 전략그리디 알고리즘 문제 풀이그리디 알고리즘의 정의greedy = 탐욕 = 그리디, 욕심쟁이 알고리즘"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지고 있으며,문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 그리디 알고리즘의 특징1. 전체 문제해결에서의.. 너비 우선 탐색(BFS, Breadth First Search) 너비 우선 탐색(Breadth First Search)breadth: 폭, 너비(=width)(->length) 그래프 전체를 탐색하는 방법 중 깊이 있게 먼저 탐색하는 DFS와 달리 깊이가 같은 너비를 먼저 탐색하는 BFS BFS의 정의BFS의 특징BFS와 DFS 과정 비교BFS 구현BFS 문제 풀이BFS의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.시작 정점으로 부터 가까운 정점(height가 낮은 곳부터)을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색한다.BFS는 두 노드 사이의 최소 경로를 구하는 성질이 있어, 주로 '최단 경로', '최소 몇 번', '최소 이동 횟수', '최소 연산 횟수' 등과 .. 브루트포스[2] - 재귀 함수 브루트포스 재귀함수를 사용하는 예제 문제풀이 재귀함수는 아래 4가지를 먼저 생각하고 알고리즘을 작성하는게 좋다.1. 인자구성2. 정답을 찾음3. 불가능한 경우4. 다음 경우 호출더보기어떤 재귀함수의 호출이 이전과 영향을 받지 않을 경우 다이나믹으로 바꿀수 있다. 부분수열 : 앞의 정보가 뒤의 정보에 영향을 주므로 다이나믹이 아님 다이나믹 : 앞의 정보를 몰라도 뒤의 정보 풀이가 가능한 경우.재귀 문제 풀이 6603 로또 : www.acmicpc.net/problem/96631 . 재귀 인자dfs(a : 입력으로 주어진 수, index : 선택할지 말지 결정할 인덱스, cnt : 현재까지 포함한 수의 개수2. 정답을 찾은 경우cnt ==63. 불가능한 경우index>=a.size4. 다음경우//선택lo.. 브루트포스[3]:백트레킹(backtracking) 알고리즘 중 하나인 백트레킹 설명과 문제풀이. 백트레킹(backtracking, 퇴각검샘) 백트레킹은 유망성 검사를 만족하는 경우 모든 조합의 수를 살펴보는 것이다. 유망성 검사를 만족하지 않은 경우 많은 부분 조합들을 배제할 수 있고 모든 경우의 수를 모두 찾는 것보다 훨씬 빠르고 풀이 시간이 단축된다. 구현방법은 DFS와 같은 구조이지만 유망성 점검을 하냐 안하냐로 구분된다. 어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. 브루트포스는 모든 방법을 만드는 것이나, 백트레킹은 아무리 해봤자 의미가 없다 싶을 때 호출을 중단하는 것. 백트레킹 알고리즘의 설명에 관해서 매우 설명이 잘되있는 블로그가 있기 때문에 참고하면 좋을 것 같다! idea-sk.. 비트마스크(BitMask) 비트마스크를 활용한 테크닉과 기법 비트마스크 자체는 알고리즘이 아니지만 다른 알고리즘과 같이 사용되어 어렵게 느껴질 수가 있다. 비트마스크(BitMask) 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법 이를 활용하면 비트연산을 통해 삽입,삭제,조회 등이 간단해짐 시간복잡도 O(1)으로 더 빠른 연산이 가능 메모리를 적게 사용함 비트 연산 AND (&) OR (|) XOR (^) SHIFT (>>,> n; for (int i = 0; i > a[i]; } for (int i = 0; i < (1 maps[i][j]; if (maps[i][j] == 'R') { r.first = i; r.second = j; } if (maps[i][j] == 'B') { b.firs.. 트리(Tree) 트리 : 사이클이 없는 그래프, 정점의 개수 : V, 간선의 개수 : V-1 루트가 있는 그래프 : 루트를 1번이라고 하며, 루트부터 아래로 방향을 정할 수 있다.부모(Parent)자식(Children)단말 정점(Leaf Node, Terminal Node) : 자식이 없는 노드형제(sibling) : 같은 부모를 가지는 노드깊이(Depth) : 루트에서 부터 거리(루트의 깊이는 0 or 1로 표기가능)높이(Height) : 깊이중 가장 큰값조상(Ancestor) : 자기자신을 포함하여 루트와 이어지는 노드자손(Descendent) : 조상과 반대트리의 지름(Diamater) : 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이 - 2번의 탐색으로 구할 수 있다. - 1. 루트에서 모든 정점까지의 거.. 그래프(Graph) 그래프(Graph) : 정의 구성 : 정점(Vertex), 간선(Edge) G = (V, E) 경로(Path) 사이클(Cycle) 단순 경로와 단순 사이클(Simple Path and Simple Cycle) : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클(일반적인 경우) 방향 있는 그래프(Directed Graph) 방향 없는 그래프(Undirected Graph,) : 양방향 그래프(Bidirection Graph) 간선 여러개(Multiple Edge) 루프(Loop) 가중치(Weight) 차수(Degree) 연결요소(Connected Component) 이분그래프(Bipartite Graph) : DFS또는 BFS 탐색으로 이분 그래프인지 아닌지 확인가능 플러드 필(Floo.. 이전 1 2 3 4 5 다음
