Today I learned : BFS 개념 조금.. 경험기술 조금..
오늘 할 일
- BFS 마무리
- ~~출근하면 파일 반입 메일 보내기, 업무 분담 메신저 보내야함 ~~
- 근무시간에 바킹독 문제집 큐~BFS 뽀개기
- 오늘은 ㄹㅇ 경험기술 정리하고 세미나 지원
3:10 상담
10866 : 덱
#include <bits/stdc++.h>
using namespace std;
const int MX=50000;
int dat[MX*2+1];
int head=MX, tail=MX;
int n;
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
while(n--){
string inst;
cin>>inst;
if(inst=="push_front"){
int x;
cin>>x;
dat[--head]=x;
}
else if(inst=="push_back"){
int x;
cin>>x;
dat[tail++]=x;
}
else if(inst=="pop_front") cout<<(tail==head ? -1: dat[head++])<<'\n';
else if(inst=="pop_back") cout<<(tail==head ? -1: dat[--tail])<<'\n';
else if(inst=="size") cout<<(tail-head)<<'\n';
else if(inst=="empty") cout<<(tail==head ? 1 : 0)<<'\n';
else if(inst=="front") cout<<(tail==head ? -1 : dat[head]) <<'\n';
else cout<<(tail==head ? -1 : dat[tail-1]) <<'\n';
}
}
head, tail을 다르게 두었다가 애먹었다.
바킹독의 실전 알고리즘 : 스택의 활용(수식의 괄호 쌍)
알고리즘 설명
BFS는 Breadth First Search는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.
본디 BFS는 그래프라는 자료구조에 모든 노드를 방문하기 위해 제안된 알고리즘이다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
pair<int,int> t1=make_pair(10,13);
pair<int,int> t2={4,6};
cout<<t2.first<<' '<<t2.second<<'\n';
if(t2<t1) cout<<"t2<t1";
}
utility 헤더에 있는 pair는 두 자료형을 묶어서 다닐 수 있다. BFS는 정말 숙달되도록 잘 알아야 한다. 그 냥 외 우 는 걸 추 천 했 으 니 외우자..
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second //X,Y를 상수로
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,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0} };
bool vis[502][502];
int n=7, m=10;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int,int>> Q; //int 두 개를 페어로 넣을 수 있는 큐 선언
vis[0][0]=1; //이게 시작점 표시인듯
Q.push({0,0}); //그리고 큐에 시작점 값을 넣기
while(!Q.empty()){
pair<int,int> cur=Q.front(); Q.pop; //현재 위치는 cur, 그리고 큐에서 값 빼기
cout<<'('<<cur.X<<", "<<cur.Y<<") -> ";
for(int dir=0;dir<4;dir++){ //디렉팅
int nx=cur.X+dx[dir]; //아 3방향으로 다 돌아보는군
int ny=cur.Y+dy[dir];
if(nx<0||nx>=n||ny<0||ny>=m) continue; // 없는 위치이면 넘기고
if(vis[nx][ny]||board[nx][ny]!=1) continue; // vis에 이미 방문한 표시가 있으면 넘기고
//근데 윗줄에서 board 배열의 역할은 뭐지? -> 아 예시 그림에서 주어진 파란 칸인지 범위 확인
vis[nx][ny]=1; // 위 조건에 부합하지 않으면 얘도 vis 넣고
Q.push({nx,ny}); //큐에 넣고
}
}
}
음 어렵군. 일단 본문 글 보기 전에 내가 코드 리뷰로 주석 달아보자.
- 내가 주석 달아보고
- 본문 읽으면서 보충하기
BFS를 구현할 때 짚어야 할 부분
- 시작점에 방문했다는 표시를 남기지 않는다. -> 시작점 두 번 방문할 수도 있음
- 큐에 넣을 때 방문했다는 표시 대신 빼낼 때 방문했다는 표시를 남겼다. -> 같은 칸이 큐에 여러 번 들어갈 수 있음
- 이웃한 원소가 범위 외인지 체크를 잘못했다. -> 이건 뭐..
1926번은 직접 풀어보자
회고
마지막 출근 주의 월요일… 벌써부터 슬프다ㅜㅜ
내선번호표 만들어서 우리팀, 옆팀 돌았는데 멘토과장님 만나서 더 슬펐다ㅜ 과장님이 엄청 잘 챙겨주셨는데(왕왕..ㅜㅜ) 갑자기 오전에 인사부 대리님께 연락 와서 상담도 했다. 하면서 느낀 건 취준하면서 쉽지는 않겠지만 나에 대해 더 잘 소개하고, 솔직해지는 것이 좋다고 생각한다.
물론 취준하면서 확신이 없어 끝없이 축소되겠지만 오늘 드는 생각은 ‘주사위는 이미 던져졌다’는 생각이다. 아무리 내가 JD를 분석하고 인재상에 맞춰 자소서를 쓴들 기업에서 원하는 사람은 바로 알아본다고 생각한다. 내가 떨어진다고 못난 사람이 아니라 결이 다른 것이고, 그부분을 내가 단기간에 어떻게 해올 수 없는 부분이라 생각한다. 서류도, 면접도 이미 주사위는 던져졌단 마음으로 올해?가 될지 내년이 될지는 모르겠지만 취준을 잘 마무리하고 싶다.
사실 아직 휴학의 끈을 놓지 않았다 ㅋㅋ 고민이다.. 2학기라도 어디로 훌쩍 떠날지.. 대학생을 좀 더 즐기고픈 마음과 그래봤자 내가 얼마나 잘 즐기겠냐(?)는 마음이 공존한다.
오늘 BFS 완강 했어야 했는데 생각보다 너무 어렵다.. 그리고 인사부 면담이 생각보다 길었다. 내일은 오전에 팀플 후딱 끝내고 오후에는 코테 집중해서 끝내려고 한다.