목차 세그먼트 트리 어떤 수들의 집합이 있다. 그 집합은 원소가 마구마구 변할 수 있다고 한다. 이 때, 그 집합의 부분합을 아주 빠르게 구하기 위해서 만들어진 구조이다. 예를 들어서.. 1, 5, 6, 7, 4, 8, 2, 3 이렇게 수가 있다고 하자. 우리가 이 수들에서 특정 범위의 합을 구하려면 어떻게 해야할까? 역시 제일 간단한 방법은 다 더하는 것이다. 3~6번째 원소를 더하면. 6+7+4+8 = 25 이렇게 다 더하는 경우 시간복잡도는 O(N)으로 작은 범위 내에서 보면 나쁠 수 있다. 하지만, 이 합을 원하는 곳이 많아서 수천, 수만명이 요구를 한다면?? 또, 이 데이터에 접근 가능한 사람이 많아서 계속해서 값이 바뀐다면?? 참으로 난감할 것이다. 데이터는 바꿔줄 수 있지만. 합을 계속 해서..
목차 백준 7662번 이중 우선순위 큐. 우선순위는 큐에 들어가는 정수값 자체를 우선순위로 하는 이중 우선순위 큐이다. 최대힙과, 최소힙을 이용해서 구현을 해 보았다. 최대값을 제거할때는 최대힙에서 삭제연산을 하고, 삭제한 요소를 저장해둔다. 그리고 최소값을 제거할때 만약 제거하는 요소가 저장해둔 배열에 있다면, 한번더 삭제한다. void pop(heap *h, heap *h2, int num){ int temp; //최대값 삭제 if(num == 1){ temp = popM(h); for(int i = h->numsize-1; i > -1 ; i--){ if(temp == h->nums[i]){ temp = popM(h); h->nums[i] = h->nums[h->numsize--]; } } } //..
목차 Neural Network Basics Binary Classification -> 이진 분류 뭐가 맞다 아니다 => 1, 0으로 나타낼 수 있는것을 구별하는것 이런 이진분류를 한번 해보도록 하자. 일단 첫번째로 입력과 출력이 필요하다. 이런 하나의 입력과 출력을 training set이라 하고 $$ (x, y) \to x \in \mathbb{R}^{nx}, y \in {1, 0}$$ 라고 말할 수 있다. 이진분류를 이미지로 나타내면 training set은 어떻게 구성될까? 먼저 이미지가 어떻게 표현되는지 알아야 한다. 이미지는 $$ n \times m$$행렬로 이루어져 있고 빨강, 초록, 파란색의 3원색이 각각 어떤 값을 갖고 있는지를 저장한다. 이를 훈련예제로 옮기면 각각의 행렬을 하나의 열..
목차 Introduction Linear Regression 선형 회귀(linear Regression)는 다수의 데이터를 대표할 수 있는 직선을 만드는 것을 말한다. 예를 들어 집의 가격과 크기를 생각해보자. 아래의 그래프와 같이 보통 집의 크기가 크면, 집의 가격이 높아지는 경향이 있다 이 모두를 적당히 대표할 수 있는 직선을 하나 그을 수 있는데, 이것을 선형회귀라고 한다. 이런 직선을 그리는 함수를 집의 크기를 입력으로 받고 집의 가격을 출력으로 하는 Single Neuron이라고 한다. Supervised Learning 인공지능을 학습 시킬 때, 결과를 알려주고 학습을 시키는 지도학습이라는 기법이다. 지도학습은 Structed Data, Unstructed Data를 통해서 학습을 시키는데, ..
목차 인공지능 공부의 시작 어제 다시 학교에 왔다. 부모님의 차를 타고, 고속도로를 타서, 먼길을 달려왔다. 낮이라서, 코로나 때문에 사람들이 많이 안다닌다고 생각하지만, 오는길에 차가 막혔던 적이 한번도 없었다. 곰곰히 생각해보니 참 신기한거다. 어떻게 이많은 도로들을 연결하고, 건설했을까 어떤 기준으로? 언제 분기하는지 이런것들 말이다. 새로운 도로를 건설하는건 엄청난 비용과 시간이 들어가는 일인데, 하나하나를 신중하게 결정해야하는데, 판단 기준이 뭘까.. 라고 그래서 난 내 나름대로 Ai를 사용하면 그 판단을 내릴 수 있지 않을까 생각했다. 내가 아는 Ai는 인간이 풀기 힘들만한 여러가지 데이터들을 모아서 최상의 결과를 내어주는 그런 기술로 알고있다. 그렇다면, 지금 존재하는 모든 교통정보들을 모아..
목차 에라토스테네스의 체 소수판정의 가장 기본이 되는 에라토스테네스의 체이다. 소수는 약수가 1과 자기자신만을 가지는 수이다. 소수를 구하는 알고리즘을 찾아보자. 알기 쉽게 예를 들어보겠다. 1~50까지의 소수 1부터 50까지의 수 중 소수를 찾는 방법을 보자 먼저 숫자를 다 적어본다. 그리고, 제일 첫번째 소수인 2의 배수를 다 지워준다. 지워주는 이유를 생각을 해보면, 소수는 1과 자기자신만을 약수로 가지는 수 이다. 어떤 수의 배수는 소수가 될 수 없다. 그러므로 범위내의 소수의 배수를 다 지워주면, 소수만 남게된다. 그렇게 2의 배수를 지우고, 3의 배수 5의 배수 7의 배수 이렇게 까지만 지워주면 나머지 수 들은 전부 소수가 된다. 왜 7까지만 지워줄까? 근데 앞에서 그러므로 범위내의 소수의 배..
목차 정말 실수를 많이 유발하는 실수 실수(mistake)가 아니라 실수(real number)에 대한 글. 이 실수는 정말 계산하기가 화가 난다. 밑의 예를 보자. void check_real(int n){ double answer = n*(1.0/n); if(answer != 1) printf("not the same number!!\n"); } int main(){ for(int i = 1; i < 100; i++) check_real(i); } 간단한 x * (1 / x)가 1인지에 대한 함수이다. 수학적으로 당연히 저 printf문은 실행되서는 안된다. 하지만 이 코드를 실행시키면, 어째서인지 한 두개의 printf문이 실행된다. 이런 경우 때문에 실수(real number) 연산은 예외를 적용..
목차 산술 오버플로 산술 오버플로는 코딩을 하면서 정말 흔하게 접할 수 있는 오류이다. (특히 C++, C에서 말이다. JAVA는 내가 안써봤고. 나머지 언어에서는 경험을 해본적이 없다.) 왜 산술 오버플로라는 오류는 흔하게 발생할까? 첫째로, 프로그램 언어는 따로 오버플로를 경고하지 않는다. 둘째로, 알고리즘을 확인하는 과정에서 논리에 집중하다 보면, 산술 오버플로를 신경쓰지 못하고 지나칠 수 있다. 그럼 산술오버플로의 사례를 살펴보자. 산술 오버플로의 사례 너무 큰 결과 C, C++, JAVA등 숫자 자료형이 크기가 제한 되어 있는 경우, 어떤 문제를 푼 결과값이 자료형의 한계를 넘어설 때 이 오류가 발생한다. 흔히 32비트 자료형을 습관적으로 사용하다가, 결과가 32비트 자료형을 넘는것을 인식하지 ..
목차 코딩하면서 자주 하는 실수들. 코딩을 하다보면 정말 정말 정말 많은 실수가 생긴다. 이런 실수들을 조금이나마 줄이고, 발생했을 때도 빨리 알아차리면 좋겠다. 배열 index 접근 오류 정말 코딩하면서 제일 많이 발생하는 오류가 아닐까 싶다. 접근하려는 인덱스가 존재하지 않아서, 멈추고, 오류가 발생한다. 오류가 발생하면 괜찮지만, int arr[10]; int arr2[10]; 정말 만의 하나의 경우로 이 배열 두개의 메모리가 이어진 상태로 만들어져서 오류가 발생하지 않으면 정말 큰일이다. 오류인지도 모르고 작성하다가, 한참 뒤에 뭐가 문젠지 하나하나 찾아가야한다. 정말 화가 나는 경우다. 이 실수, 오류를 막는 법! 대공개!! 바로 이걸 안나게 코드를 짜면 된다. 뭐 우쩌겠나. 배열에 접근할 때 ..
