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;..
Baekjoon Review
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]의 값이 일치하여 충돌하는 것..
https://www.acmicpc.net/problem/1918 이 문제는 스택을 사용하면 해결할 수 있다.알고리즘은 아래와 같다.1. 문자열을 순차적으로 탐색한다.2. 여는 괄호를 만나면 스택에 push3. 곱하기나 나누기를 만나면 스택의 top이 곱하기나 나누기일 경우 스택에서 빼서 문자열에 누적4. 더하기나 빼기를 만나면 스택의 top을 빼서 문자열에 누적. 이때 여는 괄호를 만나면 스택에서 빼는 작업 종료5. 닫는 괄호를 만나면 스택의 top을 빼서 문자열에 누적. 이때 여는 괄호를 만나면 스택에서 빼는 작업 종료 #include #include #include using namespace std;string infix;string postfix;int main(){ ios::sync_w..
https://www.acmicpc.net/problem/2206 이 문제는 BFS를 사용하면 된다.시작 위치는 1, 1부터로 나와있지만 배열 사용의 편의 상 0,0을 시작위치로 결정하였다. 이 문제의 BFS의 방문 표시는 3차원 배열로 표시해야한다.벽을 부수고 이동하는 경우와 부수지 않고 이동하는 경우가 존재하는데벽을 1번 부시면 다음번에 벽을 만났을 때 부술 수 없기 때문이다.// [row][column][1] == 벽을 부수지 않은 상태에서의 해당 칸에 도착하는 데에 이동한 칸의 개수 // [row][column][0] == 벽을 부순 상태에서의 해당 칸에 도착하는 데에 이동한 칸의 개수 따라서 다음 칸이 벽이고 부술 수 있을 때면 -벽을 부수었기 때문에 큐에 다음 칸의 좌표와 0을 넣어주고, -..
https://www.acmicpc.net/problem/13549 이 문제는 BFS를 통해 해결할 수 있다.BFS를 통해 N에서 K까지 가는 경로 중 최소 값을 구해 출력하는 것이 전부인 문제다.이때 방문 표시는 이동 후 다음 경로를 탐색하기 전 표시해야한다는 것이다.이유는 탐색할 수 있는 경로는 총 3가지인데 이동 전 표시하게 되면, 3가지의 경로를 모두 이동해볼 수 없기 때문이다. #include #include using namespace std;int N, K;int answer = 987654321;bool visited[100001];void bfs(){ queue>q; q.push({N,0}); while(!q.empty()){ int now = q.front(..
https://www.acmicpc.net/problem/14500 테트로미노에 존재하는 블록들은 모두 4칸인 것을 알 수 있다.ㅗ모양을 제외하면, 모든 블록은 depth가 4인 DFS로 구할 수 있다.따라서 ㅗ모양은 shapeN()함수로 구하고 나머지 블록은 DFS로 구할 수 있다는 것을 알 수 있다. dfs의 구현은, 매번 한 칸에 대해 dfs를 시작할 때마다 visited배열을 초기화하는 것이 아닌, dfs의 특징을 살려 다음 뎁스로 넘어가기 전 visited[nextR][nextC]를 체크하고, 다시 돌아올 때 visited[nextR][nextC]를 해제하는 방법을 사용할 수 있다. 뎁스가 깊어질 때마다 방문한 칸은 체크해야 하지만, 하나의 테트로미노(한 번의 뎁스4까지 탐색)이 끝나면 다시 방..
https://www.acmicpc.net/problem/30804 탕후루를 끼울 때 순차적을 끼울 수 있다고 생각하고, 다른 종류의 과일이 2보다 클 경우 앞에서 부터 과일을 제거하면 해결할 수 있다.따라서 1 과일 값을 입력 받은 후 cnt배열에 값이 0인지 검사(처음 끼우는 과일인지 검사) 한 후 cnt배열의 값을 1증가시킨다.이 후 처음 끼우는 과일인 경우 other 변수를 1 증가(과일 종류를 세는 변수)시킨다. other 변수의 값이 2보다 큰 경우 queue에서 과일 하나를 빼고 cnt 배열에서 값을 1 감소시킨다. (과일을 제거했기 때문)만약 제거한 과일이 탕후루 꼬치에 존재하지 않는 과일(cnt배열의 값이 0)인 경우 other 변수를 1 감소시킨다. 큐의 과일 개수를 구하고 정답 변수..
