전체 글45 [26.03.12(목)] 수업 복습, 자소서 작성 1. 수업 복습- prim, kruskal, dijkstra 알고리즘 공부, swea 문제 2sol 2. 자소서 작성 3. 전공 공부- 데이터베이스 파트 정독 소감화욜은 면접 집중수욜은 면접 복기이제 다시 공부하쟈 2026. 3. 13. [그래프] 최소 비용 문제 - 프림, 크루스칼, 다익스트라 그래프에서 최소 비용 문제란1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 (MST 문제)2) 두 정점 사이의 최소 비용의 경로 찾기 (최단 거리 비용 문제) 신장 트리n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree)무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 최소 신장 트리 알고리즘 - 1. Prim 알고리즘하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식이다.1. 임의 정점을 하나 선택해서 시작2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택3. 모든 정점이 선택될 때까지 1,.. 2026. 3. 10. [그래프] 서로소 집합 Disjoint-sets 서로소 집합이란?서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호배타 집합을 표현하는 방법연결리스트:같은 집합의 원소들은 하나의 연결리스트로 관리한다.연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.트리:하나의 집합을 하나의 트리로 표현한다.자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 상호배타 집합 연산Make-Set(x): 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산Find-Set(x): x를 포함하는 집합을 찾는 연산Union(x, y): x와 y를 포함하는 두 집합을 통합하는 .. 2026. 3. 10. [그래프] 위상 정렬 Topological Sort 위상 정렬이란?사이클이 없는 방향 그래프에서 정점들의 순서에 따라 선형적으로 정렬하는 알고리즘.위상 정렬의 특징위상 정렬의 결과는 여러 가지가 나올 수 있다.그래프에 사이클이 존재하면 위상 정렬을 수행할 수 없다. 위상 정렬의 활용작업 스케줄링: 작업 간의 선후 관계를 고려해 순서를 정할 때 사용된다.컴파일러: 코드 파일 간의 의존성을 분석하여 컴파일 순서를 결정한다.과목 또는 학습 계획 설계: 선수 과목, 후수 과목 간의 관계를 고려하여 결정한다.의존성 그래프 기반 문제 해결: 프로젝트 또는 시스템이 여러 요소와 의존 관계로 이루어진 경우, 전체 순서를 파악하거나 최적화를 위해 사용한다. 위상 정렬 알고리즘위상 정렬 문제는 아래의 두 알고리즘을 활용하여 풀 수 있다. 1. 진입 차수 기반 (Kahn's.. 2026. 3. 10. [26.03.09(월)] 수업, 면접 준비 1. 수업 복습그래프 이론, 순회, 위상정렬 복습2. 프로그래머스 sql 2sol3. 자소서 작성 특강 시청4. 면접 대비- 인바스켓 과제, 직무, 경험소감직무 면접에서 어떤게 나올까기술 질문 대비 연습을 더 빡세게 해야겠다 2026. 3. 10. [그래프] 그래프 이론 & 탐색 그래프란?비선형 자료구조데이터 사이의 연결 관계 표현정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이트리 ⊂ 그래프 그래프 유형무방향 그래프방향 그래프가중치 그래프사이클이 없는 방향 그래프 (DAG, Directed Acyclic Graph)사이클이 없는 무방향 그래프 (tree)완전 그래프: 모든 정점들에 대해 가능한 모든 간선들을 가진 그래프간선의 수: V * (V - 1) / 2부분 그래프(Sub Graph): 원래 그래프에서 일부의 정점이나 간선을 제거한 그래프 인접이란? Adjacency두 개의 정점에 간선이 존재하면 서로 인접해 있다고 함.완전 그래프에 속한 임의의 두 정점들은 모.. 2026. 3. 9. 이전 1 2 3 4 ··· 8 다음
