Jiny Devlog

백트래킹백트래킹 개념가장 최근에 방문했던 노드로 다시 돌아감(DFS)완전 탐색하지 말고, 내가 찾는 답일 가능성이 있는 경우에만 탐색한다.왜 백트래킹인가?어느 날 집을 떠나 외출한 후, 중요한 물건을 집에 놓고 왔다는 생각이 들었다. 이 상황에서 물건을 찾기 위해 모든 아파트를 탐색해야 할까? 아니면 먼저 우리 집만 탐색하는 것이 합리적일까?물건을 우리 집에 놓고 왔다고 판단하는 순간, 다른 아파트를 모두 탐색할 필요가 없다는 결론에 도달한다. 이처럼 문제 해결 과정에서 가능성이 없거나 불필요한 경로를 일찍 차단하고, 유망한 경로만 탐색하는 것이 바로 백트래킹이다.유망함수란?백트래킹에서 중요한 개념 중 하나는 유망함수이다. 유망함수는 특정 경로가 문제의 해답이 될 가능성이 있는지를 평가하는 기준을 제공하..

그래프노드와 간선을 이용한 비선형 데이터 구조그래프 용어- 노드, 간선, 가중치그래프 특징과 종류- 방향 그래프, 무방향 그래프 그래프의 구현(인접행렬)- 행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 됨- 노드 대비 간선이 적을 경우 메모리 공간효율이 좋지 않음인접행렬 표현방식- 가중치가 없는 간선을 나타내는 경우 간선이 있으면 1, 없으면 0으로 표기- 노드가 100개이고 간선이 1개인 경우에도 100 * 100 행렬이 필요함(메모리 낭비)- 특정 노드 사이에 간선존재 여부를 한번에 알 수 있음그래프의 구현(인접 리스트)- 특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식- 실제 그래프의 노드 갯수만큼만 추가하므로 메모리 낭비 없음- 특정 노드에 모든 노드가 ..

집합집합의 개념순서와 중복이 없는 원소들을 갖는 자료구조상호배타적 집합교집합이 없는 집합관계(집합은 꼭 2개가 아니라 N개일수도 있음)상호배타적 집합의 특성 활용 분야이미지 분할도로 네트워크 구성최소 신장 트리 알고리즘게임 개발클러스터링 작업집합의 연산유니온-파인드 알고리즘집합 알고리즘에 쓰이는 연산합치기(유니온)탐색(파인드)파인드 연산특정 노드의 루트 노드가 무엇인지 탐색합치기 연산두 집합을 하나로 합치는 연산문제크루스칼 알고리즘import java.util.*;class Solution { private int[] parent; public int find(int a) { if(parent[a] == a) return a; else return parent[a] =..

트리트리 개념트리는 데이터를 저장하고 탐색하기에 유용한 구조트리의 특성을 활용하는 분야인공지능자동 완성 기능데이터베이스트리 구성요소노드트리를 구성하는 노드 루트 노드노드를 연결하는 에지부모-자식, 형제 관계를 가지는 노드자식이 없는 말단 노드아래로 향하는 간선의 개수, 차수이진 트리이진 트리는 배열이나 포인터로 구현할 수 있다.배열로 표현하기배열은 선형 자료구조이고 트리는 계측 자료구조이다.규칙루트 노드는 인덱스 1번에 저장한다왼쪽 자식 노드의 배열 인덱스는 부모 노드 인덱스 * 2 이다.오른쪽 자식 노드의 배열 인덱스는 부모 노드 인덱스 * 2 + 1 이다.이진 트리 순회전위 순회: 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드중위 순회: 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드..