크루스칼(Kruskal) - 최소 신장 트리(MST)

개념 신장 트리(Spanning Tree) 모든 정점을 포함하면서 사이클이 없는 그래프 특징 원 그래프의 모든 정점을 포함 간선(node) 수 = 정점 수 - 1 노드 간 사이클을 형성하지 않음 한 그래프 내에서 여러 개의 신장 트리를 가질 수 있음 최소 신장 트리(Minimum Spanning Tree) 간선(node) 가중치의 합이 가장 작은 신장 트리 간선(node) 가중치가 가장 낮은 간선부터 탐색하여 신장트리를 구성하는 방식 대표 알고리즘 : Kruskal 알고리즘, Prim 알고리즘 차이점 Kruskal 알고리즘 : 간선(node)를 중심으로 하여 신장 트리를 구성 Prim 알고리즘 : 정점(spot)을 중심으로 하여 신장 트리를 구성 크루스칼(Kruskal) 알고리즘 가장 작은 가중치를 갖는..

• format_list_bulleted Algorithm/개념
• · 2024. 1. 10.
• textsms

18111. 마인크래프트

https://www.acmicpc.net/problem/18111 이해 평탄화가 가능한 높이에 대해 모든 경우의 수를 비교해가며 풀어야하는 문제이다. 문제를 읽어보면 알 수 있 듯, 높이에 대한 인덱스가 중요하지 않아 2차원 배열이 아닌 1차원 배열로 입력을 받아도 되고, Dictionary 형태로 받아도 된다. 구현 N*M 행렬을 높이에 대한 Dictionary로 정의 collections 내부 defaultdict를 활용 높이에 대해 쌓을 블럭 수와 부술 블럭 수를 따로 저장하여 계산 식으로 풀이 만들 수 있는가? 👉 (부술 블럭 수) + (최초 인벤토리 블럭 수) >= (쌓는 블럭 수) 걸리는 시간 👉 (부술 블럭 수) + 2 * (쌓는 블럭 수) 걸리는 최소 시간 저장 및 최소 시간 중복 시 최..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 1. 9.
• textsms

[알고리즘] Union-Find

개념 그래프 이론으로, 상호 배타적 집합(서로소집합:Disjoint-Set) 알고리즘이라고도 부름 주로 크루스칼(Krusckal) 알고리즘에서 사용하며, 순환하지 않는 트리 를 만들기 위해 사용 단계별로 이해하기 만약 아래 표와 같이 4개의 노드를 가진 서로소 집합이 있다면, 노드 번호 1 2 3 4 대표 번호 1 2 3 4 1번과 2번이 같은 집합이라면? 대표번호를 변경하여 같은 집합을 표현할 수 있음 Union 결과 노드 번호 1 2 3 4 대표 번호 1 1 3 4 아래 표와 같이 있을 때 2번은 어떤 집합에 있는지 알 수 없을까? 노드 번호 1 2 3 4 대표 번호 1 3 4 1 노드 번호를 따라가며 확인할 수 있음 2번 👉 3번 👉 4번 👉 1번 (모두 같은 집합) Find 다른 표현 노드 번호 ..

• format_list_bulleted Algorithm/개념
• · 2024. 1. 7.
• textsms

1717. 집합의 표현

https://www.acmicpc.net/problem/1717 문제 해석 합집합과 같은 집합인지 확인하는 문제로 분리집합(Union-Find)의 대표적인 문제이다. 구현 방법 총 3단계로 나누어 구현 Root를 저장할 배열 초기화 Find 함수 작성 같은 Root를 가지고 있는지 확인( 같은 집합인가 확인) Union 함수 작성 서로 다른 두 집합을 합집합 (Root 를 같게 함) 이미 같으면 할 필요 없음 코드 # 1717 집합의 표현 import sys input = sys.stdin.readline def find(num:int)->int: if parent[num] == num: return num parent[num] = find(parent[num]) return parent[num] de..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 1. 7.
• textsms

HTML(3) - 속성(Attribute)

2023.03.19 - [WEB/HTML] - HTML(2) - 요소(Element) HTML(2) - 요소(Element) 이전 글과 내용이 이어집니다! HTML(1) - 기본 구조 HTML의 개념을 잡았으니 자세히 알아보자! 개념이 궁금하시면 이전 글을 추천드립니다! HTML이란?(개념 이해) 개발자 농담 중엔 이런 글이 있다. A: l1m3kun.tistory.com 이전 글과 이어집니다! HTML을 이용하여 블로그나 Notion같은 프로그램을 쓰다보면, 부분부분 색을 바꾸거나 하이퍼 링크를 넣는 등 다양한 기능들이 포함되어있는 것을 볼 수 있다. 이런 기능들을 사용할 수 있는 것이 바로 속성이다! 속성 속성을 통해 태그의 부가적인 정보를 설정할 수 있음 요소는 속성을 가질 수 있으며, 경로나 크기..

• format_list_bulleted WEB/HTML
• · 2023. 3. 19.
• textsms

HTML(2) - 요소(Element)

이전 글과 내용이 이어집니다! HTML(1) - 기본 구조 HTML의 개념을 잡았으니 자세히 알아보자! 개념이 궁금하시면 이전 글을 추천드립니다! HTML이란?(개념 이해) 개발자 농담 중엔 이런 글이 있다. A: 어떤 걸로 코딩하는 걸 좋아하세요? B: 저는 HTML로 l1m3kun.tistory.com 요소(Element) 시작 태그와 종료 태그 그리고 태그 사이에 위치한 내용으로 구성 컨텐츠(내용)를 감싸는 것으로 그 정보의 성격과 의미를 정의 내용이 없는 없는 태그 닫는 태그 없이 사용 태그(요소) 용도 줄 바꿈 구분선 이미지 삽입, scr 속성을 활용하여 이미지 표현 입력창 head 태그에 나타내며 외부 리소스 연결 검색 엔진을 위한 키워드, 웹페이지 설명, 저자 정의 등 메타데이터를 정의할 때..

• format_list_bulleted WEB/HTML
• · 2023. 3. 19.
• textsms