본문 바로가기

알고리즘 문제

Array Roate Clockwise/Anti-Clockwise /* * clockwise rotate * first reverse up to down, then swap the symmetry * 1 2 3 7 8 9 7 4 1 * 4 5 6 => 4 5 6 => 8 5 2 * 7 8 9 1 2 3 9 6 3 */ void rotate(vector &matrix) { reverse(matrix.begin(), matrix.end()); for (int i = 0; i < matrix.size(); ++i) { for (int j = i + 1; j < matrix[i].size(); ++j) swap(matrix[i][j], matrix[j][i]); } } /* * anticlockwise rotate * first reverse left to right, the.. 더보기
Prim's algorithm using priority_queue Prim 알고리즘 개요 가중치가 있는 무방향 그래프에서 MST(최소 스패닝 트리)를 구할 때 Prim's 알고리즘을 이용할 수 있다. 본 포스팅에서는 인접 리스트로 표현된 그래프에서 PQ 자료구조를 이용해 MST를 구하는 방법을 알아 본다. 시간 복잡도는 O(E log(V)) 가 된다. ※ 참고: 인접 행렬로 구한 Prim 알고리즘 : O(V^2) Prim 알고리즘에 PQ를 이용하기 위해서는 아래 두가지 연산이 필요하다. - ExtractMin: MST에 아직 포함되지 않은 모든 정점에서 최소 키 값을 가진 정점을 가져온다. - DecreaseKey: 정점을 추출한 후 인접한 정점의 키를 업데이트 해야 하며, 새 키가 더 작으면 업데이트 한다. 알고리즘 1) 모든 정점을 무한 값을 키 값으로 가지게 초기.. 더보기
정올 1912 : 미로 탐색 문제: 정올 1912 풀이: - DFS 문제이다 - 다만, 가장 낮은 숫자의 방 부터 방문해야 하므로, 미리 인접 리스트를 정렬해 놓는다 (혹은 인접 리스트 대신에 힙을 써도 좋겠다. 즉, 힙을 원소로 가지는 벡터) - 본인의 경우 2차원 벡터를 선언하고, 노드 갯수(n)를 받자 마자 Resize를 수행해 주었는데 (왜냐하면 n을 받기 전에는 벡터를 n크기 만큼 초기화 할 수 없었으므로) 해당 방법은 실행 시간 169ms로 90점 밖에 받지 못하였고, 처음 부터 그래프 노드를 100001 만큼 늘리고 시작하니 실행시간 160ms로 통과되었다. 이상한 부분이다. #include #include #include using namespace std; int n, m; //vector v; vector v[10.. 더보기
캐시(Cache) 알고리즘 LRU 알고리즘 LFU 알고리즘 구현 LeetCode 문제 LRU 알고리즘 - 주기억 장치에 적재되어 있는 페이지들에 대해, 참조된 시간을 기준으로 교체될 페이지를 선정하는 방법 - 한 프로세스에 할당된 페이지 프레임들 모두에 페이지가 적재되어 있는 상황에서 새로운 페이지가 적재되어야 할 때는 현재 주 기억 장치에 적재되어 있는 페이지 중 가장 오래동안 참조되지 않은 페이지를 교체 (즉, 사용한지 오래 된 것을 제거) - 단점: 프로세스가 주 기억 장치에 접근할 때 마다 참조된 페이지에 대한 시간을 기록해야 한다. (참조된 페이지의 시간을 현재 시스템 시간으로 갱신한다) 아래 그림을 살펴본다. - 페이지를 참조할 때마다 시간을 갱신한다(초록색 표시) - 참조 값 5가 들어 올때 시간이 가장 오래된 것(빨.. 더보기
BOJ 9019(DSLR) 풀이 - BFS 문제 D,S,L,R 명령어 별로 경우의 수를 나눠 큐에 담고 B를 만나면 break로 빠져 나오면 된다. 고찰 - '레지스터 결과'를 보고 '명령어'를 출력해야 하므로 struct Reg를 큐에 담도록 한다. - '명령어'는 string을 이용하면 '+' 오퍼레이터로 간단하게 구현이 가능하다. - visited[10000] 배열을 두어 시작점과, 중간 숫자 결과는 방문 처리 한다!! (그렇지 않으면, 시간초과 난다) #include #include #include using namespace std; int d(int a) { return (a * 2) % 10000; } int s(int a) { if (a == 0) a = 9999; else a -= 1; return a; } int.. 더보기
Symmetric Tree(Tree 거울대칭 판별) 문제) https://leetcode.com/problems/symmetric-tree/ Symmetric Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 해설) 트리가 거울 대칭인지 판별하는 문제 풀이) 큐 하나만을 이용해서 '왼쪽 Root의 경우 왼쪽 자식'을 '오른쪽 Root의 경우 오른쪽 자식'을 매번 비교하게 할 수 있다. /** * Definition for a binary tree node. * struct TreeNode { * int .. 더보기
C++ heap 학습 목표 - 헤더파일에 속한 make_heap, pop_heap, push_heap, sort_heap 각각의 용법을 파악한다. // range heap example #include // std::cout #include // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap #include // std::vector int main () { int myints[] = {10,20,30,5,15}; std::vector v(myints,myints+5); std::make_heap (v.begin(),v.end()); std::cout 더보기
KMP 알고리즘(문자열 비교) "Is there a (longest) suffix which is also a prefix?" (접미사 중에서 접두사와 일치하는 가장 긴 것이 있는가?) ▶KMP 알고리즘 설명 - 문자열 검색 알고리즘, O(N + M). - N : 텍스트 길이, M : 패턴 길이 - 두 단계로 나뉜다. 1. KMP Substring(=pattern) Search, O(m) ABCDABCDABEE ABCDABE 를 비교하였을 때 매칭되지 않는 시점(C != E) 바로 직전의 접미사(suffix) 중에서 접두사(prefix)와 일치하는 가장 긴 길이는 얼마인가? ==> 정답 : 2 결과는 테이블 형태로 나타내는데 길이는 패턴 길이와 동일하다. 위의 예시에서 테이블은 [0 0 0 0 1 2] 이 된다. (코드) vector.. 더보기

티스토리툴바