개구리 뛰기 - BFS
SCPC 2015 1차 예선 문제 더보기 일직선 상에 돌들이 놓여있고, 개구리가 처음에는 '좌표 0'에 위치한 돌 위에 앉아 있다. '좌표 0'에는 돌이 항상 놓여 있고, 모든 돌들은 정수 좌표에 놓여 있다. (그림 1) 개구리는…
2024-06-205분
최근 글
Github - 계정이 플래그 지정되었습니다.
새로운 프로젝트에 참여하려고 보니 깃허브에서 다음과 같은 메세지를 띄워준다... 찾아보니 이메일로 사유를 보내준다는데 아무런 이메일도 와있지 않고 인텔리제이에서 연동하려고 하니 "You are marked as spam, and…
2024-06-191분
Print Prime Numbers (소수 구하기) feat. 재귀함수
Q : Write a query to print all prime numbers less than or equal to 1000 . Print your result on a single line, and use the…
2024-06-132분
Convex Hull
Convex Hull 알고리즘은 2차원 평면에 여러 개의 점이 주어졌을 때 모든 점을 포함하는 볼록 껍질을 이루는 점들을 구하는 알고리즘입니다. 이 알고리즘의 구현에는 CCW 알고리즘이 사용됩니다. 이 알고리즘의 구현 방법은…
2024-06-122분
프로젝트 회고 - News Feed
KPT Keep 초반 회의 때 원활한 소통과 적극적인 자세로 다른 팀들보다 빠른 역할 분담, 와이어프레임이나 erd 작성이 순조로웠던 점이 좋았습니다. Github를 통한 협업 및 버전관리를 수행했다는 점이 만족스러웠습니다. 보안에…
2024-06-112분
Network Flow
Network Flow란 유량 그래프란 간선의 가중치가 정점에서 정점으로 보낼 수 있는 최대 유량을 의미하는 그래프입니다. 최대 유량이란 해당 간선을 통해 동시에 흘려보낼 수 있는 물의 최대치입니다. 이러한 유량 그래프에서…
2024-06-117분
슬라이딩 윈도우(Sliding Window)
슬라이딩 윈도우(Sliding Window) 알고리즘은 투 포인터(Two Pointers) 알고리즘과 유사하게 동작하지만, 두 개의 포인터 사이의 길이가 고정되어 있다는 차이점이 존재합니다. 위의 그림과 같이 모든 영역을 고정된…
2024-06-112분
투 포인터(Two Pointers)
투 포인터(Two Pointers) 알고리즘은 주로 순차적 접근이 요구되는 조건 등의 특수한 경우에 사용되는 알고리즘입니다. 예를 들면, 정렬된 두 배열이 주어질 때 두 배열을 하나의 정렬된 배열로 합치는 경우, 어떤 배열의 연속…
2024-06-102분
순열 & 조합 (Permutations and Combinations)
경우의수 경우의 수란 '일어날 수 있는 사건의 가짓수'입니다. 예를 들어 정육면체 주사위를 던져서 나올 수 있는 경우의 수는 {1, 2, 3, 4, 5, 6}의 6가지가 있습니다. 이때 '정육면체 주사위를 던지는 사건'은 6개의…
2024-06-064분
플레인 스위핑(Plane sweeping)
플레인 스위핑(Plane sweeping)은 직각 도형의 넓이를 구할 때 주로 쓰이는 알고리즘입니다. 작은 범위는 flood-fill 을 사용하여 배열을 원하는 격자만큼 그린 후, 도형의 넓이를 직접 배열에 칠해가며 해결할 수…
2024-06-052분
CCW(Counter Clock-Wise)
CCW 알고리즘은 한 선과 한 점의 위치 관계를 구할 때 사용하는 알고리즘입니다. 한 선분 AB와 점 C가 일직선 상에 있는지, 반시계 방향에 있는지, 시계방향에 있는지를 알려줍니다. 이 알고리즘은 기하 문제를 푸는데 사용이 되며…
2024-06-042분
이분 매칭 (Bipartite Matching)
두 그룹으로 구분된 정점과, 서로 다른 그룹의 정점을 연결하는 간선들로 이루어진 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 그룹 A에 속하는 정점 Ai와 그룹 B에 속하는 정점 Bj를 연결하는 간선 (Ai,…
2024-06-033분
KMP (Knuth–Morris–Pratt)
KMP 알고리즘은 문자열 탐색 알고리즘입니다. KMP는 Knuth–Morris–Pratt의 줄임말로 KMP 알고리즘을 제안한 Donald Knuth, Vaughan Pratt 그리고 James H. Morris의 이름을 따서 이름…
2024-05-314분
Floyd-Warshall (플로이드-워샬 알고리즘)
플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다. 하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는…
2024-05-302분
벨만-포드 알고리즘
벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고…
2024-05-293분
다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다. 만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을…
2024-05-284분
서로소 집합(Disjoint-Set)
서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다. 각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는…
2024-05-254분
Binary Indexed Tree
Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며,…
2024-05-242분
세그먼트 트리(Segment Tree)
세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다. 구간 최소값을 구하는 세그먼트 트리 예시 구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자…
2024-05-234분
최소 신장 트리(Minimum Spanning Tree)
최소 신장트리란 최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다. 연결그래프가 주어질 때, MST를 구하는…
2024-05-214분