우리들의 T'SPACE

유니온-파인드(Union-Find, 서로소 집합 또는 분리 집합 Disjoint set이라고도 함)는 여러 개의 서로소 집합으로 나누어진 원소들을 추적하는 자료구조입니다. 주요 연산은 다음 두 가지입니다:파인드(Find): 특정 원소가 어느 집합에 속하는지 판별합니다. 두 원소가 같은 집합에 속하는지 확인하는 데 사용됩니다.유니온(Union): 두 개의 집합을 하나의 집합으로 합칩니다.유니온-파인드의 핵심 구성 요소부모 배열: parent[] 배열로, parent[i]는 원소 i의 부모를 저장합니다. 초기에는 각 원소가 자신을 부모로 가집니다(자기 자신이 루트).랭크/크기 배열: rank[] 또는 size[] 배열로, 유니온 수행 시 트리의 균형을 맞추어 성능 저하를 일으킬 수 있는 극단적인 경우를 피하..

문제문제 설명민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모..

트리 순회 (Tree Traversal)는 트리 자료구조의 모든 노드를 체계적으로 방문하는 방법입니다. 자주 사용되는 BFS와 DFS 알고리즘과 함께, 깊이 우선 순회의 두 가지 일반적인 유형은 전위(pre-order) 와 후위(post-order) 순회입니다. 각각에 대한 설명을 해드리겠습니다: 전위 순회정의:전위 순회에서는 다음 순서로 노드를 방문합니다:루트 노드 (root node)를 방문합니다.왼쪽 서브트리 (subtree)를 순회합니다 (재귀적(으로 전위 순회 사용).오른쪽 서브트리를 순회합니다 (재귀적으로 전위 순회 사용).이진 트리(Binary Tree)의 경우:현재 노드를 처리합니다 (예: 값을 출력).왼쪽 서브트리에 대해 재귀적으로 전위 순회를 수행합니다.오른쪽 서브트리에 대해 재귀적으로..

자료구조는 크게메모리 공간 기반의 연속 (contiguous)방식포인터 기반의 연결 (link)방식으로 나뉜다 배열은 이중에서 연속 방식의 가장 기본이 되는 자료형이다↔ 연결방식의 가장 기본이 되는 자료형은 ‘연결 리스트’가 있다배열을 C언어 기준으로 설명해드리자면, 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다.크기가 정해져 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능 하다int arr[5] = {4, 7, 29, 0, 1};물리 메모리, 즉 실제 메모리에는 이 배열 요소의 값들이 순서대로 배치된다과거에는 16비트 컴퓨터 시절에 int는 2바이트였지만,현대 32비트 이상의 시스템에는 int가 일반적으로 4바이트이다.무엇보다 배열은 어느 위치에서..

Delaunay Triangluation점들을 연결하는 최적의 방법 공간 데이터를 다루는 많은 분야에서 들로네 삼각분할(Delaunay Triangulation)은 핵심적인 기법으로 사용됩니다. 이 방법은 평면 위의 점들을 삼각형으로 연결하여 공간을 분할하는데, 단순히 연결하는 것이 아니라 특별한 기준을 따릅니다. 바로 삼각형들의 내각의 최소값이 최대가 되도록 하는 것입니다. 왜 이런 기준을 따르는 걸까요? 들로네 삼각분할의 핵심은 '빈 외접원 특성' Empty Circumcircle Property에 있습니다.이 특성을 충족시키기 위해 내각이 작은 삼각형 대신 내각이 큰 삼각형을 선택하게 되고, 이로 인해 "형태가 좋은" 삼각형들이 만들어집니다.예를 들어, 비 들로네 삼각분할에서 볼 수 있는 꼭짓점 V..

문제비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)all: S를 {1, 2, ..., 20} 으로 바꾼다.empty: S를 공집합으로 바꾼다.입력첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하..

https://www.acmicpc.net/problem/1697 문제Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 Walking: FJ can move from any point X to the points X-1 or X+1 in a single minuteTeleporting: FJ can move from any point X to the point 2*X in a single minute.If the cow, unaware of its pursuit, does not move at all, how long does it..

유전 알고리즘(Genetic Algorithm, GA) 자연세계의 진화과정 및 유전법칙에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법(Global Optimization Method)생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산, 세대, 인구 등의 개념을 문제 풀이 과정에서 사용문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻을 수 있음 아래는 전반적인 GA의 과정이다 Starts with a population of individuals (다수의 개별 솔루션으로 시작)  Each..

P, NP, NP-hard, NP-complete 문제의 이해컴퓨터 과학에서 가장 중요한 개념 중  하나인 P, NP, NP-hard, NP-complete 문제.이 개념들은 알고리즘의 효율성과 문제의 복잡성을 이해하는 데 핵심적이다.이 글에서는 각 개념을 자세히 살펴보겠습니다.P Problems (Polynomial)P 문제는 결정론적 튜링 기계(deterministic Turing machine)로 다항 시간(Polynomial Time) 내에 해결할 수 있는 문제이다 결정론적 알고리즘: 특정 입력이 주어지면 항상 같은 출력을 예측 가능한 단계 순서로 생성하는 알고리즘이다\즉 Heuristic한 알고리즘은 결정론적이지 않은 비결정론적 알고리즘이라고 할 수 있다 다항 시간: 알고리즘의 시간 복잡도가인 ..

Convex Hull은 점들의 집합이 있을때 이 모든 점들을 포함하는 크기가 최소인 Convex Polygon을 찾는 문제이다Convexity 쉽게 말해 위처럼 집합 내에 있는 두 점을 연결한 선분이 집합 내에 있어야Convex하다고 할 수 있다하지만 우리가 찾는 것은 Convex Polygon 다각형임으로 모든 내각이 180도 이하라는 조건이 또 붙는다(180도는 각이 아님 ㅋ) 가장간단한 풀이 방법은 뭘까?? 좀 간지나게 mechanical way 라고 말하는데 2차원 평면에 수직되게 못을 점들과 대응되게 박아넣은뒤 고무줄을 늘려 풀어주면알아서 착! 감기며 Convex Hull 문제의 해를 구하게 된다 이렇게 시각적으로는 너무나 쉬운 내용이지많은 컴퓨터로 구현 혹은 알고리즘으로 정의 내리기가 매우 어..