본문 바로가기

✨ Algorithm/🐕‍🦺 바킹독 개념10

[0x0A] DFS DFS depth first search 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 예시 모든 칸이 스택에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N) 시작하는 칸을 스택에 넣고 방문하는 표시를 남김 스택에서 원소를 꺼내서 그 칸과 상하좌우로 인접한 칸에 대해 (3)을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때까지 (2)를 반복 #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] = { ... }; // 1.. 2023. 6. 26.

[0x09] BFS BFS breadth first search 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 과정 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N) 시작하는 칸을 큐에 넣고 방문했다는 표시 남기기 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 (3)을 진행 해당 칸을 이전에 방문했다면, 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 (2)를 반복 // x가 행, y가 열 #include #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502.. 2023. 6. 26.

[0x08] 스택의 활용(수식의 괄호 쌍) 수식의 괄호 쌍 괄호쌍이 올바른지 체크 관찰 괄호 1종류 괄호 2종류 → 연속된 괄호 삭제는 가능 해결 방법 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다 2023. 6. 26.

[0x07] 덱 정의와 성질 정의 double-ended queue 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료 구조 성질 원소의 추가와 제거 : O(1) 제일 앞/뒤의 원소 확인 : O(1) 제일 앞/뒤이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 인덱스로 원소 접근 가능 기능과 구현 const int MAX = 1e7; int data[2*MAX + 1]; int head = MAX, tail = MAX; // 시작 지점을 배열의 중간으로 : 앞뒤로 확장 // head : 시작. tail : 다음에 들어갈 원소의 자리 void push_front(int x) data[--head] = x; void push_back(int x) data[tail++] = x; void pop_front() head++; v.. 2023. 6. 26.

이전 1 2 3 다음

티스토리툴바