Daily Log

1. 먼저 간선을 가중치 값으로 오름차순으로 정렬한다. 2. 간선을 선택해가면서 싸이클이 되어버리면 선택하면 안된다! 아무리 간선 가중치 값이 적다고 해도! 3. 2번 정점과 9번 정점은 최소비용신장트리의 원소로 들어옴 => 이때 Union & Find로 집합을 만들어서 연결시켜버린다. 4. 2와 3을 연결하는 가중치값 10 인 간선 => 이 간선을 선택하느냐 마느냐에서 2번 정점을 find로 하고, find 3을 하여 둘이 서로 다른 집합이면 연결한다. 2와 3도 Union 한다. 5. 이런식으로 계속 간선값을 누적한다. 6. 이미 2번과 8번 정점은 연결되어 있는 상태이기 때문에 선택하지 않는다. => 회로가 되면 안된다! 싸이클을 피해라! 7. find 8 find 9는 이미 트리의 집합의 원소로 ..

우선순위큐 - 맥스힙 구조 STL 사용 최대힙/최소힙 관련 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html [자료구조] 힙(heap)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 최대힙 최대힙을 사용한 우선순위큐 STL 을 통해 문제를 풀어보자 // 73번 - 최대힙(priority_queue : 우선순위 큐) #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main() { freopen("input.txt", "rt", ..

입력 - 왕자의 수 n - 특정숫자 k 출력 - 최후의 남은 왕자 풀이 - - 원탁을 Q로 생각한다. // 72번 - 공주구하기 : 큐 자료구조로 해결 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main() { int n, k; queue Q; scanf("%d %d", &n, &k); for (int i = 1; i

- 자동추천검색어가 가능한 이유? ajax를 통해서 웹서버와 통신을해서 추천검색어를 받아옴 - 페이지 리로드 할 필요 X - gmail도 페이지의 리로드 없이 새로운 메일이 보여짐 - 필요한 정보만을 부분적으로 정교하게 낚아채는 낚시꾼 => Ajax - 웹페이지 일부 정보가 달라졌음에도 전체 페이지를 리로드 하는 것은 비효율적. => Ajax는 리로드 없이 웹서버에 정보를 요청해서 부분적으로 정보를 갱신해주는 기술 - 페이지 리로드를 줄여서 사용자 경험을 향상시킬 수 있음 - 리로드 할 때마다 모든 정보를 다운로드 하는 비효율이 불만인 경우 해결 가능 - 단 하나의 index.html 이라는 페이지를 재사용하고 바뀔 수 있는 부분과 고정될 수 있는 부분을 구분해서, 바뀔 수 있는 부분만 Ajax로 동적으..

UI : User Interface API : Application Programming Interface ex. 버튼을 누르면 경고창이 뜨는 웹 - 경고창은 어떻게 만들어 진걸까? : 웹 브라우저를 만드는 사람들이 우리 대신에 경고창을 미리 만들어 놓았다가 우리가 alert이라는 함수를 실행하면, 자바스크립트에 사용 설명서를 통해서 약속한 것 우리는 그 약속을 믿고 alert을 통해 경고창을 실행시킴 - alert => API 이다.

* 문제 최소 몇번의 점프로 현재 위치 S에서 송아지 위치 E까지 갈 수 있는지 - 직선의 좌표점은 1부터 10000까지 - 한번의 점프로 앞으로 1 뒤로 1 앞으로 5까지 갈 수 있다. ex. 현재 위치 5에서 송아지 위치 14까지는 3번만에 갈 수 있다. 10 15 14 +5 +5 -1 어떤 정점에서 어떤 정점까지 최단거리!를 구하여라 이런 것은 BFS 사용 * 상태트리 만들기 1. 5를 만들고 5에서 한번만에 갈 수 있는 것 다 트리로 만들기 2. 각 트리에서 또 2번만에 갈 수 있는 지점 만들기 이미 큐에 들어간 자료 ex.5는 체크를 걸어서 다시는 큐에 들어가지 않게 체크를 해버린다. 큐에 넣어가며, 상태트리를 만들며 1번 만에 가는 것 보기 2번 만에 가는 것 보기 3번 만에 가는 것 보기 ...

* 문제 : 1번에서 각 정점으로 가는 최소 간선 수를 2번 정점부터 차례때로 출력하시오 - 여기서 dis 배열은 각 정점까지 가는 최소 간선의 수가 저장됨. 3번만에 2번으로 가면, 이미 체크가 되어있어서 4번만에 안감 - 1번을 큐에 넣고, 1번만에 갈 수 있는 정점을 찾음 => 3을 체크함 => 3을 큐에 넣고 => dis 배열의 3번 정점의 값을 기록한다 1번정점의 길이와 3번까지 가는 간선수 합해서 입력함 - 1번만에 갈 수 있는건 또 4번 정점 => 4번을 큐에 넣고 4번 dis배열 1 기록 // 69번 - 넓이우선탐색 BFS (큐 자료구조 구현) // 무방향 그래프리스트 #include #include #include using namespace std; int Q[100], front = ..

이진트리 넓이 우선 탐색 * 넓이우선 탐색이란? BFS = level 탐색 1번 노드를 탐색한다 - 1 level 1번 노드에서 1번만에 갈 수 있는 모두를 방문한다. - 2 level 1번 노드에서 2번만에 갈 수 있는 모두를 방문한다. - 3 level 1 2 3 4 5 6 7 * 레벨 탐색 할때 QUEUE 큐라는 자료구조를 사용한다. https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html [자료구조] 큐(Queue)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io -큐는 먼저 들어간 것이 먼저 나오는 것 FIFO - First In First Ou..

* 문제 가중치 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성하세요. (!)목적지까지 가는 최소 비용은 보통 "다익스트라 알고리즘" 사용함 인접행렬 활용 // 67번 - 최소비용 DFS 인접행렬 (가중치 방향그래프) #define _CRT_SECURE_NO_WARNINGS #include int n, a, b, c, map[30][30], ch[30], cost = 999999999; //cost는 minimum value void DFS(int v, int sum) { if (v == n) { if (sum < cost) cost = sum; } else { for (int i = 1; i 0 && ch[i] == 0) { ch[i] = 1; DFS(i, s..

64번은 인접행렬로 풀었지만 66번에서는 인접 리스트로 경로를 찾아보자. 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. ▣ 입력설명 첫째 줄에는 정점의 수 N(1