목록전체 글 (122)
tony9402
차수 표기법 및 차수에 대한 정의 - Big O ( O ) - Omega ( Ω ) - Theta ( Θ ) - Small o ( o ) 1. Theta ( Θ ) N 이상의 모든 정수 n에 대해서 다음 부등식이 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다. 주어진 복잡도 함수 f(n)에 대해서 다음과 같이 정의한다. 2. Big O ( O ) 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재 하는 복잡도 함수 g(n)의 집합이다. 3. Omega ( Ω ) 주어진 복잡도 함수 f(n)에 대해서 은 N 이상의 모든 n에 대해서 다음 부등식을 만족하는 양의..
1. 재귀를 이용한 피보나치 수열 1234567891011121314151617181920#include using namespace std; typedef long long ll; ll fibo(int n){ if(n > n; cout n; if (n
Search algorithm을 보기 전에 시간 복잡도에 대한 계산을 어떻게 하는지 알아야 한다. 시간 복잡도를 계산할 때, Worst case, Best case 인 경우를 구하면 된다.Worse case는 말 그대로 최악의 상황일 때 시간 복잡도를 계산하면 되고Best case는 상황이 가장 좋을 때 시간 복잡도를 계산하면 된다. Search algorithm 검색(찾기) 알고리즘(한국말로 하니깐 뭔가 어색하다) Searching 하는 알고리즘에는 기본적으로 Binary Search, Sequential Search가 있다. 1. Sequential Search(순차 검색) 아래는 Sequential Search에 대한 Pseudo-code 이다. 12345678void Seqsearch(int n,..
※ 학교 공부 복습 겸 올리는 것들이라 틀린 부분도 있을 수도 있습니다.(틀린 부분 있으면 댓글로 남겨주시면 감사하겠습니다.) 또한 간략하게 정리하는거라 내용이 부족할 수 있어 이 글을 보시는게 도움이 될 수도 안될 수도 있습니다. 알고리즘은 위에 영어로 되어있듯이 컴퓨터를 이용해서 문제를 풀기 위한 테크닉(Technique)이다. 테크닉은 Pseudo-code로 문제 풀이 과정을 프로그래밍 언어가 아니지만 프로그래밍 하는 듯이 표현하는걸로 생각하면 된다. 알고리즘을 다른 말로 설명하면 문제 풀이를 위한 절차라고 말할 수 있다. 실제로 알고리즘은 설계단계에서 사용한다. 우리학교 컴퓨터학부에선 machine이라고 말하면 machine은 CPU라고 생각하면 된다고 한다.알고리즘에서 복잡도가 곧 성능과 관련이..
백준 11657 타임머신 SPFA 공부중.... 벨만 포드랑 비슷하면서 살짝 다른 알고리즘저번에 디피로 풀면 쉽게 풀리는 문제를 그냥 대충 BFS로 풀었는데 어떤 갓분이 그거 SPFA라고 하셔서 이번에 한번 공부해봄 그땐 음수가 없었기 때문에 사이클을 체크 하는 부분이 없어도 되지만 이 문젠 음수가 존재하여 음수 사이클 존재여부를 체크 해야함 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include#include#include#include using namespace std; qu..
백준 1504 특정한 최단 경로 우선순위 큐를 이용한 다익스트라 공부중.....(소스가 좀 드러울 수도 있음)(지금은 소스만 올리고 나중에 정리해서 수정할 예정) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include#include#include#include using namespace std; const long long INF = 98765432; vector map;priority_queue pq;vector ans;int v, e; long long Daijk(int start, int e..
백준 1753 최단경로 처음에 짤땐 모든 간선을 넣을려 하지 않고 중복된 간선이 있을 수 있어서 최소비용 간선으로 갱신을 하는 소스를 짰더니 0.7~0.9초까지 나왔다. 이 갱신하는 부분을 지우고 제출해보니깐 시간이 0.2초까지 줄어들었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include#include using namespace std; const int INF = 0x3f3f3f3f; vector map;vector visit;vector ans;priority_queue pq; ..