JJ_blog

이분 탐색을 살짝 응용한 문제인데 Cpp 라이브러리를 찾다가 이분탐색을 쉽게 사용하는 함수가 있었다.! upper_bound 이분 탐색을 수행하여 원하는 값의 마지막 주소값을 반환 lower_bound 이분 탐색을 수행하여 원하는 값의 첫 번째 주소값을 반환 위 함수를 이용하면 이분탐색을 손쉽게 할 수 있다. #include void numberCard2(){ int N; scanf("%d",&N); vector arrN; for(int i=0;i

이분탐색을 이용하면 쉽게 해결할 수 있는 문제이다. scanf와 printf를 대신 cin, cout을 사용하면 시간초과가 날 수도 있다. #include int recursiveFindNumber(vector &arr, int target, int start, int end){ if(start > end) return 0; int mid = (start + end) /2; if( arr[mid] == target) return 1; else if (arr[mid] > target) return recursiveFindNumber(arr, target, start, mid-1); else return recursiveFindNumber(arr, target, mid+1, end); } void findN..

BFS를 이용하여 해결하는 문제인 것은 알고 있었지만 그냥 최단 거리가 아닌 벽을 하나 부순다는 상황이 주어져서 더욱더 혼란스러워졌다. 2일 동안 생각을 해보고 도전을 해봤지만 실패... 혼자서는 도저히 못 풀겠다는 생각이 들어 인터넷 블로그의 힘을 살짝 빌렸다..ㅠ 다른 사람들이 해결했던 방법들을 보고 이해한 후 문제를 보고 다시 풀었다..... 해결 방법 최단 거리를 측정하는 패턴은 기존 벽을 부수지 않고 이동하는 것과 동일하다. 하지만 최단거리로 가기 위해 벽을 한번 부수려면 모든 벽을 탐지한 후 벽을 부숴야 한다. 출발하자마자 벽을 부수고 가는 것이 최단 거리일 수 있지만 도착지가 벽으로 둘러 싸여 있는 경우 벽 부수는 스킬을 아껴 놓아야 한다. 해당 사례가 아래 그림이다. 출발지 0(a) 0(b..

처음에 접근을 DFS를 이용하여 토마토 집단이 몇 개인지 알아보고 최소일을 구하는 방식으로 접근했는데 BFS에 대한 이해가 부족했던 것 같다. BFS는 queue에 넣고 반복문을 통해 계산을 진행해서 출발 점이 여러 개여도 큐 안에 미리 넣기만 하면 여러 출발점에서도 동작시킬 수 있다. #include #define MAXBOXLENGTH 1001 int toM,toN; int inBoxSize[MAXBOXLENGTH][MAXBOXLENGTH]; queue tomatoQ; int tomatoMaxTime = 0; void printResult(); void toBFS(){ int dX[4] = {1,-1,0,0}; int dY[4] = {0,0,1,-1}; while(!tomatoQ.empty()){ i..

별다른 문제없이 해결했지만.. 초기화를 할 때 범위를 300이 아닌 301로 지정하여 수십 번 틀렸다..ㅠ 이차원상의 이동을 하는 문제는 이동가능한 범위를 배열로 나타내어 문제를 풀면 쉽게 풀 수 있다. 최단 거리를 찾는 문제들은 bfs를 사용하면 문제를 해결할 수 있는 것 같다. #include int testCase; int length; int finalX, finalY; //최종 도착지 int mvCount; bool knightVisited[301][301] = {false}; int knightCount[301][301]; void printLocate(); void printVisited(); void knightBFS(int x,int y){ queue knightQ; knightQ.pus..

기본적인 BFS문제만 풀다가 살짝 응용한 문제를 마주치니 정말 어렵게 느껴졌다.. 주의할 점) -1, +1, *2를 하고 탐색을 할 때 동생의 지점보다 넘어가서 뒤로 되돌아오는 경우가 더 시간이 짧게 걸리는 예제가 존재한다. □ 소스 코드 #include #define MAX 100001 #define MIN 0 bool disList[MAX] = {false}; int seekCnt = 0; int suN, broK; void hidebfs(){ queue disQ; disQ.push(make_pair(suN,0)); int subin = disQ.front().first; int time = disQ.front().second; disList[subin] = true; while(!disQ.empty..