CS/자료구조와 알고리즘 (10) 썸네일형 리스트형 유니온 파인드 알고리즘 Find 연산 대표노드를 찾는 연산 O(logN)의 시간복잡도를 갖는다 맨 처음에는 자기 자신으로 초기화 되어있다. 재귀적으로 구현할때 반드시 리턴값으로 업데이트 해줘서 경로 압축을 해줘야한다 Union 연산 두 집합을 합치는 연산 합칠때는 각각의 대표노드를 찾아서 한쪽의 대표노트로 값을 바꿔주면 된다(편의상 작은쪽으로) 선택된 노드끼리 연결하는게 아니라 대표노드끼리 연결해야함 활용 용도(발상법) 1. 네트워크 연결성 검사 네트워크 내의 노드들이 서로 연결되어 있는지, 또는 두 노드가 같은 네트워크 내에 있는지를 판별할 때 예를 들어, 컴퓨터 네트워크나 소셜 네트워크에서 두 사용자가 서로 연결되어 있는지 확인할때 2. 최소 신장 트리 알고리즘 최소 신장 트리(Minimum Spanning Tree, MS.. 백트래킹 백트래킹이란 무엇인가? -현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 (ex. 게임에서 현재상태에서 가능한 모든 선택지를 다 플레이 해보는 방법) 문제풀이에서 백트래킹의 활용방식은? -각 상태별로 여러가지 경우의수가 생기고 일일이 확인할 필요가 있을때 -분기점에 다시 되돌아올 마킹을 남겨야 할때 Code int n,m; int arr[10]; bool isused[10]; void func(int k){ if(k == m){ for(int i=0; i 재귀 재귀란 무엇인가? - 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 문제풀이에서 재귀의 활용방식은? - Base condition에서 가능하고 n-1에서 된다면(가정) n에서도 가능함(귀납적 사고) 즉 위 조건을 확인하였으면 내가 할일은 n번째의 동작을 명시하고 미래의 함수에게 n-1을 맡김 재귀함수의 조건? -특정 입력에 대해서는 자기자신을 호출하지 않고 종료되어야 함 -모든 입력은 Base condition으로 수렴해야 함 DFS DFS란 무엇인가? -다차원 배열에서 각 칸을 방문할때 깊이를 우선으로 방문하는 알고리즘 문제풀이에서 DFS의 활용방식은? -Flood-Fill -그래프 트리 탐색에서 활용 BFS vs DFS(방문 순서) STL #define X first #define Y second int board[512][512]; bool vis[512][512]; int n=7, m=10; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); stack s; vis[0][0] = 1; s.push({0,0}); while(!s.empty()){ pair cur = s.top(); s.pop.. BFS BFS란 무엇인가? - 다차원 배열에서 각 칸을 방문할때 너비를 우선으로 방문하는 알고리즘 - 그래프라는 자료구조에서 모든 노드를 방문하기 위한 자료구조 문제풀이에서 BFS의 활용방식은? -인접한 칸에 대해서 색칠하는 Flood-Fill, 최단거리 문제 혹은 움직임이 정해져 있는 경우 Code #define X fisrt #define Y second int board[502][502]; bool vis[502][502]; int n=7, m=10; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); queue Q; vis[0][0] = 1; Q.push({0,0}); whil.. 덱(Deque) 덱은 무엇인가? -양쪽 끝에서 삽입과 삭제가 가능한 자료구조 덱의 성질은? 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞뒤의 원소 확인이 O(1) 제일 앞뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 덱의 용도는? -배열을 써야하는데 앞/뒤가 모두 중요할때 STL deque deq; deq.push_front(1); // 1 deq.push_back(5); // 1 5 deq.push_front(2); // 2 1 5 for(auto x : deq) cout 큐(Queue) 큐는 무엇인가? -한쪽끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄수 있는 자료구조 큐의 성질은? 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞/뒤 원소 확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 큐의 용도는? - 선착순으로 해결해야 될때 쓰임 문제풀이에서 큐의 활용방식은? -BFS와 Flood Fill STL queue Q; Q.push(1); // 1 Q.push(2); // 2 Q.push(3); // 3 cout 스택(Stack) 스택은 무엇은가? -한쪽 끝에서만 원소를 넣거나 뺄수있는 자료구조 스택의 성질은? 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 상단의 원소 확인이 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택의 용도는? 직전의 값을 저장(기억) 전체 값보다는 바로 직전값만 확인할때 거꾸로 출력하고 싶을때(함수 호출) 문제풀이에서 스택의 활용방식은? DFS 수식 괄호쌍 전위/중위/후위 표기법 STL stack s; s.push(1); // 1 s.push(2); // 1 2 s.push(3); // 1 2 3 s.push(4); // 1 2 3 4 cout 이전 1 2 다음
