홍시홍의 프로그래밍

분류 dp 요구사항 주어진 맵에서 탈출 가능한 정점이 몇개인가 고르는 문제 풀이 모든 정점에 대해서 dfs 실시하면 500*500*500 이 되므로 안된다 이미 방문한 정점은 방문하지 않고 이전 결과를 활용할 수 있는 dp로 풀자는 결론은 금방 나왔다 하지만 구현이 어려웠다. 평소 메모리제이션 처럼 -1로 초기화 후, 첫 방문시 0으로 실시하고 다시 최종 값을 ref에 넣어주어야한다. 아래 코드를 참조한다. #include #include #include #include #include #include #include using namespace std; int n, m; char map[550][550]; int visit[550][550]; int ans = 0; int dr[4] = { -1,0,1..

분류 구현, 백트래킹 요구사항 제일 마지막 입력에서의 톱니 바퀴 구하기 풀이 문제의 흐름은 입력 -> 톱니 돌리기 -> 양 방향 확인하기 -> 정답 출력 입력 deque를 사용해서 시계 방향, 반시계 방향으로 돌릴 수 있도록 한다 톱니 돌리기 deque를 원형 큐로 생각해사 2번재, 6번째 위치를 좌, 우로 설정하여 양 옆과 비교한다 양 방향 확인하기 현재 톱니 바퀴 옆이 존재하는지와 다른 극성인지 확인한다 정답 출력 각 deque의 0번째 위치 값 확인 #include #include #include #include #include #include #include #include using namespace std; /* 10101111 01111101 11001110 00000010 2 3 -1 1 ..

분류 분할 정복 요구사항 1. 9칸으로 나누었을때 가장 작게 나누어지는 조각 찾기 2. 각 조간의 갯수 구하기 풀이 나는 어려운데 정답률이 상당히 높다 문제 풀이의 흐름은 검사 -> 분할으로 진행된다 검사는 현재 나눈 칸이 동일한 값으로 이루어 져있는지 검사하는 단계 분할은 동일한 값이 아니라면, 9칸으로 나누어서 다시 진행하는 것이다 분할하는 것이 힘들었다 9칸을 어떻게 나눌것인가 풀이는 직접 그려보고 index 번호 적어보니깐 어떻게 나눌지 보이기 시작했다 #include #include #include #include #include #include #include using namespace std; int map[2200][2200]; int n; int ans[3]; bool check(int..

분류 시뮬레이션 요구사항 문제에 주어진 대로 스티커를 놓을 수 있나, 없나 판단한다. 스티커를 놓을 수 있다면 붙인다. 최대 몇칸을 채울 수 있는가 출력한다. 풀이 1. 위치 정하기 - 모든 그래프의 정점에서 현재 모양의 스티커를 놓을 수 있는지 확인한다. 2. 안될 경우 회전하기 - 안될 경우 회전 시킨다 - 노트에다가 현재 스티커 모양과 회전 시킨 후 스티커 모양을 좌표로 그린 후, 구현한다. - 1~2개만 그려보면 구현할 수 있다. - temp[i][j]= map[c-j+1][i] 3. 정답 출력 #include #include #include #include #include #include using namespace std; struct go { int r; int c; int Nmap[11][..