Rocknz 's Blog

잘 참고 해야겠다. 증명은 https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf참고!

Gradient Descent => $$x_{n+1} = x_n - \nabla f(x_n) \times \alpha $$ Newton Method => $$x_{n+1} = x_n + (\nabla^2 f(x_n))^{-1} \times \nabla f(x_n) $$ Levenberg-Marquardt algorithm (LM) => LM is used to solve non-linear least squares problems. These minimization problems arise, especially in the least squares curve fitting. https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm Line..

이진트리. (Binary Tree) 이진트리란 ? 자식노드를 최대 2개를 갖는 트리를 이진트리라고 한다.트리란 : 싸이클이 존재 하지 않고, 수직적인 구조를 가지고 있다. 가족관계도 라고 생각하면 편한데, 위로 혹은 아래로 간다고 생각하면된다. 참고 : https://ko.wikipedia.org/wiki/트리_구조 이진트리는 트리중에 자식노드를 최대 2개밖에 갖지 않는다. 그렇기 때문에 다양한 곳에 응용 할 수 있다. Heap도 이진트리를 사용하고 있고, 나중에 설명할 IndexTree 역시도 이진트리를 사용하고 있다. 이진트리의 장점이 무엇인가? 자식 노드가 두개밖에 없기때문에 자식노드중 하나를 선택할때 굉장히 효율적으로 할 수 있다. 운동경기 처럼 1:1 대결만 존재하기 때문에 이진 트리로 표현하기..

부분합과 CCW판별은 알고리즘 보다는 알고리즘 문제를 풀때의 테크닉 정도로 생각할 수 있다. 부분합.배열의 연속된 부분의 합을 구할 때, 매번 그 구간의 합을 구한다면 굉장한 시간 낭비가 된다.이럴때는 배열에 미리 0번지부터 i번지까지의 배열의 합을 미리 구해 놓으므로써부분 합을 빠르게 구할 수 있다. // // 배열 l 의 0~ n 의합을 sum에 저장해 놓는다. int sum[100]; sum[0] = 0; for( i=1; i Counter Clock Wise 의 줄인말이다. 2차원 좌표에서 세점이 존재할때 ( A, B, C ). 두점을 이은 선분을 긋는다( A -> B). 그 선분( A -> B, 방향이 A에서 B )을 기준으로 나머지 한점(C)이 시계방향에 있는지 시계 반대방향에 있는지 판별하는..

Queue와 Stack.BFS와 DFS를 설명하다보니 Queue와 Stack 자료구조를 모르는 사람들이 있을까봐 적는다.Queue 는 FIFO (First in First out : 먼저 들어간 값이 먼저 나온다. )Stack 은 FILO (First in Last out : 먼저 들어간 값이 마지막에 나온다. )QueueQueue는 일렬로 서있는 줄이라고 생각하면 된다. [ 3, 7, 1, 4, 2] 값이 큐에 존재한다면값을 빼게되면 맨앞 3값이 빠지고 [7, 1, 4, 2] 가 남는다. 그리고 값 8을 추가하게되면 [ 7, 1, 4, 2 ] 가 된다. StackStack은 입구가 하나인 좁은 엘레베이터라고 생각하면 된다. [ 3, 7, 1, 4, 2 ]값이 스택에 존재한다면값을 빼게 되면 맨뒤 2값이..

경로탐색 알고리즘 BFS, DFS경로 탐색 알고리즘이란? 그래프에서 경로를 탐색하는 방식이다.경로? A 지점에서 B지점으로 가는 길을 뜻한다. 일상생활에 비교해보면 우리집에서 서울역까지 갈려면 2호선을 타고 4호선으로 갈아타도 되고, 버스를 타고 가도 되고, 버스를 타고 가다가 내려서 4호선을 타도 된다.이처럼 다양한 경로가 존재하는데 그중에 원하는 조건을 만족하는 경로를 찾기 위해서 모든경우를 다 해보는데 이 때 쓰는 방식이 DFS(깊이 우선 탐색)와 BFS(너비우선 탐색)가 있다.DFS -> Depth First Search. BFS -> Breadth First Search.BFS와 DFS의 문제는 (DFS와 BFS) - https://www.acmicpc.net/problem/1260 위 그래프를..

Backtracking 백트래킹 알고리즘 (퇴각 검색)https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 내가 생각한 백트래킹 알고리즘은 "모든 경우"를 다해본다는 느낌이 강하다. 백트래킹에서 중간 cutting을 잘 만들면 속도를 많이 개선 할 수 있고, 대표값을 설정하면 다이나믹과 비슷한 효과도 낼 수 있다. 내 생각엔 백트래킹 기법이 가장 기초적이고 중요한 기법이라고 생각한다.백트래킹을 배우는 사람에게 늘 하는 말이 있다. 모든 문제는 백트래킹으로 해결 할 수 있다고 늘 얘기한다.결국 모든 것을 다해보면 모든 문제를 풀수있다. 하지만 시간이 오래걸리고 메모리도 많이 잡아먹는 해법이 될것이다. 그렇기 때문에 다른 알고리즘이 필요한것이..

Dynamic Algorithm. 알고리즘중 가장 중요한 알고리즘이라고 할 수있다. Dynamic 알고리즘에 가장 중요한 핵심은 "대표하는 최적 값을 이용하는 것"이다.대표하는 최적 값이란 ? 한 부분이나 구간을 대표하는 최적값이다.즉) 부분으로 나누어서 최적 값을 구하고 => 그 부분의 최적값을 이용하여 더큰 부분의 최적값을 구하고 => 점점 진행시켜 => 전체의 최적을 구해서 답을 찾는다.최적값은 문제의 내용이나 구하고자 하는 값에 따라 다르다.그렇기 때문에 문제를 풀 때 두가지를 고려해야하는데1. 부분을 어떻게 나눌 것인가 ?2. 어떤값을 대표값으로 설정해야하는가 ? 이에 대해서 문제를 통해 자세하게 다루어보는게 좋을것 같다.RGB 거리 => https://www.acmicpc.net/problem..

Greedy Algorithm . 탐욕적인 알고리즘.개인적으로 이론적으로는 간단하나 문제로 풀기 굉장히 어려운 알고리즘이라고 생각한다. 일단 greedy 알고리즘은 가장 특징적인 값 (큰거나 작은값 등등)을 이용해 답을 구하는 개념이다."이 부분에 있어 이러한 조건으로 완성하면 무조건 최선이다." 라는 느낌이 있어야한다.예를 들면) 이 필통에 작은 연필순으로 넣으면 가장 많은 연필을 넣을 수 있다. 라는 느낌이다.어떠한 상황에서 가장 크거나 작은 값이 최적이라는 증명이 반드시 필요하기 때문에, 감만 이용해서 greedy 문제로 접근했다간 틀린 반례를 만나기 쉽다. Greedy : 탐욕스럽다. 뜻과 굉장히 어울리는데 가장 큰값 작은값으로 정렬해서 푼는 경우도 많다. 길이가 1 * n 짜리 필통이 있을 때,..

SCPC 문제를 풀다가 알게 된 것인데 이런 Combination의 합을 한번에 구할 수 있다. 일단 파스칼 삼각형을 그려보면 1 1 1 1 2 1 1 3 3 11 4 6 4 1 이때 1C1 + 2C1 + 3C1 의 diagonal 합을 보면.1C1 = 2C2 이므로 1 1 1 1 2 1 1 3 3 11 4 6 4 1이 값은 Pascal 삼각형의 기본 setting인 nCm = n-1Cm-1 + n-1Cm; 을 이용하면 1 1 1 1 2 1 1 3 3 11 4 6 4 1값 한개로 표현 할 수 있다는 것을 알 수 있다.참고자료 https://en.wikipedia.org/wiki/Pascal%27s_triangle