[알고리즘/JAVA] 그래프 - 유니온 파인드(Union-Find)

[알고리즘/JAVA] 그래프 - 유니온 파인드(Union-Find)

유니온 파인드(서로소 집합)란 ?두 노드가 같은 집합에 속하는지 확인하는 알고리즘서로소 집합이라고도 부르며 이는 서로 중복 포함된 원소가 없는 집합을 의미한다.집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자 (representative)라 한다.유니온 파인드 연산Make-Set(x) → 집합생성. x라는 원소를 대표자로 만든다.Find-Set( x ) → x의 대표자를 가져온다.Union( x , y ) → x,y를 하나의 그룹으로 만든다. 유니온 파인드 구현Make-Set(x) → 집합생성. x라는 원소를 대표자로 만든다. P = new int[N+1]; for (int i = 1; i Find-Set( x ) → x의 대표자를 가져온다. private static i..

  • format_list_bulleted 알고리즘, 자료구조/이론
  • · 2023. 4. 27.
  • textsms
[알고리즘/JAVA] 그래프

[알고리즘/JAVA] 그래프

그래프란?정점(Vertex)들의 집합과 이들을 연결하는 간선 (Edge)들의 집합으로 구성된 자료구조 그래프의 종류무향 그래프(Undirected Graph)유향 그래프(Directed Graph)순환 그래프(Cycle graph)가중치 그래프(Weighted Graph)사이클 없는 방향 그래프(DAG, Directed Acyclic Graph) 그래프 저장 방법간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정1. 인접 행렬2. 인접 리스트인접 행렬(Adjacent matrix)|V| x |V| 크기의 2차원 배열을 이용해서 간선 정보를 저장(V: 정점의 수) 배열의 배열인접 리스트(Adjacent List)각 정점마다 해당 정점으로 나가는 간선의 정보를 저장 인접 행렬인접 리스트A와 B를 잇..

  • format_list_bulleted 알고리즘, 자료구조/이론
  • · 2023. 4. 17.
  • textsms
[알고리즘/JAVA] 트리

[알고리즘/JAVA] 트리

트리란?비선형 구조 원소들 간에 1 : N 관계를 가지는 자료구조원소들 간에 계층관계를 가지는 계층형 자료구조(사이클 x)상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 트리의 조건1. 부모 : 자식 = 1 : N2. 하나의 자식은 둘 이상의 부모X3. 노드의 개수가 N개 → 간선의 개수 N-1개4. 원소가 하나이거나 비어있어도 트리 O5. 싸이클 X 트리 용어 정리노드(node) - 트리의 원소 간선(edge) - 노드를 연결하는 선 , 부모 노드와 자식 노드를 연결 루트 노드 (root node) - 트리의 시작 노드리프 노드 (leaf node) - 자식이 없는 노드경로(path) - 간선들로 연결된 노드를 순서대로 나열한 것 거리 : 간선의 수 형제 노드(sibling nod..

  • format_list_bulleted 알고리즘, 자료구조/이론
  • · 2023. 4. 12.
  • textsms
[알고리즘/JAVA] 완전탐색 - 백트래킹

[알고리즘/JAVA] 완전탐색 - 백트래킹

완전 탐색이란?모든 경우의 수를 시도해 보는 방법반드시 답을 찾을 수 있지만 전부 탐색하기에 시간 복잡도가 일반적으로 높다.완전탐색 기법 종류Brute ForceBFS/DFS백트래킹(Backtracking)비트마스크(Bitmask)  백트래킹여러 가지 선택지(옵션)들이 존재하는 상황에서 한가지를 선택한다. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다. 이런 선택을 반복하면서 최종 상태에 도달한다. - 올바른 선택을 계속하면 목표 상태(goal state)에 도달한다.백트래킹 기법 ▪ 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 감. ▪ 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 ..

  • format_list_bulleted 알고리즘, 자료구조/이론
  • · 2023. 4. 8.
  • textsms
[Python/파이썬] 백준 알고리즘 11651번 / 좌표 정렬하기 2

[Python/파이썬] 백준 알고리즘 11651번 / 좌표 정렬하기 2

[Python/파이썬] 백준 알고리즘 11651번 / 좌표 정렬하기 2 문제 링크: https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 최종 소스코드 import sys N = int(input()) arr = [] for i in range(N): a = list(map(int, sys.stdin.readline().split())) arr.append(a) arr = sorted(arr,..

  • format_list_bulleted 알고리즘, 자료구조/백준
  • · 2022. 11. 10.
  • textsms
[Python/파이썬] 백준 알고리즘 2447번 / 별 찍기-10

[Python/파이썬] 백준 알고리즘 2447번 / 별 찍기-10

[Python/파이썬] 백준 알고리즘 2447번 / 별 찍기-10 문제 링크: https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 최종 소스코드 N = int(input()) def star(N): if N // 3 == 1: return ['*'*3, '*'+' '+'*', '*'*3] arr = star(N//3) stars = [] for i in arr: stars.append(i*3) for i in arr: s..

  • format_list_bulleted 알고리즘, 자료구조/백준
  • · 2022. 11. 7.
  • textsms