로재의 개발 일기 로재의 개발 일기

DFS 탐색을 이용해서 해결한 문제이다. char board[20][20]; // 각각의 알파벳이 들어감 bool check[20][20]; // 방문을 했는지 체크 vector point; // 현재 위치에서 이동할 수 있는 범위 계산 (상하좌우) vector visit; // 이미 지난 알파벳만 push ! 주의할 점 ! 이동하지 못할 경우라도 현재 있는 위치도 이동이가능하므로 1을 출력해준다. 출처 : https://www.acmicpc.net/problem/1987 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새..

스도쿠 문제이다.주어진 스도쿠를 3가지 조건을 만족하여다양한 경우의 수 중에서 하나만 출력하면 된다. 조건1 : 각각의 가로 줄에는 1 ~ 9 숫자 하나씩만 가능하다.조건2 : 각각의 세로 줄에는 1 ~ 9 숫자 하나씩만 가능하다.조건3 : 작은 3*3 사각형에는 1 ~ 9 숫자 하나씩만 가능하다. 나의 경우에는 bool check1, 2, 3을 사용하여 구현하였으며int sudoku[9][9]; // 기존의 스도쿠 배열vector list; // 비어있는 스도쿠 배열 list의 x와 y를 활용하여, 1부터 9까지 순회시켜조건 1,2,3에 부합할 경우 다음 깊이로 진행한다. (DFS 탐색) 모든 깊이를 탐색할 시다양한 경우의 수가 나오기 때문에(문제에서 제시한 답은 경우의 수 1개) 강제로 종료시킨다. ..

오랜만에 쉬운 문제 N-Queen 문제이다. 퀸이 서로 공격하지 못하도록 위치할 수 있는 모든 경우의 수를 구하는 문제이다. 1. 퀸의 위치를 나타는 배열 col[]을 사용한다. col[x] = y // x행 y열에 퀸이 위치한다는 표시 2. 퀸이 서로 공격할 수 있는 경우 (예외처리를 해주어야 함) col[i] == col[cur] // 같은 열에 존재하는 경우(i - cur) == abs(col[i] - col[cur]) // (행 - 행) == (열 - 열)*(출처 : 위키피디아) 출처 : https://www.acmicpc.net/problem/9663 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수..

주어진 알파벳을 정렬하고 (사전 순으로 출력하기 위해서) 갯수만큼 뽑아낸 이후에, 모음이 1개 이상 && 자음이 2개 이상인지 검사하여 정답이 가능한 모든 경우를 출력하는 코드를 작성하는 문제이다. 솔직히 분류 상으로는 "백트레킹"이지만, 그렇게 하지 않아도 충분히 풀린다. 기회가 되면 재귀함수로 구현할 예정. 개인적인 생각으로는 방법은 두가지가 떠올랐다. 1. STL의 next_permutation을 사용한 조합 참고하면 좋은 글=> (next_permutation으로 조합 만들기?) => 모음 자음 검사가 귀찮고, 정렬을 해줘야 하기 때문에 코드가 복잡해지기 쉽다.( 내가 사용한 방법이다 ) 2. 재귀 함수 => 재귀 함수와 변수들을 적절하게 사용하면, 정답 조건을 한번에 만족시킬 수 있다. (추가)..

쉬운 문제이다.크게 세가지 방법이 존재한다. 출처 : https://www.acmicpc.net/problem/9095 문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.예제 입력 13 4 7 10예제 출력 17 44 274 1. 다이나믹 프로그래밍..

물통의 갯수는 세개이고 물통의 크기는 1부터 200까지이다. 이때 물통의 갯수가 세개이기 때문에 모든 경우를 고려한 BFS 알고리즘을 사용하여 A 물통이 비어있을 때, C의 물통에 담겨 있는 물의 양을 출력하면 된다. 모든 경우라고 해봤자. 총 6가지이다1. A -> B 2. A -> C3. B -> A4. B -> C5. C -> A6. C -> B ( 각각의 모든 경우는, 옮기려는 물들이 옮기려는 곳의 최대 용량보다 많은지 검사를 해야한다.)음수가 나오므로 불 필요한 연산을 하지 않기 위해서 1. 임의로 만든 water 구조를 사용하여, 저장 및 사용이 편리하도록 Queue을 사용하였다. 2. 방문 여부를 확인 하기 위해서 bool visit[][][]를 작성하였다. 출처 : https://www.a..

시간 초과를 넘기지 않도록 주의하여 구현해야 하는 BFS 문제이다. 주어진 시간이 짧지는 않지만 (6초) queue 식으로 구현을 하면, 문제 특성상 string이 복사가 일어난다. 따라서 어마어마한 시간이 지연이 될 수 있다. (저는 그랬어요 ㅠ) 시간을 줄이기 위해서, 가급적 if문과 배열을 사용하였고, vector 컨테이너를 사용하여 탐색을 진행 하였다. 주의해야 할 점은, 시작 루트(from)에서 도착 루트(to)로 향할 때 순서대로 필요한 명령어를 출력해야 하기 때문에 시간 복잡도 상, 시작 -> 도착 순으로 하나씩 검색을 하면 Big-O 표기법으로 제곱 혹은 그 이상이다. ( 애초에 BFS 접근을 하기 때문에 도착하기 전에는 어디가 최단거리인지 알 수가 없다) ( 즉, 미리 저장이 불가능하다 ..

정답률이 높았지만, 다른 정답률이 높은 문제들에 비해서 긴 소스코드를 작성해야 하는 문제였습니다. BFS와 에라토스테네스의 체의 개념을 확실하게 알고 있어야 풀 수 있는 문제입니다. ( BFS로 푸는 이유 => 모든 간선의 비용이 1이다 )저 같은 경우는, 하나의 큐와 1부터 10000까지 배열을 2개 만들어 queue q는 BFS 접근을 하기 위하여 사용하였고 int visit [10000] 배열은 방문 여부를 확인하는 배열이며, 값은 소수 변환에 필요한 횟수를 가지게 구현하고 bool c [10000] 배열은 소수인지 아닌지 확인하는 배열을 구현하였습니다. 추가적으로는 배열이 아닌 struct { int a, bool b} 혹은 vector c 컨테이너를 사용하여 충분히 풀 수 있는 문제입니다. 출처..