david의 CS Blog

회귀와 분류   머신러닝의 분류 체계는 지도학습(supervised learning), 비지도학습(unsupervised learning), 강화학습(reinforcement learning)으로 구분된다. 특히 지도학습은 정답(레이블, target variable)이 존재하는 데이터에서의 머신러닝이다.지도학습은 회귀(regression)와 분류(classification)으로 구분되는데, 회귀는 label이 numerical value(정량적인 숫자)이고 분류는 label이 categorical value(비정형적인 클래스)이다.   지도학습설명예시회귀(Regression)예측하고자 하는 값이 실수인 경우공부 시간에 따른 수학 시험 성적(실수) 예측분류(Classification)예측하고자 하는 값이 ..

데이터(Data)  데이터는 현대 사회에서 가장 중요한 자원 중 하나로 자리잡고 있다. 예를 들어 기업은 데이터에 기반한 의사결정을 통해 회사 고유의 경쟁력을 강화하고, 연구자들은 데이터 분석을 통해 새로운 인사이트를 얻으며, 데이터 분석의 보편화로 개인들도 데이터 기반 도구를 활용해 일상생활 속 여러 문제를 개선하고 있다. 하지만 데이터는 그 자체로서의 가치를 가지기 보다, 올바르게 가공되거나 정제될 때 그 가치가 드러난다.   데이터는 일상 혹은 연구 상황 등에서 마주할 수 있는 관찰 가능한 모든 정량적, 비정량적 수치를 포함한다. 좁은 의미로는 병원에서의 환자 건강 수치나 CT 이미지 데이터 등이 데이터가 될 수 있으며, 광범위하게는 여러 통계 자료를 포함하기도 한다. 본 글에서 초점을 맞추는 부분..

Machine Learning 기계와 공학의 발전은 다양한 산업 분야에서 혁신적인 변화를 가져왔으며, 특히 자동화의 도입은 생산성과 효율성을 크게 향상시켰다. 과거에는 주로 물리적인 작업의 기계화가 중심이었지만, 오늘날 인간의 의사결정과 문제 해결 능력을 보조하거나 대체할 기술이 중요해지고 있다. 이와 같은 요구에 부응하여 등장한 것이 바로 머신러닝(Machine Learning)이다. 머신러닝은 데이터를 활용하여 패턴을 학습하고, 이를 바탕으로 미래를 예측하거나 복잡한 문제를 해결할 수 있는 기술이다. 이는 단순한 자동화를 넘어, 스스로 학습하고 진화할 수 있는 시스템을 가능하게 하며, 현대 사회의 다양한 문제를 해결하는 데 핵심적인 역할을 하고 있다.   머신러닝(Machine Learning)은 기..

굉장히 오랜만에 블로그 글을 쓰는 것 같습니다. 지금까지 항상 알고리즘 문제 풀이 관련 글만 올리다가 처음으로 일상과관련된 글을 써보는데, 어색하지만 제 생각을 정리하고 싶어 쓰게 되었습니다. 또한 제가 올해 가졌던 고민들과 그에 대한 제 생각을 통해 누군가(어쩌면 수험생들...?)가 도움을 얻을지도 몰라, 그들에게 해주고 싶은 말들을 전하고자 합니다.     제게 2024년 한 해는 뭐라고 정의하기 굉장히 어려운 한 해인 것 같습니다. "후회없이 잘 살았는가?"라는 질문에 답하라고 한다면 망설여지기도 할 것이며 개인적으로 만족한 것도, 아쉬운 것도 많이 남는 한 해인 것 같습니다.  우선 제 소개를 해보자면 저는 과학고를 조기졸업하고 2024년 KAIST에 진학하여 새내기과정학부를 마친 학생입니다.작년..

트리의 지름  문제를 풀기 전에 다음 properties를 알면 좋다. '트리의 지름'은 트리에서 찾을 수 있는 가장 긴 경로이다.트리의 지름은 항상 루트 노드를 지나는 것은 아니다.트리의 지름은 최소 2개의 정점을 포함한다.트리의 지름은 유일하지 않을 수 있지만, 임의의 두 정점을 잇는 경로는 유일하다.  또한 다음 방법을 통해 경로를 구할 수 있다. 1. 임의로 한 정점(풀이에선 1번 노드)을 잡고, 그 정점과 가장 멀리 있는 정점(n1)을 찾는다.2. n1에서 가장 멀리 있는 정점(n2)을 찾으면, n1과 n2가 트리의 지름의 양 끝 점이 된다. (proof) 유일한 경로 ($n_{1}$, $n_{2}$)가 트리의 지름이 아니라고 가정하자(귀류법)그렇다면 ∃$n_{3}$, s.t. ($n_{1}$,..

Spanning Tree  Spanning Tree는 그래프의 모든 정점이 연결되어 있는 트리로, $V$개의 정점이 $V-1$개의 간선으로 연결되어 있다. 트리의 성질에 의해 모든 정점이 연결되어 있으므로 사이클이 존재하지 않는다. 스패닝 트리를 활용한 개념으로 최소 스패닝 트리(Minimum Spanning Tree)가 존재한다. 이는 간선에 가중치가 존재하는 그래프에서 가중치의 합을 최소로 하면서 스패닝 트리를 구성하기 위해 선택해야 하는 간선들을 정하는 것으로, 간선들의 가중치를 정렬하여 가중치가 작은 간선부터 우선적으로 선택하는 Greedy한 알고리즘을 채택할 수 있다.  DFS를 이용해 일반적인 그래프를 트리의 형태로 표현하는 경우가 존재한다. 특정 시작 정점에서 시작하여 중복 방문을 허용하지 ..

트리란? 노드로 이루어진 계층적인 자료구조로 사이클이 없는 그래프의 일종 트리에는 하나의 루트 노드가 있으며, 루트 노드는 자식 노드를 가지게 되고 그 자식 노드들은 그들의 자식 노드를 가지는 구조의 자료구조이다. 트리에 관한 용어들 루트 노드(root node): 부모 노드가 없는 중심이 되는 노드로 트리에 단 한 개만 존재한다. ex) 위 트리에서 루트 노드는 1번 노드이다. 서브 트리(subtree): 루트 노드를 제외한 나머지 노드 ex) 2, 3, ..., 9, 10번 노드들이 서브 트리이다. 리프 노드(leaf node): 자식 노드를 가지고 있지 않은 트리의 말단에 있는 노드 ex) 위 트리에서 리프 노드는 7, 8, 9, 10번 노드이다. 부모 노드(parent node): 어떤 노드와 간..

1. 계산 로봇 https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 각 칸에 있는 로봇이 입력값, 저장값, 출력값을 가지므로 이해를 위해 입력값, 저장값, 출력값을 저장하는 2차원 배열 3개를 만들어보자. 각 로봇들의 입력값은 로봇의 위치(x, y)를 기준으로 왼쪽에 있고, |i-a|≤j-b를 만족하는 (a, b)에 있는 로봇들의 출력값이다. 로봇의 저장값은 입력값들의 최댓값이고, 저장값에 자신들의 가중치를 더한 값이 출력값이다. 이제 배열들..

BitMasking 수학에서의 집합은 원소들의 포함 여부를 가진다. 이를 프로그래밍을 통해 표현하기 위해서는 Array 등의 메모리 공간을 이용해서 표현할 수 있다. 이 때, 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법이나, 원소들을 일일이 Array, Vector에 저장하는 방법으로 집합을 포현할 수 있다. 하지만 Array, Vector 등의 여러 원소를 포함하는 Container 뿐만 아니라 다른 방법으로도 집합을 표현할 수 있는데, BitMasking이 그 방법이다.BitMasking은 정수의 이진수 표현을 이용하여 집합을 나타내는 방법으로, 위에서 설명한 Array로 집합을 표현하는 방식에서 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법을 채택한다. 4 Byte의 Integer를 구..

https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 노드의 개수와 각각의 노드의 가중치를 입력받고 포화이진트리 모양을 만들었을 때 직사각형 영역을 그려서 영역 내에 있는 가중치들의 합을 최대로 만드는 문제이다. 만약 노드들의 좌표가 주어져 있다면 문제처럼 해결할 수 있을 것이다. 따라서 우리는 노드들의 좌표를 정해줄 것이다. 노드들의 $x$좌표는 트리를 전위 순회하는 순서로 ..