The masterplan

트리 계층적인 구조를 나타내는 자료 구조 보통 뿌리(root)가 위에, 나뭇가지(branch)와 잎(leaf)이 아래로 자라는 형태로 표현 트리 사용 예:회사 조직도, 대학 교과 과정의 수강 트리, 파일 시스템 디렉터리 구조 트리의 구성 요소 노드:트리의 데이터를 저장하는 원소 단위.정점. 에지: 노드와 노드를 연결하는 선. 간선. 트리의 에지는 부모-자식 계층 관계만을 나타냄 노드의 개수가 N이면 항상 N-1개의 에지가 존재 트리 용어 루트(root):맨 위의 노드 부모(parent)-자식(child):에지로 연결되어 있는 상대적인 관계. 위의 노드가 부모, 아래의 노드가 자식 리프(leap):가장 아래의 노드(가장 말단) 내부 노드(internal node):자식노드 중 리프가 아닌 것 형제(sibl..

처음에는 그냥 평범하게 선형 탐색을 활용했더니, 역시나 시간초과. 다른 방법으로 풀어야 했다. 그래서 사용 한 방법이 이진 탐색. upper_bound-lower_bound하면 원소의 갯수를 알수 있다. #include #include #include using namespace std; int main() { int N, M, n; std::vector v; std::cin >> N; while (N--) { std::cin >> n; v.push_back(n); } std::sort(v.begin(), v.end()); std::cin >> M; while (M--) { std::cin >> n; std::cout

선형 탐색(linear search) 전체 자료를 처음부터 마지막까지 순서대로 탐색하는 방법. 순차 탐색. 하나의 for loop: 시간 복잡도=O(n) 작정이 간단하고 직관적 정렬되지 않은 자료에도 사용가능 비효율적 bool linear_search(int data[], int n, int target) { for (int i = 0; i < n; i++) { if (data[i] == target) return true; } return false; } 이진 탐색(binary search) 정렬된 배열에 대해 검색 단계별로 검색 범위를 반으로 줄여가면서 데이터를 탐색하는 기법 시간 복잡도 : O(log n) 선형 탐색에 비해 검색 속도 빠름 이미 정렬되어있는 데이터에만 적용 가능 bool binary..

배열에서 중복된 원소를 없앤 후 정렬을 해주면 된다고 생각함. 그리고 미리 또다른 배열을 만들어 입력 좌표를 미리 저장한 후 정렬/중복원소 삭제된 배열에서 찾는 알고리즘을 생각해냈다. 또 찾을 때 이중for문을 이용하기 보단 vector stl에 있는 find를 쓸려고 했고, 사용해보니 시간 초과가 났다. 그리서 lower_bound를 사용하여 풀었다. #include #include #include using namespace std; int main() { int N; cin >> N; vector v(N); for(int i=0;i> v[i]; } vector v2 = v; sort(v.begin(),v.end()); v.erase(unique(v.begin(), v.end()), v.end());..

분할정복 :주어진 문제의 규모가 커서 한 번에 해결하기 어려운 경우, 이를 작은 부분 문제로 나눠서 해결하는 방식 분할 : 주어진 문제를 동일한 방식으로 해결할 수 있는 부분 문제로 나누기 정복 : 각 부분 문제에 대한 솔루션 구하기 결합 : 각 부분 문제의 솔루션을 결합하여 전체 문제에 대한 솔루션 구하기 병합 정렬 :분할 정복에 의한 정렬 알고리즘의 하나 입력 배열을 두 개의 부분 배열로 분할->각 부분의 배열의 원소가 하나가 될 때까지 반복 부분 배열을 병합->이때 병합된 배열의 원소가 정해진 정렬 순서에 부합되도록 순서를 조정 병합 정렬의 시간 복잡도 배열을 분할 또는 병합하는 단계:log n 배열 병합하는 과정의 시간 보잡도:O(n) 전체 시간 복잡도:O(n log n) 병합 정렬의 특징 실제 ..

정렬(sort) 주어진 데이터를 정해진 기준에 따라 순서를 재배열 하는 작업. 오름차순 or 내림차순 정렬 알고리즘의 종류 버블정렬(bubble sort) 선택정렬(selection sort) 삽입정렬(insertion sort) 위의 세가지 정렬들은 구현은 단순하나 비효율적이다. 아래의 정렬들은 구현은 복잡하나 다소 효율적이다. 쉘정렬(shell sort) 병합정렬(merge sort) 퀵정렬(quick sort) 힙정렬(heap sort) 기수정렬(radix sort) 버블 정렬 :정렬되지 않은 부분에서 인접한 두 원소의 크기를 비교하여 교환하는 작업을 반복. 시간복잡도 = O(n^2) void bubble_sort(int data[],int n) { for(int i=0;ii;j--){ if(dat..

군대 동기에게 디엠이 왔다. 평소에 저질 릴스들을 많이 주고 받는 사이여서 또 무슨 ㅈㄹ맞은 내용일까 생각하면서 디엠을 읽었다. 군대에서 찍은 영상이었다. 대충 새벽근무에 늦게 일어난 이병이 나오는 릴스였다. 갑자기 예전 생각이 났다. 나도 이런 적 있는데. 개추억이네ㅋㅋ. 지금은 추억이 되었다. 왜 좋은 기억으로 남아있을까? 분명 그때 그 상황은 심각했던거 같은데. 영화 가 생각이 났다. 할머니는 미나리였다. 미나리는 대충 키워도 잘 자란다. 그런데 맛도 있고 건강하다. 영화 속 가족들은 할머니의 가르침을 받았다. 손자 데이빗은 아픈 심장을 가지고 세상에 맞설 용기를 얻었고, 자신을 제외한 세상 모든 것을 꼬인 시선으로 바라보던 사위 제이콥은 주변을 신뢰하기 시작했다. 또한 가족의 미래에 걱정만 가득했..

개강 3주 차. 날이 춥다. 3년 전 이맘때 날씨는 안 이랬던 거 같은데. 지금은 도서관에 있다. 여기 많이 바뀌었더라. 아니, 여기도 많이 바뀌었더라. 2년 전 엔 안 이랬는데. "2년 전 엔 안 이랬는데.." 요즘 내가 제일 많이 하는 말 중 하나다. 고작 2년 남짓한 그 시간 동안 정말 많이 바뀌었더라. 집 앞에는 서브웨이가 들어왔다. 그 근처 단골 분식집은 임대를 내놓았다. 소풍 날에도, 수능 날에도, 어쩌다 가끔 평범한 주말에도 이 집 김밥을 먹었었는데. 떡볶이는 개맛없긴 했다. 나만 멈춰 있었다. 연천의 겨울은 너무 추워서 시간마저 얼어붙었다고 생각했다. 마치의 하퍼처럼. 조휴일의 말처럼 부산의 동백나무 꽃은 멈춰있는 나를 비웃듯 피어났다. 난 ㅅㅂ 눈치우고 있었는데. 작년엔 라는 영화가 자주..

큐 stl을 이용하면 된다. 그리고 k-1까지의 큐의 front를 뒤로 push해주고 k번째 원소를 pop해준다. 그리고 이것을 큐의 원소가 다 없어질 때 까지 반복한다. #include #include using namespace std; int main() { int N,K; cin>>N>>K; queue q; queue qq; for(int i=1;i

queue stl 을 사용하면 엄청나게 쉽게 풀 수 있다. #include #include using namespace std; int main() { int N; cin>>N; queue q; for(int i=1;i1){ q.pop(); q.push(q.front()); q.pop(); } cout