Algorithms13 C++/ 재귀함수의 Stack 저장 원리로 DFS 이해하기 DFS (Depth First Search) 더보기 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. -출처 위키 여기서 "맹목적 탐색" 이라는 단어가 쓰인 이유는 연결된 노드 중 임의의 하나를 선택하여 탐색을 진행하는 방법이기 때문이다. 따라서 순서 복잡하게 여러 갈래가 될 수 있음 DFS의 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. DFS의 단점 해가 없는 경로에 깊이 빠질 가능성이 .. 2021. 1. 7. C++/ Queue 자료구조 정리 Queue의 정의 - 입출력이 서로 반대쪽에서 이루어지는 제한구조. - 자료가 입력된 순서대로 출력되는 FIFO(First In First Out) 방식이다. - 입력은 front에서, 출력은 back에서 되는 구조가 기본 cplusplus 정의 더보기 queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "b.. 2020. 12. 26. C++/ Stack 자료구조 정리 Stack의 정의 - 마지막에 입력된 자료가 가장 먼저 출력되는 LIFO(Last In First Out) 방식의 자료구조 - top 이라는 인덱스 위치를 통해 push와 pop이 이루어지며, 초기상태의 top은 0 또는 -1이 된다 - top의 최대 크기 = 스택의 크기 Stack의 응용 분야 - 서브루틴 호출시 복귀 주소(Return Address) 저장 - Recursive Program(재귀 함수) 수행 시 사용 - 인터럽트 발생 시 상태 저장 - 후위식 변환 - 버퍼 - 트리 운행 시(preorder, postorder, inorder) - DFS - Quick Sort 배열로 구현해본 Stack C++ STL에서 stack을 제공하지만 직접 구현부터 해봐야 할 것 같아서 배열을 이용해 코드를 .. 2020. 12. 26. C++/공주구하기 + 조세퍼스 인프런 45강 공주구하기 알고리즘 강의를 들었고, 지난번에 봤던 코딩테스트에서 나왔던 문제라 기억이 났다 (아니면 프로그래머스에서 풀었었나..? 암튼 푼 적이 있음) 굉장히 간단한 알고리즘인데 생각해 내는게 쉽지 않았고, 같은 방법을 재활용하면 문제 해결력이 높아질 것 같아서 정리! 공주 구하기 더보기 정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다. 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시.. 2020. 12. 14. C++/ 삽입정렬 이번에야 말로 제대로 이해하기 알고리즘 공부하면서 정렬을 수 없이 많이 거쳐갔지만.. 실제로 머리에 남은건 1도 없다 이번에야 말로 제대로 이해하고 넘어가야 다음 것들도 수월하게 할 수 있을 것이라는 생각이 들어서 정리해 보려고 한다. 삽입정렬(Insertion sort)이란? - 자료 배열의 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬. 알고리즘 순서 1. 첫 번째 자료를 tmp 변수에 선정. 2. i=1, 즉 두 번째 자료에서부터 for loop를 돌린다. 3. 이중 for loop 안에서는 j가 i-1부터 0까지 돌며 , tmp와 각 자리의 값을 비교한다. 4. 만약 tmp 값이 j 자리의 자료보다 작다면, j 자리의 자료를 오른쪽으로 한 자리 당긴다. (내림차순 기준) 5. .. 2020. 11. 6. C++ Vector를 이용한 배열의 동적 메모리 할당 Cplusplus 인용 - 더보기 VectorVectors are sequence containers representing arrays that can change in size. Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage be.. 2020. 10. 24. 이전 1 2 3 다음 반응형
