algorithm (35) 썸네일형 리스트형 그리디 알고리즘(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] - 재귀 함수 브루트포스 재귀함수를 사용하는 예제 문제풀이 재귀함수 1. 인자구성 2. 정답을 찾음 3. 불가능한 경우 4. 다음 경우 호출 더보기 어떤 재귀함수의 호출이 이전과 영향을 받지 않을 경우 다이나믹으로 바꿀수 있다. 부분수열 : 앞의 정보가 뒤의 정보에 영향을 주므로 다이나믹이 아님 다이나믹 : 앞의 정보를 몰라도 뒤의 정보 풀이가 가능한 경우. 재귀 문제 풀이 6603 로또 : www.acmicpc.net/problem/9663 1 . 재귀 인자 dfs(a : 입력으로 주어진 수, index : 선택할지 말지 결정할 인덱스, cnt : 현재까지 포함한 수의 개수 2. 정답을 찾은 경우 cnt ==6 3. 불가능한 경우 index>=a.size 4. 다음경우 //선택 lotto.push_back(a[ind.. 브루트포스[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.. 정렬(Sorting), Stable_Sorting youtu.be/kPRA0W1kECg 정렬 알고리즘을 소리로 표현한 영상이다. 정렬 방법은 30가지가 넘는 여러가지가 있다., 정렬 알고리즘의 종류로는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬, ...... 등 여러가지가 있지만, 알고리즘 문제풀이에서 주로 사용하는 것들은 정렬시간이 O(NlogN)이 걸리는 정렬을 사용한다. 정렬을 직접 구현하는 것보다는 STL에 있는 sort를 사용하는 것이 좋다. 이전 1 2 3 4 5 다음
