간타타 공부장 간타타 공부장

*MST(Minimum Spanning Tree) - Spanning Tree : 그래프 내의 모든 노드를 포함하는 트리 - Minimum Spanning Tree: Spanning Tree중에서 사용된 간선들의 가중치 합이 최소인 트리 *크루스칼 알고리즘(Kruskal Algorithm) - 통신만, 도로망, 유통망의 길이, 구축비용, 전송시간 등을 최소로 구축하려는 경우 - Union Find 알고리즘이 적용됨(싸이클 판별) gilmatnote.tistory.com/39 Union Find알고리즘 - 합집합을 찾을 때 주로 사용 - 서로소 집합 알고리즘이라고도 함 - 여러 노드 중에서 그룹화를 지을 때 사용하는 알고리즘 - 크루스칼 알고리즘 구현 시 싸이클이 발생하지 않도록 판별할 때 사 gilmat..

- 합집합을 찾을 때 주로 사용 - 서로소 집합 알고리즘이라고도 함 - 여러 노드 중에서 그룹화를 지을 때 사용하는 알고리즘 - 크루스칼 알고리즘 구현 시 싸이클이 발생하지 않도록 판별할 때 사용하는 등 다양한 알고리즘 문제 적용시 사용이 됨 - 무방향 그래프에서 적용 *문제 상황 - 노드의 연결 정보는 현재 위와 같다는 문제가 주워져 있다 - (1,2,3)이 한 그룹, (4,5)이 한 그룹이다. *구현 방법 1, 일차원 배열 (parent)으로 해당 노드의 부모의 값을 적용하도록 한다. - 배열안의 있는 값은 노드의 부모의 값을 저장하도록 한다. (이때, 부모는 배열안의 수가 자기 자신인 노드를 지칭한다.) - 초기 설정은 해당 노드의 부모가 자기 자신으로 초기 설정을 해 준다. 초기 parent배열 ..

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 1, 관심이 있는 정보는 어차피 skill 문자열에 있는 문자들이기 때문에 조사하고자 하는 문자열을 순회하여 skill에 있는 문자들만 뽑아내고 skill에 있는 인덱스를 벡터로 다시 만들어서 조사를 한다. 2, 벡터를 순회하면서 인덱스 숫자가 순차적으로 늘어나는지 확인한다. #include #include using namespace std; vector renewal(string skill, string search) { vector result; int str_size = search.size(); for (int i = 0; i < str_size; ..

programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 어떠한 사람들은 4차원 배열을 통하여 해결하였으나 나는 비트마스킹을 이용하여 문제를 해결하였다. 1, 해당 위치에서 이미 지나간 길의 정보를 저장하여야 하는데 map 이차원 배열에 해당 위치에서 위로 간 경우 1, 아래로 간 경우 2, 왼쪽으로 간 경우 4, 오른쪽으로 간 경우 8 을 저장하여 주고 & 연산자를 이용하여 지금 해당 위치에서 이동하려고 하는 길이 이미 지난 길인지 판별을 해 주웠다. *주의 할 점 - 지금 위치와 다음 위치 둘 다 이미 지나간 길에 대한 정보를 갱신 - 범위를 넘어 섰는지 확인 소스코드 #include #include usin..

programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 요즘은 dfs, bfs 단독으로 문제가 나오기 보다는 그래프 탐색을 이용하혀 한번 더 알고리즘 개념을 이용한 문제들이 종종 있는것을 볼 수 있다. 이번에는 그래프 탐색과 MST(최소비용 신장 트리) 개념을 합친 문제를 풀어 보았다. 나중에 프림스 알고리즘과 크루스칼 알고리즘에 대하여도 정리를 하여 포스팅을..

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 생각보다 간단한 문제였는데 고민을 오래했다. *실패한 방법 O(n^2) 풀이법 1, 왼쪽 상단에서 오른쪽 하단으로 이어지는 대각선을 생각하였다.(어차피 대칭이므로 어느 선을 그어도 동일) 2, 정사각형의 왼쪽 하단과 오른쪽 상단의 점을 구한 후 두 점이 대각선의 아래에 있나 위에 있나 판별하여 갯수를 세어줌 => 결론은 시간초과와 약간의 실패 기록들..

본 내용은 생활코딩의 내용을 바탕으로 정리하였습니다. opentutorials.org/course/228/4894 HTTPS와 SSL 인증서 - 생활코딩 HTTPS VS HTTP HTTP는 Hypertext Transfer Protocol의 약자다. 즉 Hypertext 인 HTML을 전송하기 위한 통신규약을 의미한다. HTTPS에서 마지막의 S는 Over Secure Socket Layer의 약자로 Secure라는 말을 통해서 알 수 있듯이 opentutorials.org Http와 Https http(Hypertext Transfer Protocol) : hypertext인 html을 전송하기 위한 통신규약 https(Hypertext Transfer Protocol Over Secure Socket..

programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 1, DP로 풀었을 시 O(n^2)이기 때문에 시간초과 결과로 실패 2, 투포인터 알고리즘을 이용하여 O(N+M)으로 해결 소스코드 #include #include #include #include #include using namespace std; vector solution(vector gems) { vector answer; set jewelry; set search; pair check; map count; int v..