해나의 컴공생존기

이는 좀 특이하게 1차원 BFS문제이다. 2차원에서는 상하좌우로 BFS를 진행했다면 이 문제에서는 앞으로 뒤로 2배앞으로 이렇게 세개로 진행하면 된다. 이렇게 배열을 찾아가다가 동생 위치에 숫자가 써지면 답이 된다! 코드로 짜보자! 코드는 금방짰다! 1차원 배열에서 BFS는 처음이라 낯설었지만 이해하고 나니 코드가 어렵지는 않았다. #include #include using namespace std; int road[100001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, K; cin >> N >> K; road[N] =1; queue Q; Q.push(N); while (road[K] == 0) { int a= Q.front(); Q.pop(..

흠..쉬울것같았는데 은근 고민스럽다..! 일단 미로문제니까 BFS로 풀자! 먼저 진호의 위치와 불의 위치를 파악하고, 진호의 위치로부터 가장자리로 가는 최단거리를 구한다. 최단거리를 구하는 방법은 check판에 이 자리까지 오는데 걸린거리를 기록하면서 나중에 최대값을 찾으면 될 것 같다. 불이랑 만나는지는 최단거리 루트를 구하고 생각할지, 아니면 BFS하면서 같이 구할지 고민하다가 fire배열을 만들어서 BFS업데이트할때 같이 업데이트해가면서 비교해봐야겠다고 생각했다. 계속 어떤 케이스는 되고 어떤케이스는 안되고 해서 오류를 하나하나 고쳐나갔다. 근데 이제 웬만하면 모든케이스가 다 되는데... 너무 억울한데..도대체 뭐때문에 안되는지 모르겠다ㅠㅠ 일단 내 코드는 차차 고민해보는걸로하고..! 다른 아이디어..

골드단계의 문제를 스스로 풀어보는건 처음이라! 꼭 스스로 풀겠다는 다짐을 하며 문제를 보았다. 음..1부터 시작해서 그냥 0인거 BFS하면 되겠다 싶었는데 요일를 세야하니까 한 타임에 몇개가 큐에 들어왔는지 세서 그 큐가 다 소진될때마다 하루씩 늘려야겠다고 생각했다. 풀 수 있을거같은데 시간초과가 날거같은...느낌? 일단 GO 다른 방법이 생각났다. 며칠째에 내가 익었는지 내 칸에 적어놓는다면 내 다음칸은 내 칸을 보고 +1을 하면 된다!! 다이나믹한 방법이다. 야호~! 맞았따~!~! 혼자힘으로 했다는게 너무 뿌듯하다~!~! #include #include #include using namespace std; int dx[4] = {0,1,0,-1}; int dy[4] = { 1,0,-1,0 }; que..

미로찾기는 BFS에서 많이 나오는 문제이다. 미로찾기 까지는 성공했지만,,, 이 문제의 핵심인 최단경로구하는거에서 막혔다.. 가다가 이길이 아닐때 어떻게 거리를 구하지...??? 맞는일인지 아닌지 어떻게 알고 거리를 update하지?? 이 것에 대한 해결방안으로 방문했는지 체크하는 배열에 이 자리까지 오는데 걸린 거리를 저장하는걸로 하였다. 다이나믹 프로그래밍..을 이용했다고 볼 수 있을 것 같다. #include #include #include #include using namespace std; int check[100][100]; int n, m; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; string a[100]; int main() { ios::..

어떤식으로 해야할지 알 것 같으면서도...코드로 짜려고하니까 잘 생각이 안난다. BFS로 1이 있는한 계속 탐색을 하고 0 으로 둘러쌓이면 탐색을 멈추면된다. 그렇게 그림을 하나 찾아내면 그 다음은 어디에서부터 탐색해야할까? 내가 놓치고 있던게 있었다. 다 0으로 둘러쌓여있으면 Queue는 비기 때문에 BFS는 끝난다. 그럼 그 이후 탐색을 하면서 방문하지 않았고 1인 지점을 찾은 뒤 거기서 부터 다시 BFS를 진행하면된다..! BFS 문제를 처음 풀어봐서 조금의 도움을 받았다는게 너무 아쉽고 찝찝하다... 다음에는 무슨일이 있어도 꼭 내 힘으로만 풀어야지!!!!!!!! #include #include #include using namespace std; int check[500][500]; int ma..

국어를 잘못하는지 집중력이 낮은지.. 문제 이해하는데에 좀 걸렸다. 결론적으로는 괄호문제와 비슷하다고 생각했다. A괄호와 B괄호가 있다고 생각하고 풀면 어렵지 않을 것 같다. 한 줄 읽고 한글자씩 보면서 읽은 글자가 스택의 맨 위와 같으면 pop해주고 그렇지 않다면 스택에 push 해준다. 스택이 비어있다면 무조건 push해준다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N,cnt=0; cin >> N; for(int i=0;i

1. ios::sync_with_stdio(0); 2. cin.tie(0); 3. endl안쓰기 char 배열 보다 string 활용하기 for each문 활용하기

괄호문제는 스택을 쓰는 대표적인 문제이다! 문자열을 하나씩 읽어서 괄호만 스택에서 관리해야겠다. 나름 생각한대로 알고리즘을 짰는데,,, 시간초과가 났다. 먼저 간단하게 할 수 있는 것들부터 했다. 1. ios::sync_with_stdio(0); 2. cin.tie(0); 3. endl안쓰기 하지만 해결이 안됐고,, 결국 답지를 보면서 원인을 찾아봤다. 시간초과가 안나기 시작한건 char배열으로 getline을 받았는데 string으로 getline으로 받았다는 것과 이 변화에 따라서 for each문으로 바꾼것!이다. 그랬더니 틀렸습니다! 가 떴고 일단 시간초과가 안난것이 기뻤다 ㅎㅎ 그다음에 여러가지 반례를 찾아보고 열리는 괄호만 있을 때 안된다는 것을 발견했다! 그것만 고쳤더니 맞았습니다!를 만났다..

앞뒤로 넣기 간단한 deque를 이용하면 해결할 수 있을 것 같다. 1번도 연산자의 일부라고 생각해서 1번을 사용할 수 있으면 1번을 쓰고 1번을 못쓰는경우에만 2번3번을 써야한다고 생각해서 실버4치고 복잡하다고 생각하고있었다.. 아직 문제를 많이 안풀어봐서 문제해석능력이 부족한것같다. 찾을 숫자는 num이라는 배열에 정리하였고 순서판의 숫자들은 deque에 넣어관리하였다. 분명 간단하다고 생각했는데... 자꾸 실패해서 보니까 왼쪽이동 오른쪽이동의 규칙이 명확하지 않았다. 그래서 찾아야하는 숫자의 인덱스와 덱의 사이즈의 절반을 비교하여 오른쪽으로 이동할지 왼쪽으로 이동할지 결정하였다. 그랬더니 바로 원하는 결과가 나왔다! #include #include using namespace std; int num..

큐를 이용하면 구현이 어렵지 않을 것 같다! #include #include using namespace std; int main() { queue p; int N,s=0; cin >> N; for (int i = 1; i