my devlog;

스패닝 트리 (Spanning Tree) -> 연결 그래프 G의 스패닝(신장) 트리란, G의 모든 정점을 포함하는 부분 그래프로서의 트리. 모든 정점들이 연결되어 있어야 하며 사이클이 존재해서는 안 됨. n개의 정점을 갖는 스패닝 트리는 반드시 n-1개의 에지를 가짐. 최소 스패닝 트리(최소 신장 트리) -> 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치 합이 최소인 스패닝 트리. ▷ Prim의 MST 알고리즘 ○ 아이디어 : 스패닝 트리 집합의 인접 정점 중 최소 가중치로 연결된 정점을 추가하며 스패닝 트리 집합을 점진적으로 확장해 나가자! ○ 알고리즘 1. 임의의 시작 정점에서 출발. (대개 인덱스가 가장 작은 정점) 시작 정점을 스패닝 트리 집합(MST)에 추가. 2. MST에 인접한 정점 ..

중요한 점 1. result 배열을 어떻게 오름차순으로 만들 것이냐 -> numbers를 정렬한 후 더하기, result를 정렬하여 반환하기, 자동정렬이 되는 컨테이너를 사용 2. result 배열에서 어떻게 중복을 제거할 것이냐 -> 원소 입력시 이미 존재하는 값의 원소인지 구분, 중복을 허용하지 않는 컨테이너를 사용 원소 간의 중복을 허용하지 않고 자동으로 원소가 오름차순 정렬되는 set 컨테이너를 사용하여 풀면 된다는 것을 알 수 있다. #include #include #include #include using namespace std; vector solution(vector numbers) { set s; for(int i = 0; i

스택, 큐 문제지만 이번에도 스택과 큐 없이 풀었다.. 프로그래머스의 문제 분류는 보면 항상 '그 자료구조를 꼭 써야지 풀리는 문제'라기보다는 '그 자료구조를 써서 풀 수도 있기는 한 문제'인 듯하다. 주의할 점 : '질문하기'를 보면 알 수 있지만, 효율성에 연연하지 않고 정확한 답을 푸는 것에 집중하면 어떻게든 풀린다. 추가할만한 테스트 케이스는 prices가 [1,2,3,2,3,1]인 경우, return값은 [5, 4, 1, 2, 1, 0]이 나와야 한다. #include #include #include using namespace std; int find_smaller(int i, vector &prices){ int index = 0; for(int k = 1; k < (prices.size()..

▷ 개념 ○ 강한 연결 방향그래프(Strongly Connected Digraph) -> 어떤 두 정점을 잡든 간에 서로 연결이 되어 있는, 방향 경로가 존재하는 그래프. ○ 강한 연결 요소(Strongly Connected Component) -> 어떤 두 정점을 잡든 서로 도달할 수 있는 경로가 있는 부분 방향 그래프. 같은 강한 연결 요소에 속하는 정점들은 서로 이동할 수 있는 방향 경로가 반드시 존재함. 사이클이 발생한다면 무조건 SCC에 해당하며 강한 연결 방향 그래프는 강한 연결 요소가 오직 하나. SCC를 하나의 정점으로 고려하여 각 SCC를 위상 정렬할 수 있음. ▷ 알고리즘 ○ 타잔 알고리즘(Tarjan's Algorithm) · 개념 : 모든 정점에 대해 DFS를 수행하여 SCC를 찾는..

DFS 또는 BFS를 사용하여 연결 성분의 개수를 구하는 문제이다. 참고 : hyunah-home.tistory.com/entry/%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS%EC%99%80-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS-%EC%9D%91%EC%9A%A9-%EC%97%B0%EA%B2%B0-%EC%84%B1%EB%B6%84-%EC%B0%BE%EA%B8%B0 #include #include using namespace std; int visited[201]; int answer; void dfs(int v, vector computers){ visited[v] = answe..

그래프 탐색 : 그래프의 기본 연산 중 하나. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문. 특정 정점에서 특정 정점까지 갈 수 있는지 없는지를 탐색 1. 깊이우선 탐색(DFS) ○ 개념 : 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 방향으로 다시 탐색을 진행. 갈림길로 다시 돌아가는 과정에서는 스택을 사용하거나 재귀 함수 호출을 이용. ○ 알고리즘 : 정점 v를 방문한 후 해당 정점이 방문되었다고 표시하고 v의 모든 인접 정점에 대해 방문되지 않은 정점이라면 재귀 함수 호출. ○ 프로그램 int visited[8]; vector adj_list[8]; //adj_list[i]에는 i의 인접 정점들의 리스..

그래프 -> 연결되어 있는 객체 간의 관계를 표현하는 자료구조. 가장 일반적인 자료구조의 형태로 트리, 이진트리도 그래프의 특수한 경우. 선수과목 관계, 도로망, 영역간 인접 관계 등을 표현할 수 있음. ▷ 개념 · 그래프 G는 ( V,E )로 표시. 특별한 언급이 없으면 그래프는 자가 루프와 중복 에지가 없는 단순 그래프를 의미. · 정점(vertex) V(G) : 그래프 G의 정점들의 집합. 여러 가지 특성을 가질 수 있는 객체를 의미하며 노드라고도 불림. · 에지(edge) E(G) : 그래프 G의 에지들의 집합. 정점들 간의 관계를 의미하며 간선 또는 링크라고도 불림. · 인접 정점(adjacent vertex) 어떤 정점에서 에지에 의해 직접 연결된 정점 · 경로(path) 정점 s로부터 정점 ..

스택/큐 분야로 분류되었던 문제이다. 스택이랑 큐를 쓰지 않고도 풀 수 있다는 게 함정이지만! #include #include using namespace std; vector solution(vector progresses, vector speeds) { vector answer; while(true){ for(int i =0; i= 100){ int value = 1; for(int j = 1; j= 100) value++; else break; } answer.push_back(value); progresses.erase(progresses.begin(), progresses.begin()+value); speeds.erase(speeds.begin(), speeds.begin()+value); }..

우선순위 큐(priority queue) -> 우선순위를 가진 원소들을 저장하는 큐. 들어온 순서에 상관없이 가장 우선순위가 높은 항목이 삭제됨. 스택이나 FIFO 큐도 우선순위 큐의 특별한 형태라고 볼 수 있음. 최소(min) 우선순위 큐와 최대(max) 우선순위 큐 존재. ▷ ADT create() :: = 우선순위 큐를 생성 init(pq) :: = 우선순위 큐 pq를 초기화 is_empty(pq) :: = 우선순위 큐 pq가 비어있는지 검사 is_full(pq) :: = 우선순위 큐 pq가 가득 찼는지 검사 insert(pq, x) :: = 우선순위 큐 pq에 원소 x를 추가 (x값을 우선순위라고 가정) deleteMin(pq) :: = 우선순위 큐 pq로부터 가장 우선순위가 높은 원소를 삭제하고..

트리 -> 부모-자식 관계의 노드들로 이루어진, 계층적인 관계를 나타내는 특별한 자료구조(비선형 리스트). ▷ 용어 · 노드 : 데이터, 정보가 저장된 트리의 구성 원소 · 에지(간선) : 노드와 노드 사이를 나타내는 구성 원소 · 루트 : 부모가 없는 노드, 최상단 노드 · 리프 : 자식이 없는 노드, 단말 노드 · 레벨 : 트리의 각 층의 번호(루트의 레벨은 0 또는 1) · 높이(깊이) : 트리의 최대 레벨 · 차수 : 노드가 가지고 있는 자식 노드 개수 이진트리 -> 공집합이거나, 공집합이 아닌 경우 특별히 지정된 노드인 루트가 있고, 각 노드는 최대 2개의 자식 노드가 존재하며, 각 노드가 왼쪽 부분트리 및 오른쪽 부분트리를 가짐. ▷ 분류 · 포화 이진트리(full binary tree) : ..