cyphen156

이번 글에서는 정답을 찾기 어려울 때 최대한 정답에 근접한 답을 억지로 찾아내는 근사해에 대해 다룬다.이런 정답에 근접한 답을 구하기 위해서는 값의 변화량을 추론할 수 있어야 하는데 그것을 도와주는것이 미분과 접선의 방정식이다.미분과 기울기 : 함수에서 값의 순간 변화량사실 수학은 연속적인 수로 계속 이어져 있다.이 연속적인 수들을 극한을 통해 어느 한 특정한 지점으로 계속 줄여나가다 보면 그 지점에서의 특정할 수를 근사하게 찾아낼 수 있고, 이 때의 값의 변화율을 기록한 것을 미분값(접선의 기울기)라고 부른다.도함수 : 순간변화율의 기록한 또다른 함수특정 함수를 미분한 결과를 도함수라고 부른다.미분이 특정한 순간의 순간 변화율을 구한것이라고 했다.그렇다면 이 연속적인 수들의 집합을 특정 순간을 변경해 ..

이번 글에서는 누적합과 계차라는 서로 반대 개념을 다룬다.이 둘을 다루기 전에 먼저 구간합에 대해 알아야 한다.구간합이란?수열이 있을 때 특정 구간(Chunk , Segment)단위로 요소들의 합을 빠르게 구하는 것이다.예: A=[2,4,5,1,3]A = [2, 4, 5, 1, 3]A=[2,4,5,1,3] 일 때, 구간합(2~4번 원소) = A[2]+A[3]+A[4]=4+5+1=10A[2] + A[3] + A[4] = 4 + 5 + 1 = 10A[2]+A[3]+A[4]=4+5+1=10.단순하게 구하면 O(N), 질의가 많아지면 비효율적.→ 이를 빠르게 하기 위해 누적합을 사용한다. 누적합(Prefix Sum) S[i]=A[1]+A[2]+⋯+A[i] 누적합은 수열의 요소들을 처음부터 자기 자신까지를 미리 ..

이번 챕터에서는 계산 기하학에 대해서 탐구한다. 대충 게임 수학때 햇던 내용을 떠올린다면 좋지 않을까? 싶다'수학/게임수학' 카테고리의 글 목록 '수학/게임수학' 카테고리의 글 목록Cyphen의 개인 공부 블로그입니다. 프사는 아는 동생이 그려준 그림 주인장과 싱크로율 0%cyphen156.tistory.com이 책에서는 벡터의 내적과 외적에 대해서 간단하게 다루고 있고, 수식만 보여주자면 다음과 같다벡터의 내적(Dot Product)과 외적(Cross Product)점과 선분의 거리 구하기세 점을이 존재할 때 한 점과 다른 한 점을 이어 선분을 만들고, 마지막 남은 한 점과 선분 사이의 거리가 최소가 되는 길이(수선의 발의 길이)를 구하는 문제이다. 그림으로 표현하면 다음과 같이 표현된다.그런데 사실 ..

이전 글에서는 분할정복(Divide & Conquer) 기법을 학습하였다.이번 챕터에서는 수학적으로 규칙성(점화식, Recurrence Relation) 을 찾아내어 문제를 최적화하는 기법인 동적 계획법(Dynamic Programming) 을 다룬다.우선 프로그래밍이라는 것의 본질을 생각해보자.사실 동적 계획법은 “특정 알고리듬”이라기보다는, 프로그래밍이라는 행위 그 자체와 맞닿아 있는 사고 방식이라 할 수 있다.세상에는 수없이 많은 문제가 존재한다.그리고 프로그래밍이란 그것을 컴퓨터로 표현하여 해결하는 과정은 결국 규칙을 찾아 코드화하는 행위이다.따라서 동적 계획법은 알고리듬 학습 과정에서 반드시 짚고 넘어가야 할 중요한 주제이다.코딩 테스트 관점에서의 동적 계획법다만 코딩 테스트라는 제한된 맥락에서..

수열과 정렬의 차이수열은 단순히 수나 데이터를 순서대로 나열한 것이다.정렬은 단순히 나열된 상태를 넘어, 특정 기준(오름차순, 내림차순, 사전식 등) 에 맞춰 데이터를 배열하는 과정을 말한다.정렬의 중요성데이터 위치 파악 용이데이터가 어떤 기준으로 정리되어 있으면 원하는 값을 쉽게 찾을 수 있습니다.탐색 속도 향상정렬된 데이터에서는 이진 탐색(Binary Search) 같은 효율적인 탐색 알고리즘을 적용할 수 있어, 단순 순차 탐색(O(N))보다 훨씬 빠른 O(log N) 시간 안에 원하는 값을 찾을 수 있게 해준다.검색에 사용된 알고리듬에 따라, 데이터가 저장된 구조에 따라 자료의 검색 시간이 획기적으로 차이가 나게 된다.다른 알고리의 기반정렬은 그 자체로도 중요하지만, 이후 다른 알고리즘(탐색, 최적..