https://www.acmicpc.net/problem/2447 별은 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태로 출력해야한다.이는 가운데인 경우 별 패턴을 출력하지 않는 것이고 가운데가 아닌 경우 별 패턴을 출력하면 된다. 별을 출력할 떄는 가운데인 경우 공백을 출력하고 아닌 경우 별을 출력한다.출력을 위해 area에 맞게 별과 공백을 배열에 삽입한다. 별을 그리기 위해 9개로 영역을 나눈다.영역을 9개로 나누기 위해 area/3을 진행하고 시작 위치와 끝 위치를 알려준다.가운데를 나타내기 위해 가운데에 해당하는 경우 pattern 값을 false를 준다. #include using namespace std;int N;char star[6600][6600];void ..
분류 전체보기
https://www.acmicpc.net/problem/1992 원래 존재하는 image의 값이 다를 경우 4등분 해야 함을 알 수 있다.이는 분할 정복을 사용해 문제를 해결해야 함을 알 수 있다. 자를 때는 왼쪽 위, 오른 쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 잘라야한다.등분은 4등분이기 때문에 area/2를 해준다.quadTree(y, x, area/2);quadTree(y, x + area/2, area/2);quadTree(y + area/2, x, area/2);quadTree(y + area/2, x + area/2, area/2); 배열을 순회하여 같은 문자가 아닐 시에 자르고 같으면 값을 출력해준다. #include using namespace std;int N;char image[6..
https://www.acmicpc.net/problem/1780 종이를 자를 때는 같은 크기의 종이를 9등분 한다.이는 분할 정복을 사용하여 문제를 해결해야 함을 알 수 있다. 종이를 자를 때 N = 9인 경우 크기 3인 종이가 9개 존재하게된다.따라서 원래 종이의 크기가 n인 경우 다음 종이는 n/3이 된다는 것을 알 수 있다. 종이를 자를지 선택할 때는 paper[y][x]의 값이 paper[y부터 y + size][x부터 x + size 값] 에 있는 값이 다를 경우 자른다. 자르지 않는 경우 paper[y][x]에 존재하는 값을 count하면 된다. #include using namespace std;int N;int paper[2200][2200];int onePaper = 0;int zero..
https://www.acmicpc.net/problem/11444 초기 점화식을 사용해 DP로 문제를 해결하고자 하였다.하지만, 문제 조건 중 N의 최대 값이 1,000,000,000,000,000,000인 것을 알게 되었으며실제로 DP로 문제 접근 시 시간 초과가 발생 하였다. 따라서 이 문제는 DP가 아닌 정복 분할 형태로 해결해야한다. 피보나치의 점화식은 다음과 같다.FIBO[N + 2] = FIBO[N-1] + FIBO[N] 위 점화식을 사용해서 2로 분할하면 아래와 같은 수식을 새울 수 있다.F[n] = F[n-1] + F[n-2]F[n] = F[n-1] + F[n-2] + F[n-2] + F[n-3] = 3F[n-2] + 2F[n-3]F[n] = 5F[n-3] + 3F[n-4]F[n] = 8..
다익스트라 알고리즘?그래프에서 최소 비용을 구하는 경우 사용되는 알고리즘최소 비용 중, 주어진 두 노드(시작 노드, 도착 노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.동작 원리시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.방문한 정점들과 연결되어 있는 정점들 중, 비용이 적게드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.2번 과정으로 갱신될 수 있는 정점들의 거리를 갱신시켜준다.2번 과정과 3번 과정을 반복한다.시작노드를 0번 노드로 가정dist 배열이 초기 INF로 초기화되어 있다고 생각한다.1번 과정에 의해 0번 노드로 갈 수 있는 1번노드와 4번 노드, 5번 노드의 거리를 갱신0번 노드를 방문한 노..
https://www.acmicpc.net/problem/1759 백트레킹을 사용해서 해결할 수 있는 문제이다.암호에 사용되는 알파뱃은 반드시 모음 1개 이상과 자음 2개 이상이 필요하다.따라서 depth가 L일 때 모음과 자음 수를 비교한 후 answer를 출력할 수 있도록 한다. #include #include using namespace std;int L, C;char alpha[16];char answer[16];int visited[16];void dfs(int idx, int moCnt, int jaCnt, int depth){ if(depth == L && moCnt >= 1 && jaCnt >= 2){ for(int i = 0;i>L>>C; for(int i = 0;..
https://www.acmicpc.net/problem/14889 백트레킹을 사용하는 문제이다.idx와 cnt라는 매개변수를 통해 백트레킹을 구현하였다.idx를 통해 다음 팀원을 구하는 과정에서 이전에 선택한 팀원을 고를지 선택하는 과정이 생기지 않도록 하였다. (반복횟수를 적게함)cnt 변수를 통해 depth를 조절하였다.팀원을 선택할 때는 N/2명을 선택하면 모든 팀에 팀원을 배치하였다고 볼 수 있다.start팀이 N/2명을 골랐다면 link팀은 start팀이 고른 이외의 사람이 들어가기 때문이다. #include #include #include using namespace std;int N;int S[21][21];bool visited[21];int answer = 987654321;// 0 1..
https://www.acmicpc.net/problem/9663 이 문제는 백트레킹을 사용하면 해결할 수 있다. 백트레킹을 사용하는 이유는 다음과 같다.1. 한개의 줄에 퀸을 배치하기 위해서는 대각과 위를 비교해야한다.2. 만약 대각 성분이나 위를 비교했을 때 충돌할 경우 이전 행으로 이동해서 다른 위치에 퀸을 배치해야함 이 문제의 백트레킹을 사용하는 이유를 살펴보면 각 행에는 퀸이 1개만 존재한다는 것을 알 수 있다.따라서 col 배열을 통해 각 행에 위치한 퀸의 위치를 저장한다.- 퀸이 (0, 3)에 위치한다면 col[0] = 3 퀸을 배치하고, 배치한 퀸이 충돌하는지 검사하는 방법1. col[0] = 1, col[1] = 1, col[2] = 1인 경우는 col[x]의 값이 일치하여 충돌하는 것..
