Mikyo CodingStory

안녕하세요. 밀쿄입니다. 오늘은 유니온 파인드라는 알고리즘에 대해서 알아보겠습니다. 유니온 파인드는 그래프 알고리즘의 일종 입니다. 그리고 합집합 찾기라는 의미를 담고 있습니다. 이렇게 말하면 감이 안오지만 쉽게 말하자면 "여러 가지 노드가 있을 때, 두 노드를 선택하여 가 같은 그래프에 속하는 지 판별하는 알고리즘" 이라고 생각하시면 편할 것 같습니다. 따라서 이 알고리즘은 두 가지 연산으로 이루어져있습니다. 이름에도 나와있듯이 유니온(Union) 연산과 찾는(Find) 연산입니다. Union은 두 노드가 속해있는 집합을 합치는 연산입니다. Find는 한 노드가 어떤 집합에 포함되어 있는 지 찾는 연산 입니다. 예시를 하나 들어보겠습니다. 처음에는 1, 2, 3이 있다고 가정해봅시다. 각각의 원소들은 ..

안녕하세요. 밀쿄입니다. 오늘도 문제하나를 같이 풀어보겠습니다. https://programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 우선순위 큐를 사용하는 문제입니다. 먼저 큐와 우선순위 큐 두 개를 만들어 줍니다. 큐는 배열의 인덱스와 함께 우선순위를 저장해줍니다, 그리고 우선순위큐는 우선순위를 정렬해서 저장해줍니다. 자 이렇게 해주고 나면 이제 당연하게 큐에서 하나 pop하고 우선순위큐에서 pop을 해서 우선순위를 비교해줍니다. 우선순위가 같다면 당연히 인쇄를 ..

안녕하세요. 밀쿄입니다. 오늘은 이진 탐색 트리에 대해서 알아보겠습니다. 이진 탐색트리는 두 자료구조를 결합한 자료 구조 입니다. 그 자료 구조 중 하나는 탐색이 빠르지만 삽입 삭제가 안되고 다른 하나는 삽입 삭제는 빠르지만 탐색에 O(n)이란 복잡성을 가지고 있습니다. 그래서 그 두개를 합쳐서 탐색이 빠르고 삽입삭제가 빠른걸 만들고자 고안이 되었습니다. 그래서 그 두 개가 무엇인지 궁금하실텐데 바로 이진 트리와 연결리스트입니다. 자 그럼 이진 탐색 트리에 대해 본격적으로 알아보겠습니다 이진 탐색트리는 다음과 같은 특징을 가지고 있습니다. 각 노드의 왼쪽 서브트리에 있는 노드의 값은 부모 노드보다 그 값이 작다. 각 노드의 오른쪽 서브트리에 있는 노드의 값은 부모 노드보다 그 값이 크다 들어가기전에 스위..