실전 알고리즘 (3) 썸네일형 리스트형 실전 알고리즘 -0x08, 0x09 0x08강 스택 괄호 응용 주요 알고리즘 스택 괄호 응용 주요 알고리즘string 입력 for(auto c:a) //입력받은 string을 하나씩 접근if (, { ,[ : push else if ) :s.empty() || s.top()≠ ‘(’ : is_Valid , false 아니면 popelse if },] : 경우도 동일 스택이 비어있는지 확인하고 스택의 top 값이 pop 하는 조건과 같지 않은지 확인if (!empty) : isValid false if (isValid) : cout “YES” else “NO”3986번 코드 🚫getline과 cin의 확실한 차이를 알아야할 것 같음동일한 코드에서 cin으로 쓰면 정답 , 아니면 오답이었음 틀린 코드#include #include usin.. 실전 알고리즘 -0x0A, 0x0B DFSDFS 정의Depth First Search: 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 💡깊이 우선 알고리즘 vs 너비 우선 알고리즘 (BFS)BFS 과정에서 큐가 스택으로 바뀐 것 뿐 !!시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번 진행해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입스택이 빌 때까지 2번 반복모든 칸이 스택에 한 번씩 들어가므로 시간 복잡도는 칸이 N개일때 O(n)실수 주의할 부분 (bfs 이어서)시작점 방문 표시 잊지않기시작점 방문 표시 후에 스택에 넣어야한다.스택에 넣고자하는 원소가 범위에 벗어나면 컴파일 .. 실전 알고리즘 -0x06,0x07 Queue정의와 성질스택과 달리 먼저 들어간 원소는 먼저 나오기! FIFO (First In First Out)시간 복잡도원소의 추가 : O(1)원소의 제거: O(1)제일 앞(front), 제일 뒤 (rear)의 원소 확인 : O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다배열 이용 구현const int MX= 100005;int dat[MX];int head = 0; tail= 0;원소가 들어가있는 자리: dat[head]부터 dat[tail]까지큐의 크기 : tail - head배열이 존재한다고 할 때 처음엔 head, tail이 0을 가리키고 있으면서 add 할 경우에는 tail이 +1 , 값을 빼고싶을 때는 Head를 +1하면된다. 이 경우 원소를 계속해서 삽입 삭제 .. 이전 1 다음
