c++ (5) 썸네일형 리스트형 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) DFS(Depth First Search)는 루트 노드에서 시작해 자식 노드들을 순서대로 탐색하는 알고리즘으로 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 길찾기 같은 기능을 구현하거나 모든 노드를 방문해야하는 경우에 사용한다. 재귀함수는 스택으로 구현한다. BFS(Breadth First Search)는 루트노드에서 시작해 인접한 노드들을 먼저 탐색하는 알고리즘으로 DFS와는 반대다. 최단경로를 구현할때 사용한다. 큐로 구현한다. 이제 그래프를 만들어서 구현을 해보겠다. vector를 사용해서 위의 그래프를 만들었다. DFS재귀함수를 사용하여 구현했다. bool형 배열로 방문했는지 체크하고 인접 노드들이 방문했는지 체크하여 방문하지 않았다면 재귀적으로 그래프를 탐색한다.결.. 백트랙킹 Backtracking 알고리즘은 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법이다.모든 경우의 수를 따져가며 해를 찾다가 필요가 없다고 판단되면 그 경우를 배제한다. 이를 가지치기라고 한다.백트랙킹으로 DFS와 BFS 모두 구현이 가능하다. DFS와 BFS는 다음에 더 공부해 보겠다. 예제 - 프로그래머스 피로도https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krcheck라는 배열을 만들어서 방문 체크를 하고 .. 배열(Array), 리스트(List), 벡터(Vector) 배열https://learn.microsoft.com/ko-kr/cpp/cpp/arrays-cpp?view=msvc-170 배열 (C++)표준 C++ 프로그래밍 언어로 네이티브 배열 형식을 선언하고 사용하는 방법을 알아봅니다.learn.microsoft.com배열은 연속된 메모리영역을 차지하는 동일한 형식의 집합이다. 배열의 인덱스에는 랜덤 접근이 가능하고 컴파일시 크기가 확정되어 크기를 미리 지정해줘야 한다. 배열을 동적으로 할당할수 있다. 리스트https://learn.microsoft.com/ko-kr/cpp/standard-library/list-class?view=msvc-170 list 클래스자세한 정보: list 클래스learn.microsoft.com 리스트는 비연속적인 메모리 구조를 갖는.. Stack과 Heap 스택과 힙에는 메모리들이 저장된다. 각각 저장되는 메모리들이 다르다. 스택에는 지역변수, 함수의 매개 변수 등이 저장되고 함수의 호출때 할당되고 호출이 종료되면 소멸한다.스택은 후입선출(LIFO)의 입출력 형태를 가지고 있는 자료구조다. 크기가 컴파일타임에 정해진다. ※ 컴파일타임(Compiletime), 런타임(Runtime)컴파일타임: 개발자가 작성한 코드를 컴파일(개발자의 코드를 컴퓨터가 이해할 수 있는 언어로 바꿔주는 과정)을 통해 프로그램이 실행가능하게 되는 과정런타임: 컴파일을 마친 프로그램이 사용자에 의해 실행되어 동작할 때 힙에는 동적할당 메모리가 저장된다. C++에서 new로 할당하면 힙영역에 할당되는 것이다. 하지만 C#에서는 Garbage Collection이 있어 자동으로 메모리가 .. 포인터 https://learn.microsoft.com/ko-kr/cpp/cpp/pointers-cpp?view=msvc-170 포인터(C++)Microsoft C++의 원시 포인터 및 스마트 포인터 정보입니다.learn.microsoft.com포인터는 개체의 메모리 주소를 저장하는 변수이다.변수 같이 어떤 데이터를 저장하기 위해 메모리에서 저장할 공간을 할당받는다. 이때 데이터가 저장된 메모리 시작주소를 주소 값이라고 한다. * 참조연산자를 붙여 포인터 변수를 선언한다. 포인터에 저장된 주소에 저장되어 있는 값을 반환한다.& 주소연산자는 해당 변수의 주소값을 반환한다. ptr 포인터 변수를 변수 a의 주소값으로 초기화해서 출력해보면 ptr은 a를 참조하기 때문에 3이 출력된다. 참조연산자 없이 그냥 출력.. 이전 1 다음
