💻 OnlineJudge/Baekjoon

[백준 / BOJ] C++ 1003 피보나치 함수

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 아~~ 주 쉽게 생각했다가 짜증만 엄청 냈던 문제.. 시간초과를 생각못하고 어떻게 풀던 시간초과가 나오고, 계속 '이렇게해서 안되면 어쩌란거야 ?'를 반복하다가 찾아보니 점화식을 이용하는 문제였다. 이럴거면 피보나치 위에 그 함수코드는 왜있었는지 이해불가.. 아무튼 피보나치 함수의 점화식은 아래와 같다. N이 0일때, return값이 0인경우 = 1, 1인경우 = 0 N이 1일때, return값이 0인경우 = 0, 1인경우 = 1 N이 2일때, return값이 0인경우 = 1, 1인..

[백준 / BOJ] C++ 2448 별찍기 - 11

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 풀이 이것저것 해보다가 결국 끼워맞추기를 시작한 문제.. 반복되는 문양을 vector 배열에 넣어준다. 이후에는 코드에서 알 수 있듯.. 끼워맞춰서 출력만 되도록하였다. 이해를 돕기위해 아래 이미지를 참조하자. 반복되기 이전 공백이 3개씩 들어가며, 그 공백의 갯수는 2^n개로 알 수가 있다. 입력값이 3 * 2^k 이기 때문에 유추할 수 있다. 앞에 공백 " "을 채워주고 별 그린 이후 이후 공백 " "을 채워준다. 아래 코드를 참조하자. Code..

[백준 / BOJ] C++ 2407 조합

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 풀이 조합 공식을 이용 - (nCm = n-1Cm-1 + n-1Cm)을 이용하여 값을 구한다. long long을 사용해도 자료형 허용 범위를 넘어가는 미친 문제이다. 조합 공식쓰고 그냥 했다가 왜 안되지? 하며 꽤나 헤매었던 문제... Visual studio 2022 C++ 17 개발환경으로 long long으로 빌드하거나 디버깅하면 문제없이 다 출력이 된다. 그래서 오히려 헤메었다.. python에서는 자바의 Biginteger가 백그라운드에서 자동 지원이라서 string으로 구현하지않아도 문제없이 실행이 ..

[백준 / BOJ] C++ 2096 내려가기

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 사실 한번 살펴보면 간단한 문제이다. dp 문제들에 익숙해지면 조건식을 바로 알아챌 수 있다. 1. 별표 문양이 왼쪽에 있을 경우 dp[i][0] = arr[i][0] + max(dp[i - 1][0], dp[i - 1][1]); 2. 별표 문양이 중앙에 있을 경우 dp[i][1] = arr[i][1] + max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]); 3. 별..

[백준 / BOJ] C++ 1991 트리 순회

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 정말 오랜만에 보는 순회 문제이다. 사실.. 나는 전위, 중위, 후위를 구현하는 방법을 알고있어서 어렵지 않게 문제를 풀었다. 풀이할게 딱히 없고, preorder, inorder, postorder를 구현할줄 알면 어렵지 않게 푸는 문제이다. Code ( C++ ) #include #define MAX 26 using namespace std; int N; typedef stru..

[백준 / BOJ] C++ 1967 트리의 지름

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 깊이우선탐색(DFS)를 이용한 문제이다. 백준 문제를 풀다보면 자주자주 나오는 유형의 문제이다. 그래도 이 문제는 가장 끝 노드와 그 해당 노드로 부터 가장 멀리 떨어진 노드를 찾는다는 조건이 주어지기 때문에 비교적 쉽게 문제 풀이가 가능하다. 조건의 시작점은 트리의 시작 노드에서 부터 가장 멀리 떨어진 노드이다. (DFS 탐색 첫번째) 조건의 끝점은 시작노드로 부터 가장..

[백준 / BOJ] C++ 1932 정수 삼각형

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 문제에서 주어지는 조건을 활용해보자. 아래층으로 내려올때 선택 할 수 있는 수는 윗층에서의 대각선에 위치한 수이다. 즉, 위의 이미지를 참조하여 써보겠다. node[0][0] = 7 node[1][0] = 해당 node + node[0][0], node[1][1] = 해당 node + node[0][0] node[2][0] = 해당 node + node[1][0], node[2][1] = 해당 node + max(node[1][0], node[1][1]), .....

[백준 / BOJ] C++ 1918 후위 표기식

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 후위 표기식 문제이다. 기본적으로 후위표기식의 순서는 다음과 같다. 전체 식 중 괄호 안에 있는 연산 전체 식의 사칙연산 중에서 곱셈 또는 나눗셈이 들어간 연산 이후 더하기 빼기 연산 이후, 전역으로 선언해놓은 스택에는 연산자만 입력해준다. 입력한 문자열 ( 연산식 )의 길이만큼 한글자씩 탐색한다. 그렇다면 후위표기의 알고리즘은 아래와 같다. 알파벳인지, 연산자인지 우선 확인 여는 괄호 ..