sncap Style

Dynamic Programming과 Greedy Algorithm 다이나믹 프로그래밍(Dynamic Programming)과 그리디 알고리즘(Greedy Algorithm)은 모두 최적화 문제를 풀 때 사용하는 알고리즘 기법이다. (두 기법 모두 알고리즘 자체가 아닌, 알고리즘 기법-전략-인데, 왜 하나는 Programming이 붙고, 다른 하나는 Algorithm이 붙는 지.. 그 이유는 모르겠다..) 두 기법 모두 비슷한 문제를 풀 기 때문에 언뜻 보면 두 알고리즘의 차이가 애매모호할 수 있다. 오늘은 이 두 기법의 개념을 정리하여 차이점을 확실히 알아두려 한다. 개념 정리 부분은 NHN NEXT의 자료구조 및 알고리즘 과목 lecutre note를 참고하였다. Dynamic Programming ..

1/4: 다이나믹 프로그래밍어려운 다이나믹을 배워봅니다.격자판 채우기: https://www.acmicpc.net/problem/1648연습 시즌: https://www.acmicpc.net/problem/9023트리의 독립집합: https://www.acmicpc.net/problem/2213팰린드롬 경로: https://www.acmicpc.net/problem/2172Sequence: https://www.acmicpc.net/problem/2291택배: https://www.acmicpc.net/problem/1866가로등 끄기: https://www.acmicpc.net/problem/2315사수아탕: https://www.acmicpc.net/problem/2419팰린드롬: https://ww..

Greedy Algorithm (탐욕 알고리즘) 일들의 수행시간이 서로 겹치지 않으면서 일을 되대로 많이 할 수 있도록 스케쥴링하는 문제. Greedy 말그대로 탐욕 알고리즘은, 매 순간마다 최선의 선택을 하는 그런 알고리즘이다.즉, 선택할때마다 가장 좋다고 생각되는 것을 선택해 가며, 최종적인 답을 구하는 알고리즘이라 할 수 있다. 그러나, 이 알고리즘을 설계 할 때 유의할 점은 전체를 고려하는 게 아니라 문제를 부분적으로 나누고, 나누어진 문제에 대한 최적의 해답을 구함으로써, 전체적인 최적의 해가 될 수 있는 경우를 찾는 방법이다. 유의할 점은, 매 순간마다 최선의 선택을 하여 나온 해가 반드시 전체적인 최적해는 아니라는 것이다. 그렇기 때문에, 탐욕 알고리즘을 사용할 때에는 전체적인 최적해 인지를..

동적계획법 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -위키백과 조금더 쉽게 설명하자면 작은 문제들을 해결한다음에 이 해결한 결과들을 바탕으로 보다 더큰 문제의 해답을 얻는 방법이다. (작은 문제들의 해를 배열에 저장한 다음 그것들을 순환적인 성질을 이용하여 결합해 큰 문제의 해를 구하는 것) 동적계획법의 특징은 다음과 같다. 1.동적계획법은 해를 저장하는 배열을 사용한다 ( Table) 동적계획법이 분할정복( Divide and conquer : 큰..

알고리즘 공부할때... 동적계획법 이때....점화식이란걸 접함. http://blog.naver.com/PostView.nhn?blogId=cyc083&logNo=150152541601 여기 자세히 설명이되어 있는데.. 어렵다..-_-;;

K번째 최단 경로 (https://www.acmicpc.net/problem/1854)도로 포장 (https://www.acmicpc.net/problem/1162)길의 개수 (https://www.acmicpc.net/problem/1533)도시 분할 계획 (https://www.acmicpc.net/problem/1647)전구와 스위치 (https://www.acmicpc.net/problem/2138)동전 뒤집기 (https://www.acmicpc.net/problem/1285)동전 뒤집기 (https://www.acmicpc.net/problem/1640)최대 곱 (https://www.acmicpc.net/problem/1500)로봇 조종하기 (https://www.acmicpc.net/pro..

http://clearpal7.blogspot.kr/2016/06/2.html 교차와 거리, 면적> *직선과 직선의 교차 x좌표에 대해 푼 뒤 방정식에 대입해 y좌표를 구하는 코드를 작성하거나 하면 수평선이나 수직선 같은 예외에 제대로 대응 할 수 없습니다. 직선의 교차를 작성할 수 있는 간단한 방법은 직선을 한 점과 방향벡터, 즉 a+p*b형태로 표현하는 것입니다. a+p*b와 c+q*d의 교점을 구하기 위해서는 a+p*b=c+q*d방정식을 풀면 된다. ax+p*bx=cx+q*dx ay+p*by=cy+q*dy 연립방정식을 p에 대해 정리하면 p=(c-a)Xd/bXd 이 p를 a+p*b에 대입해 원하는 점을 구할 수 있다. *선분과 선분의 교차 이 경우는 한 직선위에 두 선분의 판단에 유의해야 한다. 한..

http://1nsunym.github.io/ko/online/01-09-2016/algorithm-polygon-area 다각형 넓이볼록다각형의 경우삼각형의 면적은 삼각형을 이루는 두 벡터의 외적의 절대값의 절반입니다. a⃗ a→와 b⃗ b→가 이루는 삼각형의 면적인 TT는 다음과 같습니다.a⃗ =(x2−x1,y2−y1,0)a→=(x2−x1,y2−y1,0)b⃗ =(x3−x1,y3−y1,0)b→=(x3−x1,y3−y1,0)T=∣∣∣a⃗ ×b⃗ 2∣∣∣T=|a→×b→2|T=∣∣∣(x3−x1)(y2−y1)−(x2−x1)(y3−y1)2∣∣∣T=|(x3−x1)(y2−y1)−(x2−x1)(y3−y1)2|삼각형을 전부 더하면 됩니다.오목다각형P1(x1,y1)P1(x1,y1)을 오목다각형의 꼭지점 중 내각이 ππ 이..

http://cookyworld.tistory.com/49 ClockWise(이하 CW)와 CounterClockWise(이하 CCW)알고리즘은 한 선과 한 점의 위치관계를 구할 때 쓰입니다.응용하면 선과 선의 위치관계도 구할 수 있습니다. 예를 들어 보면, 위와 같이 선분AB(보라색)가 있습니다. 연보라색은 선분AB의 연장선으로 이해를 돕기 위해 추가했습니다.그리고 점i(빨강색), 점j(초록색), 점k(파랑색)가 있습니다. CW, CCW알고리즘으로는 점 i, j, k가 선분AB의 시계방향에 있는지 반시계방향에 있는지 혹은 일직선(연장선)상에 있는지 구할 수 있습니다! 다음의 식을 통해서 각 위치관계를 알 수 있습니다.점 K가 있다면 K의 x좌표는 K.x, K의 y좌표는 K.y입니다.res = (A.x ..