알고리즘/문제풀이 - 백준

백준 2798 블랙잭

문제 : https://www.acmicpc.net/problem/2798 서론 재귀를 활용한 브루트포스 아이디어 주어진 수의 첫번째 숫자부터 마지막 숫자까지 재귀함수를 이용하여 완전탐색을 한다. recursive(O/X){ recursive(O); recursive(x); } 5 6 7 8 9 O O O X X O O X O X O O X X O O X O O X O X O X O O X X O O X O O O X X O O X O X O X O O X X O O O 탐색을 하던 중 O의 개수가 3개가 나오면 O를 모두 더해주고 M과 가장 가까운지 확인 후 리턴, 탐색깊이가 M과 같아지면 무한히 재귀에 빠지는것을 막기 위해 리턴 구현 //c++ #include #include using namespa..

2019. 7. 6. 15:15
알고리즘/문제풀이 - 백준

백준 11729 하노이 탑 이동 순서

문제 : https://www.acmicpc.net/problem/11729 서론 재귀가 있는건 알겠는데 정확하게 보이질 않아서 위키를 참고했다. 참고 : https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91 풀이과정 하노이의 탑 게임을 하면서 n이 1부터 4까지의 답을 적어보았다. n이 2일때의 답이 n이 4일때의 최하단과 동일한게 보이긴 하는데 다른 별다른 규칙성이 보이질 않는다. 그런데 게임을 하다보니 n이 3일때의 게임 진행 도중 n이 2일때를 만날 수 있음을 확인했다. 왼쪽 기둥을 시, 중간 기둥을 빈, 오른쪽기둥을 목이라고 하고(시작, 빈곳, 목표) 게임 도중 발견한 규칙을 생각하며 표1의 숫자들을 한글로 바꾼..

2019. 7. 6. 12:56
알고리즘/문제풀이 - 백준

백준 2447 별 찍기 - 10

문제 : https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 서론 스스로 해결하지 못한 문제. 출력결과를 배열에 넣는다는 생각을 못했고, 바로 출력하려고 시도하다 못풀었다. 그런데 바로 출력해서 푸신 분들도 있다. 존경스럽다. 아래 코드는 배열에 넣는 방식으로 풀었다. 풀이 n이 3일때의 출력결과는 다음과 같다. 3*3 행렬에서 정중앙(1행 1열)만 공백처리 한다. * * * * * * * * n이 9일때의 출력결과는..

2019. 7. 5. 19:47
알고리즘/문제풀이 - 백준

백준 2562 최댓값

문제 : https://www.acmicpc.net/problem/2562 서론 c++의 max_element를 활용해본 문제 아이디어 9개의 수를 벡터에 넣고 최대값은 배열이나 벡터의 최대값을 리턴해주는 max_element를 이용한다. max_element는 최대값의 주소를 리턴하므로 포인터 연산자를 붙인다. 최대값의 번지수는 max_element로 얻어진 최대값의 벡터주소에서 벡터의 시작주소를 빼고 +1 하면 얻을 수 있다. 구현 /c++ #include #include #include using namespace std; vectorv; int main() { int n; n = 9; for (int i = 0; i > tmp; v.push_back(..

2019. 7. 5. 15:16
알고리즘/문제풀이 - 백준

백준 9663 N-Queen

문제 : https://www.acmicpc.net/problem/9663 서론 백트래킹을 이해하기 위해 풀어본 문제 퀸이 위치할 수 있는 조건을 만드는것, 퀸이 놓일때 이전에 놓인 퀸들을 모두 고려해야하는것, 재귀를 시작할 위치를 지정하는것을 생각하는데 꽤나 오래걸렸다. 걸린시간대비 결과물이 짧은 코드이지만 간결하게 나온것 같아서 만족한다. 아이디어 & 풀이과정 DFS 조건을 만족하려면 각 행에는 하나의 퀸만 둘 수 있다. DFS를 이용하여 1행부터 n행까지 각 행마다 하나씩 퀸을 두면서 가능한 모든 경우의 수를 탐색한다. set A 1행 1열에 퀸을 하나 놓고 행을 증가시켜 모든 열을 탐색한다. 2행 1열에 퀸을 놓아보지만 조건을 만족하지 않으므로 리턴한다. 2행 2열도 안되므로 리턴 2행 3열은 가..

2019. 6. 28. 18:17
알고리즘/문제풀이 - 백준

백준 1920 수 찾기

문제 : https://www.acmicpc.net/problem/1920 서론 이진탐색 문제 구현 //c++ #pragma warning (disable : 4996) #include #include #include using namespace std; int a[100001]; int n, m; int bs(int target) { int start = 0; int end = n - 1; while (start > n; for (int i = 0; i > m; for (int i = 0; i < m; i++) { int target; scanf("%d", &target); printf("%d\n", bs..

2019. 6. 27. 21:15