잡다로그

DFS 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 과정 BFS와 동일한데, 큐가 스택으로 바뀐다. 시작하는 칸에 스택을 넣고 방문했다는 표시를 남긴다. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다. 해당 칸에 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다. 스택이 빌 때까지 2번을 반복한다. 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. 구현 BFS에서 구현했던 코드를 참고한다. 스택으로만 바꾸면 됨. 2023.11.13 - [Algorithm] - [C++/코테] BFS [C++/코테] BFS 개념 설명 글이므로 언어와 상관없이 읽으실 수 있습니다...

스택 Stack FILO 자료구조. 먼저 넣은 것이 가장 나중에 나온다. 프링글스 통처럼! 수식의 괄호 쌍, 전위/중위/후위 표기법(코테 X), DFS, Flood Fill 등에 활용된다. 스택의 성질 원소의 추가와 제거는 O(1) 제일 상단의 원소 확인이 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다. STL에서도 기능이 없지만, 배열을 이용해서 구현하면 가능하도록 만들 수는 있다. 스택의 구현 배열 또는 연결 리스트를 사용하여 구현할 수 있다. 배열로 구현 시, 원소를 담을 큰 배열 1개, 인덱스 저장 배열 1개 필요 data[0]부터 저장 pos: 다음 원소 삽입 위치. 즉 스택의 길이(원소의 수) push함수 pos가 가리키는 위치에 원소를 삽입한다. pos를 1 증..

배열은 데이터를 자주 바꾸지 않고 그냥 쌓아두고 싶을 때 활용할 수 있다. 입력을 담아두기 위해 많이 사용. 배열의 성질 $O(1)$에서 k번째 원소를 확인/변경 가능하다. 추가적으로 소모되는 메모리의 양(overhead)가 거의 없다. Cache hir rate가 높다. 메모리 상에서 연속한 구간을 잡아야 해서 할당에 제약이 걸린다. 배열의 연산 $O(1)$ 임의의 위치에 있는 원소를 확인/변경 원소를 끝에 추가 마지막 원소를 제거 $O(N)$ 임의의 위치에 원소를 추가 - 평균적으로 N/2개의 원소가 밀리기 때문 임의의 취이에 있는 원소를 제거 배열 사용팁 배열 전체를 특정 값으로 초기화하기 cstring 헤더에 있는 memset 함수를 활용하는 방식 (비추) for문을 사용해서 하나하나 바꿔주는 것..

C++ 복습을 위해 기초 문법을 일부분 기록한 글입니다. STL과 함수 인자 C++에서는 함수 인자에 값을 보내면 복사본을 전달한다. 그렇기 때문에 함수에서의 동작이 원본 변수에 적용되지 않게 되는데, 그러한 원리를 값에 의한 호출이라고 한다. 값에 의한 호출 (Call by value) #include using namespace std; void func(int a) { a = 5; } int main(void) { int t = 0; func(t); cout