71. 송아지 찾기
vector<int> ch(10001,0);
int d[3] ={1,-1,5};
queue<int> Q;
int main(){
freopen("input.txt","rt",stdin);
int s, e;
cin>>s>>e;
Q.push(s);
ch[s]=0;
int x, p;
while(!Q.empty()){
x = Q.front();
Q.pop();
for(int i=0; i<3; i++){
p = x + d[i];
if(p==e){
cout<<ch[x] + 1;
return 0;
}
else if(ch[p] == 0){
ch[p] = ch[x] + 1;
Q.push(p);
}
}
}
return 0;
}BFS를 이용해 최소 횟수를 탐색하는 문제였다.
처음 생각한 방법은 남은 거리를 5로 나누고 그 몫을 이용한 후에 나머지를 분류해서 각각의 답을 설정해놓는 것이었는데, 이렇게 했을 때 문제는 현수가 앞에 있을 때의 케이스를 또 나누어야한다는 것이었다.
BFS를 이용해 풀 때 처음에는 수가 커지면 time limit 오류가 나왔는데, 나는 일단 관련 수를 다 Q에 넣고 해당 위치에 갔을 때 ch[Q[ft]] 가 0인지 확인하고 해당 수에 반복문으로 가지를 뻗는 형식으로 코드를 작성했다.
이 방법이 아니라 애초에 for문으로 가지를 뻗을 때 해당 수가 송아지 위치와 같은지 확인 + 아직 해당 수가 나온적이 없는지를 확인하여 코드를 짜면 문제가 해결됐다.
결국 확인하고 Q에 넣느냐, 일단 넣고 나중에 확인하느냐 차이였는데, 자료수가 커지면 커질수록 이 둘의 효율성 차이가 분명해지는 것 같다.
72. 공주 구하기(큐 자료구조 이용)
int main(){
//freopen("input.txt","rt",stdin);
queue<int> prince;
int n, k;
cin>>n>>k;
for(int i=1; i<=n; i++){
prince.push(i);
}
int tmp = 1;
while(prince.size()>1){
int x = prince.front();
if(tmp==k){
tmp=1;
}
else{
tmp++;
prince.push(x);
}
prince.pop();
}
cout<<prince.front();
return 0;
}45번에서 풀었던 문제인데, 이번에는 큐를 이용해 푸는 문제였다.
45번을 풀 때 푼 방법을 확인해보니 배열자체를 돌면서 k번째에 있는 수를 0으로 조정하거나, 나같은 경우는 erase함수를 이용해 제거했는데, 이 방법과 비교해보면 큐를 이용하는 것이 훨신 직관적이고 효율성에서도 뛰어날 것 같다.
큐를 이용하면 가장 먼저 들어갔던 수를 다루게 되므로 맨 앞에 있는 수를 pop, push를 이용해 맨 뒤로 보내고 k번째에 있는 수는 push를 실행하지 않음으로써 마지막에 남는 수를 구할 수 있다.
73, 74 최대,최소 힙
최대힙과 최소힙에 대해 배웠다.
최대힙의 경우는 이진트리로 부모노드가 자식노드보다 크도록 값이 저장되는 자료구조이다.
priority_queue<int> pQ; //선언
pQ.top() // 부모노드 값을 호출
pQ.pop() // 부모노드값을 제거
pQ.push() // 큐에 값을 대입(자동으로 정렬된다)반대로 최소힙을 구현하는 방법은 값을 넣을 때 부호를 - 로 바꿔주면 된다. 그리고 꺼낼 때 다시 -를 곱해주면 최솟값이 부모노드에 존재하도록 할 수 있다.
