본문 바로가기

전체보기272

[백준 1182] 부분수열의 합 흔한 부분수열의 합 문제이다. 문제에서 제시한 값과 일치하는 경우의 수를 출력하는 문제이다. 크게 두가지 방법으로 풀 수 있는데1. DFS 탐색을 사용하여 각각의 경우 탐색 2. 비트마스크를 사용하여 모든 경우 탐색 click! => (비트마스크란?) 출처 : https://www.acmicpc.net/problem/1182 문제 N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지.. 2019. 5. 11.
[백준 1987] 알파벳 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열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새.. 2019. 5. 11.
[백준 2580] 스도쿠 스도쿠 문제이다.주어진 스도쿠를 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개) 강제로 종료시킨다. .. 2019. 5. 8.
[백준 9663] N-Queen 오랜만에 쉬운 문제 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이 주어졌을 때, 퀸을 놓는 방법의 수.. 2019. 5. 8.
[백준 1759] 암호 만들기 주어진 알파벳을 정렬하고 (사전 순으로 출력하기 위해서) 갯수만큼 뽑아낸 이후에, 모음이 1개 이상 && 자음이 2개 이상인지 검사하여 정답이 가능한 모든 경우를 출력하는 코드를 작성하는 문제이다. 솔직히 분류 상으로는 "백트레킹"이지만, 그렇게 하지 않아도 충분히 풀린다. 기회가 되면 재귀함수로 구현할 예정. 개인적인 생각으로는 방법은 두가지가 떠올랐다. 1. STL의 next_permutation을 사용한 조합 참고하면 좋은 글=> (next_permutation으로 조합 만들기?) => 모음 자음 검사가 귀찮고, 정렬을 해줘야 하기 때문에 코드가 복잡해지기 쉽다.( 내가 사용한 방법이다 ) 2. 재귀 함수 => 재귀 함수와 변수들을 적절하게 사용하면, 정답 조건을 한번에 만족시킬 수 있다. (추가).. 2019. 4. 28.
[백준 9095] 1,2,3 더하기 쉬운 문제이다.크게 세가지 방법이 존재한다. 출처 : 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. 다이나믹 프로그래밍.. 2019. 4. 28.

티스토리툴바