목록 자료구조 (2)
반응형

Stargazer

[백준] 9019번 : DSLR (BFS - Queue)

접근: 최소 길이를 찾는 문제이기 때문에 BFS로 접근한다. 전략: D,S,L,R 의 연산 과정과 현재 숫자를 큐에 넣고, 한번 씩 돌린다. 이때 이전 상태를 반복하지 않기 위해서 visit 한 상태를 저장하는 배열을 만들어 사용한다. 코드: #include #include using namespace std; //DSLR int t; bool visit[10001]; void bfs(int a , int b){ queue q; q.push({a,""}); for(auto& a : visit){ a = false; } while(!q.empty()){ auto cur = q.front(); q.pop(); if(cur.first == b){ cout t; for(int test=0;test> a >> b..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2022. 7. 11. 19:16
[자료구조] 트리 후위순회 결과와 깊이 순서로 트리 구조 구하기

*자료구조 시간에 문제풀다가 배운 내용을 정리한 것입니다. 입력: 후위 순회한 결과와 그 노드의 깊이 출력: 전위 순회한 결과 예를 들어 후위 순회한 결과가 다음과 같이 주어 졌을때, 값: 5 2 8 9 10 6 7 3 4 1 깊이: 2 1 3 3 3 2 2 1 1 0 출력은 다음과 같다 1 2 5 3 6 8 9 10 7 4 트리를 그림으로 그리면 다음과 같다. #솔루션 우선 깊이의 개념을 이해해야한다. 깊이는 노드가 루트에서부터의 간선의 개수이다. 그리고 후위 순위는 가장 왼쪽 것부터 그리고 가장 깊이가 깊은 것부터 처리한다. 따라서 깊이의 변화로 이들의 관계가 무엇인지 알 수 있다. 우선 노드 1의 자식은 깊이가 1인 녀석들이다. 그래서 입력값으로부터 2 3 4 임을 알 수 있다. 여기서 더 내려가면..
Undergraudate basics(학부생 기초)/자료구조, 알고리즘 2021. 4. 23. 00:31
Prev 1 Next