목록Queue (4)
Seung's Learning Record
≣ 목차 트리 트리 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조로, 순환하는 길이 없는 그래프라고 말할 수 있다. 루트 노드 (root node) : 트리의 최상단 노드 리프 노드 (leaf nodes) : 트리의 최하단 노드 내부 노드 (internal nodes) : 루트와 리프 사이에 위치한 노드 부모 (parent) 노드와 자식 (child) 노드 : 정점의 바로 위 노드가 부모 노드, 바로 아래 노드가 자식 노드 (부모의 부모는 조상노드, 자식의 자식은 후손 노드) 노드의 수준 (level) : root로 부터 각각의 노드까지 도달하기 위해 거쳐야하는 간선의 수 (root = level 0) 노드의 차수 (degree) : 자식 노드의 수 트리의 높이 (..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cixZIF/btsEEGQdkz6/QftmJd6fmJWiEKdukQ8Jdk/img.png)
난이도 : 실버2 소요시간 : 1시간 9분 사용한 풀이법 : bfs,queue 풀이 과정 1. 테스트 케이스 시작 때 마다 vis[][], bc[][] 배열 0으로 초기화 2. 배추 위치 입력 들어올 때 마다 bc[][]배열 1 삽입 3. for문 돌면서 방문 이력이 없으면서 배추가 있는 곳을 만나면 bfs 실행 => 하나의 배추 군단이 끝나면 bfs종료 후, cnt++됨 4. cnt값 출력 작성 코드 #include #include #include using namespace std; queue Q; int bc[50][50]; int vis[50][50]; int t,n,m,k,x,y; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int d..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bE4SZ2/btsEmWE2ZH6/LLaG6QE0If7WnEdXrAscpk/img.png)
난이도 : 실버1 소요시간 : 1시간 28분 사용한 풀이법 : dfs,queue 풀이 과정 1. 수빈 현 위치로 부터의 거리 측정용 배열 dist[], 이동 가능 위치 체크용 큐 Q[] 생성; 2. dist[]는 -1로 초기화, Q[]에 수빈 현위치 push; 3. dist[k]에 값이 들어가기 전까지 while 루프{} 4. 현위치 확인용 변수 cur에 Q.front() 대입; 5. cur이 -1, +1,*2 일때의 상황 for문 돌리면서 bfs 진행 6. 조건 충족 시, 해당 상황의 dist 값을 dist[cur]+1로 설정; 7. while 탈출 시 dist[k]값 출력; #include #include using namespace std; queue Q; int dist[100002]; int m..
Queue 란? 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 먼저 들어간 원소가 먼저 나오게 되는 FIFO(First In First Out) 구조이다. 큐에서는 원소가 제거되는 쪽을 가장 앞인 front, 원소가 삽입되는 쪽을 가장 뒤인 rear라고 부른다. Queue 성질 원소의 추가 O(1) 원소의 제거 O(1) 맨 앞, 맨 뒤 원소 확인 O(1) 맨 앞, 맨 뒤를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 Queue 구현 스택과 마찬가지로 큐 역시 배열을 이용하여 구현하는 방법과 STL을 이용하여 구현하는 방법이 있다. 배열을 사용한 구현 스택에서의 구현 방법을 큐에 대입해보자. 원소가 삽입되면 tail이 가르키는 인덱스에 값을 넣고 tail++를 하면된..