카테고리: 알고리즘

페이지당5 10 20

투 포인터(Two Pointers)

투 포인터(Two Pointers) 알고리즘은 주로 순차적 접근이 요구되는 조건 등의 특수한 경우에 사용되는 알고리즘입니다. 예를 들면, 정렬된 두 배열이 주어질 때 두 배열을 하나의 정렬된 배열로 합치는 경우, 어떤 배열의 연속…

경우의수 경우의 수란 '일어날 수 있는 사건의 가짓수'입니다. 예를 들어 정육면체 주사위를 던져서 나올 수 있는 경우의 수는 {1, 2, 3, 4, 5, 6}의 6가지가 있습니다. 이때 '정육면체 주사위를 던지는 사건'은 6개의…

플레인 스위핑(Plane sweeping)은 직각 도형의 넓이를 구할 때 주로 쓰이는 알고리즘입니다. 작은 범위는 flood-fill 을 사용하여 배열을 원하는 격자만큼 그린 후, 도형의 넓이를 직접 배열에 칠해가며 해결할 수…

CCW 알고리즘은 한 선과 한 점의 위치 관계를 구할 때 사용하는 알고리즘입니다. 한 선분 AB와 점 C가 일직선 상에 있는지, 반시계 방향에 있는지, 시계방향에 있는지를 알려줍니다. 이 알고리즘은 기하 문제를 푸는데 사용이 되며…

두 그룹으로 구분된 정점과, 서로 다른 그룹의 정점을 연결하는 간선들로 이루어진 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 그룹 A에 속하는 정점 Ai와 그룹 B에 속하는 정점 Bj를 연결하는 간선 (Ai,…