알고리즘(71)
-
[백준/C++] 1780번 종이의 개수
문제: www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제풀이 기준점 x, y와 종이의 변의 길이 N을 매개변수로 하는 함수를 선언하여 재귀방식으로 문제를 해결했다. 기준점과 종이의 나머지 부분을 비교하여 같으면 카운트를 하고 다르면 기준점과 N를 적절하게 나누어 9개의 함수를 호출했다. (9등분) 코드 #include using namespace std; int cntm1 = 0; //-1인 종이 갯수 int cnt0 = 0; //0 종이 갯수..
2021.02.23 -
[백준/C++] 1541번 잃어버린 괄호
문제: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제풀이 문제의 분류는 그리디 알고리즘이지만 문자열 처리만으로 풀 수 있는 문제였다. 식의 '-' 연산을 만나기 전까지의 수는 계속 더해주고 '-' 연산을 만난 후 부터는 '+' 연산을 만나든 '-' 연산을 만나든 관계없이 빼주면된다. 예를 들어 10+10+10-10+10+10 은 10+10+10-(10+10+10) 즉, 10+10+10-10-10-10 이 된다. 코드 #include using n..
2021.02.22 -
[백준/C++] 1260번 DFS와 BFS
문제: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제풀이 DFS와 BFS의 구현문제이다. DFS는 재귀함수의 형식으로 구현했고 BFS는 queue를 이용하여 구현했다. 코드 #include #include using namespace std; int N,M,V; int visited[1001] = {0,}; //방문여부 int link[1001][1001] = {0,}; //간선 void init(){ //dfs후..
2021.02.21 -
[백준/C++] 11727번 2×n 타일링 2
문제: www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제풀이 DP문제이다. 이 문제의 점화식은 P[i] = 2*P[i-2] + P[i-1] 이다. 10,007로 나눈 나머지를 출력하기 때문에 배열의 크기를 10,007로 선언하였다. 코드 #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; int arr[10007] = {1, 3}; for(int i=2..
2021.02.17 -
[백준/C++] 11726번 2×n 타일링
문제: www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제풀이 DP문제이다. 경우의 수가 피보나치 수열을 이룬다. 10,007로 나눈 나머지를 출력하기 때문에 배열의 크기를 10,007로 선언하였다. 코드 #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; int arr[10007] = {1, 2}; for(int i=2; i
2021.02.17 -
[백준/C++] 9461번 파도반 수열
문제: www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제풀이 DP문제이다. 문제의 점화식 P[i] = P[i-5] + P[i-1] 주의할 점은 배열을 선언할 때 long long 형으로 선언해주어야 한다는 것이다. 처음 문제를 풀 때 int 형으로 선언하여 9%에서 계속 틀려서 헤매었다. 코드 #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T..
2021.02.17