dev.notes

풀이문제를 제대로 안읽어서 순서대로 방문하기 문제인데, 순서대로 방문하지 않고 풀어서 틀렸습니다.. 처음 생각했을 때는 n=4이므로 전체 가능한 칸의 수는 16이 되고, DFS로 백트래킹 할 경우, 맥시멈 4 * 3^15 재귀 호출되고, 각 재귀 호출에서 4방향 탐색을 위해 for문을 도니까 4 * 3^15 * 4 ~= 2.3억이 나와서 시간 안에 부족하지 않나 생각했습니다. n이 작아서 예시를 들어서 해보니, 대부분 각 칸에서 다음으로 진행 가능한 경우가 3가지가 되지 않고 pruning 되어서 통과 될 것이라 판단하였습니다. 또 BFS로 풀이한다면, 풀이가 조금 더 복잡해질 것이라고 판단했습니다. 현재까지 이동한 경로에 따라, 다음 이동 할 수 있는 칸이 달라지기 때문입니다. 위 부분을 유의하여 순서..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에 bfs로 풀었는데 dfs로 푸는 것이 시간 복잡도 측면에서 유리한 것 같아서 차이를 정리하려고 합니다. 처음 한 풀이 (bfs) #include #include #include int dx[] = {-1, 0, 0, 1}; int dy[] = {0, -1, 1, 0}; bool vis[101][101]; using namespace std; // 격자의 각 칸에는 X 또는 1~9사이 자연..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 풀이 시간 복잡도를 계산하면 모든 점의 좌표에서 5가지 테트로미노의 회전과 대칭을 고려한 경우의 수를 모두 계산하므로 대략 n*m*5(5가지 테트로미노)*10(회전과 대칭을 고려했을 때 가능한 경우가 대략 10개 정도라고 가정)*4(4개의 정사각형) 정도가 된다. 즉 상한을 구하면 500 * 500 * 5 * 10 * 4 = 50,000,000으로 모든 경우를 2초안에 여유롭게 계산이 가능하..