SW/Algorithm
-
[알고리즘] LRUSW/Algorithm 2018. 1. 6. 18:30
운영체제를 공부했다면 누구나 한번쯤 들어봤을 것이다. 또한 정보처리기사에도 자주 출제되고 중요한 교체기법중 하나이다. 2017 하반기 카카오 코딩문제에도 출제될 만큼 중요한 것 같다. 운영체제를 공부하면서 이런 알고리즘을 이론적으로만 공부하면서 해결했지 직접 코딩을 해본적이없어서 시험에 마주쳤을 때 당황했다. 입력으로는 캐시 크기와 도시이름을 받고 출력으로는 걸리는 시간을 구하는 것 이다. cache hit일 경우 실행 1, cache miss일 경우 실행 5로 계산한다. cache hit : 요구되는 데이터가 이미 캐시에 로딩 되어 있는 경우이다. cache miss : 캐시에 존재 하지않을 경우 이다. LRU (Least Rescently Used) 란? LRU는 Least Rescently Used..
-
[알고리즘] Heap sortingSW/Algorithm 2018. 1. 6. 16:55
Heap sort 코드링크 insert delete min(max) Complete Binary Tree 순서대로 채워져있는 트리 배열사용 레밸의 맨 왼쪽은 2^h 루트에서 마지막 노드 = floor(logN) 2^h ~ 2^(h+1)-1개 노드 그 노드의 부모는 floor(k/2) 그 노드의 왼쪽 자식 2k, 오른쪽 2k+1 Binary Heap Binary Heap 특징 : 컴플릿트 바이너러 / min heap(부모는 자식보다 작거나 같다.) / max heap(부모는 자식보다 크거나 같다.) insert : 마지막 노드에 추가 하고 위치로 GO! (fix heap) delete(min/max) : 루트만 지울 수 있다. 루트를 삭제 마지막 노드를 루트로 올림. fix heap! Heap Constr..
-
[알고리즘] Greedy(탐욕법)SW/Algorithm 2018. 1. 6. 11:55
Greedy Algorithm (탐욕) 정의 : 매 선택에서 지금 이 순간 당장 최적인 해를 구함. 동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용. 근시안적으로 해를 구할 당시에 가장 최적인 해를 구함. 동적 계획법처럼 반드시 최적의 해를 구한다는 보장이 없다. 한번의 선택이 다음 선택에서는 전혀 무관한 값이여야 하는 매순간의 최적해가 문제의 최적해. 과정 선택 : 현 상태에서 최적해에 포함시킬 대안을 선택 타당성 조사 : 선택된 해가 주어진 문제의 조건을 만족하는지 검사 해답 조사 : 원래의 문제가 해결되었는지를 조사 WHEN? 탐욕 알고리즘을 사용해 최적의 답을 구할 수 있다는 것이 쉽게 보이면 탐욕 알고리즘을 사용할 수 있는지가 의심스럽고 다른 알고리즘으로 답을 구할 수 있는 경우 사용X 탐욕..
-
[알고리즘] String MatchingSW/Algorithm 2018. 1. 6. 05:30
스트링 매치 코드링크 브로트포스 : 한 칸씩 옮기면서.. 매칭 O(m*n) m=패턴 / n=스트링 DFA KMP algorithm DFA (Deterministic Finite Automaton) 시작 스테이트 - accept 스테이트. 패턴에 알맞는 단어가 나오면 다음 스테이트. 내부적으로는 이차원 배열을 사용(1에서 A나오면 2번으로..) DFA construction x를 구한다. x = [들어온단어][전스테이트의 x] 이다. x는 그 다음스테이션의 기본값으로 세팅하면 된다. [들어온단어][스테이트]위치에 다음 스테이트 값(i+1)을 넣는다. 반복.. (마지막은 넣지않는다.) int x=0;for(int i=0;i AAA, AABB => null) 미스매치시 이부분을 다시 사용한다.AAABBAAAC..
-
[알고리즘] Dynamic Programming (동적프로그래밍)SW/Algorithm 2018. 1. 5. 22:00
Dynamic Programming (동적계획법) 분할정복비법처럼 작은 문제들로 나누어 각각 해답을 찾고 원래 문제의 해답을 계산 하지만 중복이 발생하여 반복연산이 많아 수행시간이 길다. => 메모리제이션으로 해결(반복연산 제거) ex) 최적화 문제(최대,최소) : working backward기법 사용 (top-down 방법으로)-> 재귀식으로 정의 (중복계산발생)-> bottom-up 방식 -> 저장할 테이블을 생성 [앞 1~3번째 까지는 최적값을 계산하는 과정이고, 마지막은 최적해답을 계산하는 단계]factorial //많은 중복연산을 함. n=100int f(int n) //메모리제이션 - 미리저장{int i ,f[100];f[0]=1; //base casefor(i=1;i c(n) = c(n-1..
-
[알고리즘] 카타란 수SW/Algorithm 2018. 1. 5. 14:55
카탈란 수 코드링크 쌍을 이루는 것들을 나열하는 모든 경우의 수. 카탈란 수열 문제들 모든 괄호 짝 산 만들기 대각선 피해가기 다각형을삼각형으로 나누기 모든 괄호 짝 n쌍의 괄호가 잘 짜놓은 방법을 Cn. (A)B => A에 괄호가 k쌍 있다면 B에는 n-1-k쌍이 있다.(트리?) C1= C0C0 c2= C0C1+C1C0 c3= C0C2+C1C1+C0C2 ... Cn= Σ Ci*Cn-1-i (i는 0~n-1) Code void PrintBracket(bool *state,int size){ for(int i=1;i>n; bool state[2*100]; //n은 최대 100개, 괄호를 열것인지 닫을것인지 넣는다. Bracket(state,1,n,0); return 0;}
-
[Codeforces] Educational Codeforces Round 35/ B.Two CakesSW/Algorithm 2018. 1. 4. 22:58
Educational Codeforces Round 35/ B.Two Cakes 문제 링크 코드 링크 블로그 풀이풀이 케익 두개를 한개는 a조각으로 다른하나는 b조각으로 나눈다. n명의 사람이 오는데 접시에 자른케익을 놓는다. 한 접시에는 적어도 한조각이 있어야한다. 두가지 종류의 케익을 같은 접시에 놓을 수 없다. (문제에) 접시에 최소 캐익의 조각 개수가 최대가 되도록 한다. min(a/i,b/(n-i)) : 접시에 최소 캐익의 조각. max(ans,min()) : 최대가 되도록 int main(){ int n,a,b; cin>>n>>a>>b; int ans=0; for(int i=1;i
-
[Codeforces] Educational Codeforces Round 35/ A.NearestMinimumsSW/Algorithm 2018. 1. 4. 08:30
Educational Codeforces Round 35/ A.NearestMinimums 문제 링크 코드 링크 블로그 풀이풀이 영어가 약해서 무슨말인지 이해하기 힘들었다. 주어진 숫자 중 최소끼리 가장 가까 운 거리를 구하는 것 이다. 3 4 6 3 중 3 이 최소.. 3 에서 3은 3칸 이므로 답은 3 이다. int input[100004];int main(){ int n; cin>>n; long long min_n=1000000003; int distance=100000000; int ans=10000000; for(int i=1;i>input[i]; if(min_n>input[i]) { min_n=input[i]; distance=i; ans=100000000; } else if(min_n==in..