우리들의 T'SPACE

Pre Order Post Order Tree Traversal 전위 후위 순회

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

ROUGE 점수 (Recall-Oriented Understudy for Gist Evaluation)

ROUGE는 자동 생성된 텍스트의 품질을 평가하는 중요한 지표로, 특히 텍스트 요약이나 기계 번역 같은 자연어 생성 작업에서 널리 사용됩니다. ROUGE의 기본 원리는 매우 직관적입니다. 기계가 생성한 텍스트를 사람이 직접 작성한 '정답' 텍스트와 비교하여, 둘 사이의 유사도를 측정합니다. 이때 여러 가지 관점(다양한 종류의 ROGUE 점수)에서 평가를 진행하는데, 각각의 평가 방식이 서로 다른 특징을 가지고 있어 함께 사용될 때 더욱 의미 있는 평가가 가능합니다. 가장 기본이 되는 ROUGE-1(R1)부터 살펴보겠습니다. ROUGE-1 (R1) ROUGE-1(R1)은 개별 단어의 일치도를 측정합니다. 예를 들어, 생성된 요약문과 참조 요약문에서 같은 단어가 얼마나 많이 등장하는지를 확인합니다. 이는 가..

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

레저보어 샘플링이 알고리즘은 아래와 같은 문제상황에서 사용된다. Data Stream이 있는데 나에게는 한정적인 Memory 가 있고 Data Stream의 크기는 미리 알지못하지만나는 공평하게 Random Sampling을 전체 Data Stream에서 하고 싶을때 어떻게 할까? 정답 부터 말하자면스트림에서 항목을 하나씩 가져옵니다첫 번째 항목을 선택하여 저장합니다k번째 항목을 선택할 때 1/k의 확률로 선택하고 기존 선택을 대체합니다↔ 모든 데이터에 대해 일정한 확률을 사용하면 마지막 데이터가 데이터셋에 포함될 가능성이 첫 번째 데이터보다 훨씬 더 높아집니다. 첫 번째 데이터는 더 많은 선택 과정을 견뎌야 하기 때문입니다.밑에 수학적인 증명을 보여주기 전에 더 와닫게 예시를 들어보면 죄수들이 한줄로 ..

문제비어있는 공집합 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://tonnykang.tistory.com/278 ADsP 데이터 분석 준 전문가 정리 17거리 측도변수가 연속형인 경우유클리디안 거리 (Euclidean):L2 Norm, 두 점 사이의 거리를 계산할 때 가장 널리 쓰이는 계산 방법으로, 두 점 사이의 가장 짧은 거리를 계산한다맨하튼 거리 (Manhattan):tonnykang.tistory.com연관분석연관분석의 척도지지도 (Support)전체 거래 중에서 A와 B라는 두 개의 품목이 동시에 포함된 거래의 비율지지도가 높다는 것은 그 두개의 아이템이 같이 잘 팔린다는 것신뢰도어떤 하나의 품목이 구매되었을 때 다른 품목 하나가 구매될 확률항상도품목 A가 주어지지 않았을 때 품목 B가 구매될 확률 대비 품목 A가 구매될 떄 품목 B가 구매될 확..

유전 알고리즘(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 문제의 해를 구하게 된다 이렇게 시각적으로는 너무나 쉬운 내용이지많은 컴퓨터로 구현 혹은 알고리즘으로 정의 내리기가 매우 어..

문자열 처리는 컴퓨터 과학과 프로그래밍에서 매우 중요한 주제이다.특히, 특정 패턴을 텍스트 내에서 찾는 'Exact String Matching' 문제는 자주 등장하고 많은 분야에 활용된다. Exact String Matching 목표: 텍스트 문자열 T 내에서 패턴 문자열 P의 모든 출현 위치를 찾는 것.예: T = "AGCTTGAGCTTGA", P = "GCTTGA"라면, P는 T에서 두 번 index 1, 7에서 나타난다부분 문자열 (Substring)  vs Subsequence 부분 문자열(Substring): 원 문자열의 연속된 부분.S{i,j}=Si,S{i+1}...Sj예: S = "AGCTTGA"일 때, "GCT"는 부분 문자열.부분 수열(Subsequence):원 문자열에서 몇 개의 문자..