전체 글

[2023 Google Solution Challenge] Global Top 10 진출

들어가며올해 1월 달, 고려대학교 GDSC (Google Developer Student Club)에 들어가게 되었다. 당시 진행했던 큰 프로젝트가 끝나갔고, 종강도 했던 터라 시간적인 여유가 많았었다. 그래서 작년에 활동했던 CMC 처럼 IT 개발 동아리에 들어가 또 다른 프로젝트를 진행하고자 했다. 그러던 중 전세계 대학교에서 구글이 지원하는 학생 개발 동아리인 GDSC에 대해 알게 되었다. 마침 우리 학교에도 막 1기가 생겨서 바로 서류를 넣고, 최종 면접 후 합격하였다. Google Solution ChallengeGDSC 활동 중에서 가장 메인 이벤트라고 할 수 있는 2023 Google Solution Challenge에 참가하였다. https://developers.google.com/com..

[Algorithm] 크루스칼 (Kruskal) 알고리즘

Idea Kruskal Algorithm 크루스칼 알고리즘은 최소 신장 트리, MST 를 찾는 알고리즘입니다. 그래프의 간선을 하나씩 늘리면서 가중치가 최소인 간선부터 추가하는 Greedy 방식을 사용합니다. 즉, 간선을 추가하는 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택하며 MST를 만들어가는 알고리즘입니다. 동작 과정 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. - 즉, 가장 낮은 가중치를 먼저 선택한다. - 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다. 각 단계에서 간선 선택을 Greedy하게 실시 하고, 이전 단계에서 만들어진 신장 트리와는 상관없..

[Algorithm] Spanning Tree와 MST (Minimum Spanning Tree)

Idea Spanning Tree Spanning tree는 그래프 내의 모든 정점을 포함하는 트리를 의미합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. 이때 간선의 개수가 최소이어야 하며, 따라서 최소 연결 부분 그래프라고도 합니다. N개의 정점에 대해서 모든 정점을 포함하는 트리를 만들기위해서는 최소 N-1개의 간선이 필요합니다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다. 이때 사이클을 포함해서는 안됩니다. MST (Minimum Spanning Tree) MST는 한 그래프에 대한 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미합니다. 그림에서 아래 3개의 신장 트리 중에서 ..

[Algorithm] 유니온 파인드 (Union-Find) 알고리즘

Union-Find Idea 유니온 파인드 알고리즘은 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다. 노드를 합치는 Union 연산과 root 노드를 찾는 Find 연산으로 이루어집니다. 이러한 연산을 토대로 서로소 집합(공통 원소가 없는 두 집합) 자료 구조라 불리기도 합니다. 기차를 통해 출발지와 도착지를 정해서 이동이 가능한 지 판별하려고 합니다. 그래프를 통해 기차를 타고 서울에서 강릉으로 가는건 가능하지만 서울에서 부산으로 가는건 불가능하다는 것을 알 수 있습니다. 문제는 그래프가 복잡해지면 이러한 판단이 어려워 집니다. Union-Find 알고리즘을 이용하여 복잡한 그래프에서 두 노드가 연결되어 있는지 판별할 수 있습니다. 동작 과정 8개의 단절된 노드들이 있고, 이 노드들은 배열에..

[Algorithm] 플로이드 워셜 (Floyd-Warshall) 알고리즘

Floyd-Warshall Idea 플로이드-워셜 알고리즘은 모든 정점에서 다른 모던 정점까지의 최단 경로를 모두 구하는 알고리즘입니다. 모든 정점에서 다른 모든 정점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장합니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 플로이드 워셜 알고리즘은 이 중 3번째 유형(All-To-All) 입니다. 플로이드 워셜 알고리즘의 점화식은 아래와 같습니다. 3중 반복문을 이용하여 위 점화식을 기준으로 테이..

[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘

Bellman-Ford Idea 벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있습니다. 단, 음의 사이클이 없는 그래프에서만 벨만-포드 알고리즘을 적용할 수 있습니다. 이를 위해 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세웁니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 벨만-포드 알고리즘은 이 중 2..

[Algorithm] 다익스트라(Dijkstra) 알고리즘

Dijkstra Algorithm Idea 다익스트라 알고리즘은 그래프에서 한 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 매번 최단 경로의 정점을 선택하며 탐색을 반복함으로써 출발 정점에서 나머지 각 정점까지의 최단 경로를 모두 찾게 됩니다. 단, 모든 링크의 가중치(길이)는 양의 정수 값이어야 합니다! 이러한 최단 경로(최소 비용)을 구하는 알고리즘은 다익스트라 알고리즘 외에도 벨만-포드, 플로이드-워샬 알고리즘 등이 있습니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든..

[BOJ/백준] 17291번 새끼치기 (Python 파이썬)

https://www.acmicpc.net/problem/17291 17291번: 새끼치기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준 www.acmicpc.net 문제 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준년도 1년 2월에 1마리가 탄생한다. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는..