해나의 컴공생존기

문제 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며..

https://www.acmicpc.net/problem/1874 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 ..

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

미로찾기는 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..

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

정의해준 재귀함수를 분석해보겠다. 인자로 a,b,c 가 들어오고 이 값에 따라 재귀호출을 하는 것 같다. a,b,c 중 하나라도 0이하가 되면 1을 리턴한다. a,b,c 중 하나라도 20이상이 되면 a,b,c에 20을 넣고 재귀호출한다. a> b >> c; if (a == -1&&b==-1&&c==-1) break; //종료조건 cout

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다. 의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면 n-1과 n-2를 인자로 재귀호출하여 더해준다. 만약 6이 들어온다면 f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) ) → ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 ) → ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 ) → ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8 동적프로그래밍 의사코드를 보면 인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고 나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다. 하지만 '..

문제는 그렇게 어렵다고 생각하지 않았지만 리스트를 정의하지 않고 선언한 뒤 리스트의 처음을 가르키는 iterator를 생성하면 어디를 가르킬까?에 대한 의문때문에 내가 답을 납득하는데에 시간이 걸렸다. 결론은 null을 가르킨다는 것이었다. 나는 list L; 이렇게 선언을 했지만 답을 보니 list L={ }; 로 선언을 했다. 나처럼 해도 오답은 아니지만 답 코드를 보니 null이 들어있는 한칸이 만들어지는 것이 아닐까? 하는 발상이 떠올랐다. 그렇게 계산해보고 예제를 넣고 풀어보니 논리가 맞았다. 앞으로 그렇게 생각해야지... #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int fre; ci..

한번 동적할당을 하고 이중 포문을 이용해서 코드를 짰는데 시간초과가 났다.. 그래서 두번 공적할당을 하고 합을 구하는 과정에서 시간복잡도를 줄였다.. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int num ; int* arr; cin >> num; arr = new int[num]; for (int i = 0; i > arr[i]; int sum=10,fre=0; cin >> sum; int* N = new int[sum+1]; for (int i = 0; i < sum+1; i++) N[i] = 0; for (int i = 0; i < num; ..