알고리즘
-
[BOJ] 7562.나이트 이동(BFS)SW/Algorithm 2018. 7. 9. 20:49
깃허브 코드보기 /**************************************************************** 날짜: 2018/07/09 작성자: 임중현 문제: 백준 7562.나이트의 이동 풀이: 방향(8방향)을 설정하고 bfs로 한줄씩 찾아가면서 처음으로 찾는것이 최소로 움직이는 횟수 노드의 뎁스를 알아야 함으로 DFS가 아닌 BFS로 풀면 된다. *****************************************************************/ #include using namespace std; int dx[]={-1,-2,-2,-1,1,2,2,1}; int dy[]={-2,-1,1,2,-2,-1,1,2}; struct Position{ int x,y; P..
-
[BOJ] 7513.준살 프로그래밍 대회(맵)SW/Algorithm 2018. 6. 11. 15:16
깃허브 코드보기 /****************************************************************날짜: 2018-06-08작성자: 임중현문제: 백준 7513.준살 프로그래밍 대회 풀이: 들어온 단어를순서대로 맵에 매핑하고 숫자(마지막에들어오는)대로 뽑음 *****************************************************************/ #includeusing namespace std; int main(){int t;cin>>t;for(int tc=1; tc>m;map mapping;string input; for(int i=0;i>input;mapping.insert(make_pair(i,input));}cin>>n;string s..
-
[알고리즘] 다익스트라 알고리즘 (최단거리)SW/Algorithm 2018. 1. 17. 20:00
다익스트라 알고리즘 (Dijkstra Algorithm) 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. O(v^2)의 복잡도 이지만 우선순위큐를 사용함으로 O(Elogv)의 시간 복잡도를 가지게 된다. E는 간선 v는 노드 // E => 최악의 경우 E번의 탐색한 노드를 집어 넣는 경우가 발생한다. 시작점에서 연결되있지 않은 노드도 무한대 크기만큼 연결되어있다가정하고 알고리즘을 수행한다. E[][] 는 간선들의 크기를 나타낸다.(그래프) D[]는 시작점에서 모든 정점을 가는 최소값을 가지게 된다. q는 시작점에서 q에 있는 정점들을 방분한다. D[v]=min(D[v],D[select_v]+E[select_v][v]) 풀이 시작점 하나를 잡는다. q에 시..
-
[알고리즘] BacktrackingSW/Algorithm 2018. 1. 6. 21:00
Backtracking 미로찾기 막다른 골목이면 이제까지 온 길을 돌아오게 된다. (백트레킹 -> 스택 & 재귀?) right hand / left hand -> 오른손(왼손)으로 벽을 짚고 간다.(출구가 중간에 있으면 안될 경우도 생김) N-Queen NxN 크기의 체스판에서 퀸을 같은 행, 같은 열, 같은 대각선 위에 놓지 않을 수를 구하기. 문제 해법 4개의 퀸을 모두 다른 행에 놓으면서 해가 되는 퀸의 열의 위치가 어디인지 계산 Candidate 해 모두 다른 행에 대한, 가능한 모든 열의 조합 [(1,1),(2,1),(3,1),(4,1)], ..... , [(1,4),(2,4),(3,4),(4,4)] => 4-퀸 = 4 4 4 * 4 해의 개수 (n^n) State-Space Tree : 모든 ..
-
[알고리즘] 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..