본문 바로가기

Algorithm/알고리즘 개념 정리21

[실전 알고리즘] BFS BFS? 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 예시 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐가 빌 때까지 큐에서 원소를 꺼내고 상하좌우로 인접한 칸에 대해 처음으로 방문했다면 해당 칸을 큐에 삽입하는 것을 반복 #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] = {{1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,0.. 2022. 8. 30.
[실전 알고리즘] 스택의 활용(수식의 괄호 쌍) 수식의 괄호 쌍이란? 수식의 괄호 쌍: 주어진 괄호 문자열이 올바른지 판단하는 문제 문제 해결을 위한 관찰 문제 해결 방법 1. 여는 괄호가 나오면 스택에 추가 2. 닫는 괄호가 나왔을 경우, 2-1. 스택이 비어있으면 올바르지 않은 괄호쌍 2-2. 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 2-3. 스택의 top이 짝이 맞는 괄호일 경우 pop 3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍 연습문제 4949번: 균형잡힌 세상 (acmicpc.net) 정답 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); while(tr.. 2022. 8. 15.
[실전 알고리즘] 덱 정의와 성질 덱: 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 Double Ended Queue. 덱의 성질 1. 원소의 추가와 제거가 모두 O(1) 2. 제일 앞/뒤의 원소 확인이 O(1) 3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 1. 배열로 구현 #include using namespace std; const int MX = 1000005; int dat[2*MX+1]; int head = MX, tail = MX; void push_front(int x){ dat[--head] = x; } void push_back(int x){ dat[tail++] = x; } void pop_front(){ head++; } void pop_back(){ tail--.. 2022. 8. 13.
[실전 알고리즘] 큐 정의와 성질 큐: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 큐의 성질 1. 원소의 추가와 제거가 모두 O(1) 2. 제일 상단의 원소 확인이 O(1) 3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 1. 직접 구현 #include using namespace std; const int MX = 1000005; int dat[MX]; int head = 0, tail = 0; void push(int x){ dat[tail++] = x; } void pop(){ head++; } int front(){ return dat[head]; } int back(){ return dat[tail-1]; } void test(){ push(10); push(20); push.. 2022. 8. 12.
[실전 알고리즘] 스택 정의와 성질 스택: 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 스택의 성질 1. 원소의 추가와 제거가 모두 O(1) 2. 제일 상단의 원소 확인이 O(1) 3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 1. 코드로 직접 구현 #include using namespace std; const int MX = 1000005; int dat[MX]; int pos = 0; void push(int x){ dat[pos++] = x; } void pop(){ pos--; } int top(){ return dat[pos-1]; } void test(){ push(5); push(4); push(3); cout 2022. 8. 11.
[실전 알고리즘] 연결 리스트 정의와 성질 연결 리스트: 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결리스트의 성질 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요 2. 임의의 위치에 원소를 추가하거나 임의 위치의 원소 제거가 O(1) 3. 원소들이 메모리상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 쉬움 배열 vs 연결리스트 기능과 구현 STL의 List가 이중 연결 리스트 STL List 예시 #include using namespace std; int main(void) { list L = {1,2}; // 1 2 list::iterator t = L.begin(); // t는 1을 가리키는 중 L.push_front(10); // 10 1 2 cout 2022. 8. 10.

티스토리툴바