본문 바로가기

분류 전체보기311

[Deque] 1021 회전하는 큐 문제에 나온 그대로 하면 풀리는 문제이다. M 2019. 8. 27.
Circular Queue Circular Queue Queue의 front에서 추가, 삭제시 O(N)이 걸린다는 것을 보완합니다. 1) List(연결 리스트) 이용해서 구현 #include #include using namespace std; list::iterator circularNext(list &l, list::iterator &it) { return next(it) == l.end() ? l.begin() : next(it); } list::iterator circularPrev(list &l, list::iterator &it) { return it == l.begin() ? --l.end() : prev(it); } list circle; int main() { for (int i = 1; i < 6; ++i) { .. 2019. 8. 27.
[Queue] 19.5 외계 신호 분석 이 문제는 종만북, '알고리즘 문제해결 전략 2' 에 나와있는 예제 입니다. RNG를 만드는 방법, 입력이 너무커서 한번에 넣지 못하니, 온라인 알고리즘을 만드는 법을 배웠습니다. 또한 구간합을 탐색하는 데 이미 계산한 것들을 queue에 push하여 담고, 필요없는 것들을 즉각적으로 pop하여 필요한 구간합만 계산하는 아이디어도 얻었습니다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; // 선형 합동 난수 생성기(Linear congruential random number generator) struct RNG { unsigned seed; RNG() : seed(1983) {} unsigned next() { unsig.. 2019. 8. 27.
19. [스택, 큐, 데크] 간단 정리 구현 1. 연결리스트 O(1) : 리스트 양쪽 끝에 추가와 삭제 O(N) : 임의의 노드의 할당, 삭제, 포인터 따라가기(traveling) 2. 동적 배열 스택 : 추가, 삭제 O(1) 큐 : rear(뒤) 부분 추가, 삭제 O(1) / front(앞) 부분 추가, 삭제 O(N) 따라서 circular queue(혹은 circular buffer)를 만들기도 함. (추가, 삭제 발생시 head와 tail을 변경) : O(1) 데크 : 둘다 O(1) 온라인 알고리즘 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘. 입력의 크기가 너무 커서 프로그램상에 올려놓을 수 없을 때 사용한다. 2019. 8. 27.
8. 동적계획법(DP) 2 메모이제이션 구현 패턴 int fun(int a, int b) { // Process the base case if (...) return ...; // (a, b)에 대한 답을 구한 적이 있으면 return int& ret = cache[a][b]; if (ret != -1) return ret; // Get what you want here ... return ret; }memset(array, 0, sizeof(array)); for문보다 쉽게 초기화 할 수 있음. 단, 0과 -1만 &#39;운 좋게도&#39; 초기화 될 수 있습니다. 메모이제이션의 시간 복잡도 분석 = (부분 문제 수) x (한 부분 문제 당 반복문의 수행 횟수) 2019. 8. 26.
선형자료구조 1. 동적배열 - 원소를 순서대로 저장 --> 인덱싱(원소찾기)이 O(1) - 삽입, 삭제 O(N) - 원소들이 메모리에 연속해 배치되어 있어 CPU 캐시의 효율을 높여줍니다. capacity: 미리 여유있게 할당받은 메모리의 크기 = 배열의 용량 size: 배열의 원소 수 용량(capacity)이 꽉찼을 때, 배열에 새로운 원소를 추가하려면 아래 방식으로 재할당을 하여야 합니다. 더 큰 새 배열을 동적으로 할당받고, 기존 배열의 내용을 모두 복사한 다음, 배열에 대한 포인터를 바꿔치기(swap)해야 합니다. - append() 연산과, 성능 append() 연산을 여러번 할 때 배열의 최종크기가 얼마일지 미리 짐작할 수 있다면, 동적배열의 용량을 미리 늘려둠으로써 재할당 비용을 없앨 수 있습니다. --.. 2019. 8. 26.
[vscode] 원격 서버 접속, Remote Development using SSH 원격서버에서도 vscode로 작업을 하고 싶습니다. 필요사항으로는 1. 로컬에 ssh 가 설치되어 있어야하고, 2. 당연히 vscode가 설치되어 있어야 하고, 3. vscode Extensions(단축키 Ctrl+Shift+X) 에 가셔서, Remote Development extension pack 을 깔아야 합니다. - 일반 리눅스/max 사용자라면 다음을 다운받아주시고, 저는 윈도우를 쓰는 입장이라, 리눅스를 사용하기 위해 WSL을 쓰는데 Remote - WSL 이 자동으로 install되어있었습니다. 자 환경이 갖추어졌다면 이제 시작해볼가요? 예를들어 접속할 원격 서버 ip가 111.222.33.44이고 host가 jin이라고 해봅시다. 1 >> 먼저 원격 서버의 호스트에 인증key 를 설정해야.. 2019. 8. 26.
[Disjoint Set] 1717 집합의 표현 예제입력 및 출력) 7 8 0 1 3 0 3 2 3 4 5 6 7 1 1 7 NO 0 7 6 0 3 2 3 4 5 6 6 1 7 1 NO 0 3 7 0 3 2 6 4 5 6 6 0 4 2 0 3 2 6 2 5 6 6 0 1 1 0 6 2 6 2 5 6 6 1 1 1 YES 이 문제를 풀기 위해서는 Disjoint Set을 공부하면 좋습니다. 집합을 표현하고 다루는 3가지 함수를 배워봅시다. Disjoint Set은 만드는 방법이 연결리스트와 트리가 있지만, Union(합집합), Find 의 성능이 트리가 더 우월합니다. 자료구조는 트리로 가정해봅시다. 1. makeset() {0}, {1}, {2}, ... , {n} 의 집합을 만들어봅시다. p[n+1] 배열을 만들고, p[x] = x 라고 하면, 예를.. 2019. 8. 26.
[ITK-SNAP] Exception occurred during ITK-SNAP startup 문제 해결 탐색기에 %APPDATA% Enter >> AppData 접근 Roaming/itksnap.org/ITK-SNAP/UserPreference.xml 삭제 2019. 8. 20.
[잠실역, 방이동 맛집] 엄군고기 리뷰 안녕하세요, Wordtory 입니다! 오늘은 잠실역 바로 앞, 방이동에 있는 맛집, 엄군고기를 리뷰해볼까 합니다. 잠실역 8호선에서 10번 출구로 나오면 '송파구청' 보이는데요, 송파구청에서 조금만 걸어내려가면 얼마 지나지않아 방이동 먹자 골목이 나옵니다. 가서 제가 주문한 것은, 3인분 짜리 600g 삼겹살이었어요. '고원돈 삼겹 한근' 가격은 38,000원 입니다. 다른집에 비해 저렴하지요? 위에 보시는 것과 같이나오고, 종업원이 맛있게 구워주십니다. 종업원은 여러분 계시는데, 저희는 처음에 할머니가 구워주셔서 그랬는지 더 맛있었습니다 : D 4명이 모이기로 했는데, 친구 한 명늦게와서 먼저먹어버리기 시전했습니다. 밑반찬 메뉴는 위와 같이 샐러드, 콩나물파절이 등이 나옵니다! 쌈장과 소금을 각자마다 .. 2019. 8. 17.
728x90

티스토리툴바