알고리즘
-
[백준 3111] 검열알고리즘/백준 2019. 5. 11. 22:47
아직 도전하기에는 쉬운 문제는 결코 아닌 듯 했다. 2개의 Stack을 사용하여, 하나는 왼쪽부터 검사 또 다른 하나는 오른쪽부터 검사를 하여 없애고자 하는 문자열을 모두 없애는 기능을 구현하는 것인데, 필자의 소스코드에는 왼쪽과 오른쪽을 합쳐 없애야 하는 알파벳을 사라지게 하는 부분을 아직 구현을 하지 못해 contest solution을 올렸다. http://hsin.hr/2009/index.html위 사이트에 들어가면 다양한 Testcase를 제공하니반례를 찾을 때 매우 유리하다. 출처 : https://www.acmicpc.net/problem/3111 문제 김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모..
-
[백준 1182] 부분수열의 합알고리즘/백준 2019. 5. 11. 12:24
흔한 부분수열의 합 문제이다. 문제에서 제시한 값과 일치하는 경우의 수를 출력하는 문제이다. 크게 두가지 방법으로 풀 수 있는데1. DFS 탐색을 사용하여 각각의 경우 탐색 2. 비트마스크를 사용하여 모든 경우 탐색 click! => (비트마스크란?) 출처 : https://www.acmicpc.net/problem/1182 문제 N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지..
-
[백준 1987] 알파벳알고리즘/백준 2019. 5. 11. 12:15
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열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새..
-
[백준 2580] 스도쿠알고리즘/백준 2019. 5. 8. 22:57
스도쿠 문제이다.주어진 스도쿠를 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개) 강제로 종료시킨다. ..
-
[백준 9663] N-Queen알고리즘/백준 2019. 5. 8. 20:55
오랜만에 쉬운 문제 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이 주어졌을 때, 퀸을 놓는 방법의 수..
-
[백준 1759] 암호 만들기알고리즘/백준 2019. 4. 28. 06:31
주어진 알파벳을 정렬하고 (사전 순으로 출력하기 위해서) 갯수만큼 뽑아낸 이후에, 모음이 1개 이상 && 자음이 2개 이상인지 검사하여 정답이 가능한 모든 경우를 출력하는 코드를 작성하는 문제이다. 솔직히 분류 상으로는 "백트레킹"이지만, 그렇게 하지 않아도 충분히 풀린다. 기회가 되면 재귀함수로 구현할 예정. 개인적인 생각으로는 방법은 두가지가 떠올랐다. 1. STL의 next_permutation을 사용한 조합 참고하면 좋은 글=> (next_permutation으로 조합 만들기?) => 모음 자음 검사가 귀찮고, 정렬을 해줘야 하기 때문에 코드가 복잡해지기 쉽다.( 내가 사용한 방법이다 ) 2. 재귀 함수 => 재귀 함수와 변수들을 적절하게 사용하면, 정답 조건을 한번에 만족시킬 수 있다. (추가)..
-
[백준 9095] 1,2,3 더하기알고리즘/백준 2019. 4. 28. 05:02
쉬운 문제이다.크게 세가지 방법이 존재한다. 출처 : 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. 다이나믹 프로그래밍..
-
[백준 2251] 물통알고리즘/백준 2019. 4. 25. 19:20
물통의 갯수는 세개이고 물통의 크기는 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..