챗지회피티님의 블로그

자료 구조1. 자료 구조란? 개념: 여러 원소들이 겹치지 않는 부분집합들로 분할되어 있을 때, 이 부분집합들을 효율적으로 관리하기 위한 자료구조로 서로소 관계이며 상호 베타 집합들은 서로 중복으로 포함된 원소가 없는 집합들이다. 이는 집단에 속한 특정 멤버(대표자 root)를 통해 각 집합들을 구분한다.주요 연산:find: 주어진 원소가 속한 집합의 대표(또는 루트)를 찾습니다.union: 서로 다른 두 집합을 하나로 합칩니다.최적화 기법: 경로 압축(Path Compression)과 랭크(또는 크기)를 고려한 합병(Union by Rank)을 사용하여, 연산의 효율성을 크게 향상시킵니다.활용 예: 크루스칼 알고리즘 같은 최소 신장 트리(MST) 문제, 네트워크 연결성 확인 등에서 많이 사용됩니다.이 두..

1. 그래프(Graph)1. 그래프란?무방향 그래프: 간선에 방향이 없어 A → B나 B → A가 같은 의미.방향 그래프: 간선에 방향이 있어 A → B와 B → A가 다름.가중 그래프: 간선에 가중치(비용, 거리 등)가 있는 그래프.cycle을 도는 방식 2. 인접 행렬 그래프 가중치 X가중치 O연결: true, 1value비연결: false, 00 Node 수인접 행렬배열 크기메모리수행 횟수100100*10010,00010K, 4K10,00010001000*10001,000,0001M, 4M1,000,00010,000노드 수가 많으면 인접 행렬 불가100,000,000100M, 400M1억인접 행렬로는 메모리 초과, 시간 초과이므로 불가 → 인접 리스트로 해야 함, 인접 리스트 수행 속도(Nod..

1. Greedy (그리디) 1. 그리디란? 현재 단계에서 선택할 수 있는 것 중 가장 좋은 것을 선택하는 알고리즘으로현재 단계에서 가장 좋은 것을 선택했지만 모든 선택을 끝낸 최종의 값은 가장 좋은 선택이 아닐 수도 있으니 유의!!!2. 문제 해결 최적화 방법 2-1. 국소적 최적화최선의 선택을 위해 문제 해결을 위한 기준(가치)으로 정렬을 하여 가장 좋은 것을 선택한다. 2-2. 전역적 최적화정렬할 수 없는 경우 현재 선택할 수 있는 데이타 중 가장 좋을 것을 탐색하여 선택한다.3. 그리디 알고리즘 성립 조건 3-1. 탐욕적 속성각 단계에서의 국소적 최적 선택이 전체 해의 최적성을 해치지 않아야 한다.부분 문제에서 얻은 해 -> 전체 문제에서도 최적임을 유지 3-2. 최적 부분 구조문제의 ..