Algorithm/Intermediate (20) 썸네일형 리스트형 유니온 파인드[Union Find] 유니온 파인드(Union Find) 그래프 알고리즘의 일종으로서 서로소 집합, 상호 배타적 집합(Disjoint-set)이라고도 한다. 알고리즘 문제 풀이에서는 주로 집합을 나타내며 합집합만 사용할 때 쓰인다. 여러 노드가 존재할 때, 선택한 두 노드를 같은 그래프로 합치거나 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. Parent[x] : x의 부모 노드 Find : x가 속한 집합의 root 노드를 반환하는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 Parent 초기화 vector parent(n); for (int i = 0; i 부모 자식 관계는 중요하지 않음(단지 유니온 연산을 하다가 나온것) -> 하나로 묶여 있다는것이 중요함. -> 가장 중요한것은 루트. 최종 루.. 스택 중간난이도 문제 풀이(Stack PS) 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 9935 문자열 폭팔 : https://www.acmicpc.net/problem/9935 가장 쉽게 생각하는 방법 : 배열에 문자를 저장해서 폭발이 없을 때까지 포문 돌리기 O(N*N), N = 백만이므로 불가능 stack 사용 -> 문자열이 폭파하였을 때, 폭파 가능한 이전 문자열을 O(1)만에 찾을 수 있다. (서로 다른 문자 이므로 가능, 중복이 될 경우 첫 번째 문자인지 마지막 문자인지 구별이 안됨에 따라서 스택 알고리즘 적용이 어렵다.) 폭파 대상을 저장하는 stack 1.. 브루트 포스[4]:두포인터, 중간에서 만나기 (Brute Force[4]:Two Pointers, Meet in the Middle(MITM)) 브루트 포스(brute force) 이러한 브루트 포스방법 중에서 투포인터, 중간에서 만나기에 관해서 소개를 하려고 한다. 두 포인터(Two Pointers) 배열에서 전체의 경우의 수를 반복문을 통해서 찾는 것이 아니라 두개의 포인터를 조작하여 원하는 결과를 얻는 방법이다. 여기서 두개의 포인터를 이용하여 기존보다 시간복잡도가 줄어드는 구조를 만들 수 있다. 두 포인터 예제 2003 - 수들의 합2 https://www.acmicpc.net/problem/2003 A[i]+...+A[j] = M이 되는 i,j 쌍의 개수를 찾는 문제와 같다. 가장 기본적으로 생각 할 수 있는 방법은 반복문을 만드는 것이다. 반복문으로 i와 j를 선택하고 i부터 j까지의 합을 구한다. (i선택 x j선택 x 합더하기 = .. 이분탐색 문제 풀이[Binary Seach PS] 1. 이분탐색 문제 푸는 방법 2. 이분탐색 문제 풀이 1. 이분탐색 문제 푸는 방법 이분탐색을 이용하여 풀 수 있는 문제는 어떤 유형이고 문제를 해결하기 위해서는 어떻게 이분탐색을 이용할까? -> 정답을 구할 수 없지만, X가 가능한지 아닌지 알아내는 것은 가능한 문제들이 있다. 1. 정답을 구하는 문제(최적해 문제) A에서 B까지 가는 가장 빠른 시간을 구하는 것 2. 가능한지 살펴보는 문제(Yes/No 문제) A에서 B까지 X라는 시간으로 이동할 수 있나? 1.를 풀 수 있으면 2 또한 풀 수 있다. 2를 풀 수 있을때, 1을 풀 수 있을까? 풀 수 있다. X라는 시간에 작은 것부터 순서대로 대입하면 No가 계속 나오다. Yes가 나오는 시점이 해가 된다. =어느 한 기점을 기준으로 yes와 no가.. 분할 정복법(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.. 이전 1 2 3 다음
