본문 바로가기

Learning-log -CS/Data Structure & Algorithm25

(자료구조 & 알고리즘 정리) 서로소집합, 유니온파인드 (2023.06.24) 1. 서로소 집합 1) 개념 - 집합 A와 집합 B에 공통된 원소가 존재하지 않으면 A와 B를 서로소 집합이라고 함 2) 서로소 집합 표현 방법 - 연결리스트 - 트리 3) 연산 - Make-Set(x) : 유일한 멤버인 x를 포함하는 새로운 집합을 생성하는 연산 //슈더 //p[x] : 노드 x의 부모 저장 //rank[x] : 루트 노드가 x인 트리의 랭크 값 저장 Make-Set(x) { p[x] = x rank[x] = 0; } // for(i=1; i rank[y]: p[y] = x; else p[x] = y if(rank[x] == rank[y] : rank[y] ++; 4) Union 연산의 효율을 높이기 - 기존 코드 //슈더 Union(x,y) p[Find-Set(y)] = Find-Se.. 2023. 6. 24.
(자료구조 & 알고리즘 정리) 그래프(DFS, BFS) (2023.06.23) 1. 그래프 표현 방식 1) 인접행렬 - 노드의 개수가 N일 때, N*N 행렬(N*N의 2차원 배열)을 만들어 x행과 y행이 연결 되어 있으면 1, 되어 있지 않으면 0을 행렬 값으로 가지도록 표현 - 무방향 그래프 모든 간선이 양 방향으로 이동이 가능한 것이라 간주 x번째 노드와 y번째 노드가 연결되어 있고 그 배열을 adj라 하자 => adj[x][y] = adj[y][x] = 1 행렬은 왼쪽 대각을 기준으로 양쪽이 대칭이 됨 => 대각을 기준으로 양쪽을 모두 사용하지 않고 행 행인 경우 중 하나만 사용해도 됨 - 가중 그래프 행렬의 값을 가중치로 저장 가중치>=0 이라면 간선이 없는 곳의 값을 -1 로 하 - 특징 구현 간단 특정 두 노드가 인접한지 상수시간에 파악 가능 메모리 낭비 심함(정점에 비.. 2023. 6. 23.
(자료구조 & 알고리즘 정리) 분할정복 (2023.06.15) 1. 분할정복 1) 개념 - 분할 : 해결할 문제를 여러 개의 작은 부분으로 나누기 - 정복 : 나눈 작은 문제를 각각 해결 - 통합 : 해결된 답을 모으기 2) 코드 Recursive_Power(x,n) { if (n==1) return x; if n is even y = Recursive_Power(x, n/2); return y*y; else y = Recursive_Power(x, (n-1)/2); return y*y*x; 2. 문제 1) 2023. 6. 15.
(자료구조 & 알고리즘 정리) 완전 탐색, 백트래킹 (2023.06.14) 1. 순열 구현 1) 비트마스킹 input[] numbers[] perm(cnt, flag) { if cnt == N return; for (i from 0 to N-1){ if (flag & 1 i=2, swap(2,2) 후 perm(2) perm(1) return; //[2, 1, 3] //perm(1) swap(0,1) perm(1)-> i=1; swap(1,1) ; perm(2) -> i=2, swap(2,2) 후 perm(3) return; //[2, 3, 1] //perm(1) swap(0,1) perm(1)-> i=2; swap(1,2) ; perm(2) -> i=2, swap(2,2) 후 perm(3) return; //[3, 2, 1] //perm(2) swap(0,2) perm(1)->.. 2023. 6. 14.
(자료구조 & 알고리즘 정리) 트리(Tree) (2023.06.13) 1. 트리 개념 1) 비선형 자료구조 2) 원소들 간에 1:n관계를 가지는 자료구조 3) 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 자료구조 => 루트노드만 접근할 수 있으면 트리의 모든 노드들을 다 탐색할 수 있게 됨. 4) 용어 노드 : 트리의 원소 트리는 한 개 이상의 노드로 이루어진 유한집합이며 다음 조건을 만족 노드 중 최상위 노드를 루트라 함 나머지 노드들은 분리집합으로 분리 가능 위의 분리집합들은 다시 하나의 트리가 됨(재귀적 정의), 루트의 부트리(subtree)라고 함 간선 : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드 : 트리의 시작 노드인 최상위 노드(트리 전체 탐색 시 루트노드부터 탐색) 형제 노드 : 같은 부모 노드의 자식 노드들 조상 노.. 2023. 6. 13.
(자료구조 & 알고리즘 정리) 스택, 큐, LinkedList (2023.06.05) 1. 스택(Stack) 1) 개념 - LIFO 방식 (가장 나중에 들어온 데이터가 가장 먼저 나가는 방식) - 모든 연산은 최상단에서 2) 연산 및 시간복잡도 - push : 삽입(가장 상단에 원소 추가) // O(1) - pop : 삭제( 가장 상단에 있는 원소 삭제) // O(1) - top : 조회(가장 상단에 있는 원소 조회) // O(1) - len : stack을 구성하고 있는 원소의 개수 출력 - 탐색(검색) : O(N) - Java에서는 Stack 클래스로 구현되어 있음 3) 관련 문제 및 게시글 링크 2022.10.12 - [Learning-log/Data Structure & Algorithm] - 자료구조 - 순차적 자료구조 : 스택(Stack)(2022.09.22~10.12) 자료구.. 2023. 6. 5.

티스토리툴바