본문 바로가기

algorithm28

[C/C++] 백준 11726번 https://www.acmicpc.net/problem/11726  오늘 풀 문제는 실버3 문제다.2xn 크기의 직사각형을 1*2 or 2*1 타일로 채우는 방법의 수를 구하는 프로그램을 작성해보자.  조건:n은 1 이상 1000 이하의 정수다.타일링 방법의 수를 1,0007로 나눈 나머지를 출력해야 한다.아이디어:이 문제는 피보나치 수열과 유사한 규칙성을 갖는다.문제를 작은 부분으로 나누면,n = 1일 때는 1가지 방법만 가능 (타일 하나)n = 2일 때는 2가지 방법 가능 (가로로 1×2 두 개 또는 세로로 2×1 두 개)n = 3일 때는 n = 1과 n = 2를 합친 경우의 수와 같다.따라서, 점화식을 세울 수 있다.점화식:dp[n]=dp[n−1]+dp[n−2]   #include #include.. 2025. 1. 4.
[C/C++] 11725::트리의 부모 찾기 👉 문제 링크 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 👉 문제 👉 문제접근방식 & 주의할점 단순 트리의 부모만 구하면 되는 문제다. DFS, BFS 두 가지 풀이 방법이 있는데 DFS로 풀어봤다. adj에 값을 대칭으로 입력한다. 그리고 자식노드에 하나씩 방문하여 부모를 지정해주는 로직으로 풀었다. 초기에 작성한 코드는 아래와 같다. #include #include using namespace std; int n; //number of nodes vector adj; //int node[100001.. 2023. 8. 15.
[C/C++] ios::sync_with_stdio(false); 와 cin.tie(NULL);을 사용하는 이유 C++로 알고리즘을 풀 때 실행 속도를 높이기 위해 흔히 아래와 같은 구문을 작성해줍니다.ios::sync_with_stdio(false);cin.tie(NULL);저 같은 경우 단순히 시간초과가 발생했을 때 남들이 위 코드를 작성하면 AC를 받을 수 있다고 하여 지속적으로 작성하고 있었는데, 어느 날 갑자기 원리가 궁금해져 찾아봤는데 내용이 흥미로워 오랜만에 포스팅을 작성합니다. ios_base::sync_with_stdio(false);의 장점ios_base::sync_with_stdio 구문은 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생합니다.따라서, ios_base::sync_with_s.. 2023. 8. 10.
[C/C++] 11279::최대 힙, ios::sync_with_stdio(false);와 cin.tie(NULL); 사용하는 이유 👉 문제 링크 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 👉 문제 👉 접근방식 & 주의할점 priority_queue를 사용하여 직관적으로 풀면 쉽게 풀리는 문제이다. 그러나 아래의 두 코드를 사용하지 않으면, 시간초과가 뜬다. ios::sync_with_stdio(false); cin.tie(NULL); ios::sync_with_stdio(false);와 cin.tie(NULL);은 C++의 표준 입출력 라이브러.. 2023. 8. 10.
[C/C++]char형 int형으로 변환 Char형- C언어에서 Char형은 character의 줄임말로 기본적으로 문자를 저장할 떄 사용되는 자료형이ㅏㄷ.- 해당하는 문자의 ASCII코드의 값이 정수로 저장되어 있다. ASCII코드- 위의 표는 아스키 코드 테이블로, 48번 부터 숫자 0-9를 할당하고 있다는 것을 알 수 있다.- 위에서 말했듯이 Char 변수형은 이러한 아스키 코드값을 정수 형태로 저장하므로, 사칙연산이 가능하다. Char형 숫자를 int형으로 변환하는 방법- 숫자의 아스키값은 48번 부터 0-9를 할당하고 있으므로, char형 '1'은 정수값 49를 가진다.- 따라서 0의 아스키값인 48을 char형의 값에서 빼주면 순수한 숫자를 얻어낼 수 있다. char c = '1';int n = c - 48;//n=1- 위와 같은 코.. 2023. 4. 11.
[C/C++] 2805 :: 나무 자르기 👉 문제 링크https://www.acmicpc.net/problem/2805 2805번: 나무 자르기첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보www.acmicpc.net  👉 문제👉 접근방식 & 주의할점이번 문제는 랜선 자르기 문제와 풀이 방식이 유사한 문제이다.이 문제를 풀기 전에 되도록이면 아래의 문제를 먼저 보고 오는 것을 추천한다.위의 문제를 먼저 풀고 오면 이 문제도 자연스럽게 풀릴 것이다. https://onlyoliy.tistory.com/entry/CC-1654-%EB%9E%9C%EC%84%A0-.. 2022. 10. 26.
[C/C++] 1654 :: 랜선 자르기 (이분탐색) 👉 문제 링크https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그www.acmicpc.net  👉 문제👉 접근방식  & 주의할 점이분탐색을 이용한 문제로 백준 2805번 나무자르기 와 비슷한 맥락의 문제이다. 알고리즘1. low의 값을 1, high를 랜선들 중 가장 긴 길이로 지정한다.2. mid값을 구하고, 몇개의 랜선을 만들수 있는지 이분탐색을 이용하여 구한다.(1) 만들수 있는 랜선의 수가 요구되는 랜선수보다 많거나 같다면(count >=.. 2022. 10. 26.
[C/C++] 2512번 :: 예산 (이진탐색) 👉 문제 링크https://www.acmicpc.net/problem/2512 2512번: 예산첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상www.acmicpc.net👉 문제 👉 접근방식 이분 탐색을 사용하는 문제들 중 경로가 가장 확실하게 보이는 문제였다.mid 를 count 로 두고 sum값을 매번 구해서 M과 비교하여 count값을 구해내는 문제다.  👉 코드#include #include #define MAX_COUNT 10000using namespace std;int N, M;int arr[MAX_COUNT];void bsearc.. 2022. 10. 22.
[C++] 2581::소수 링크https://www.acmicpc.net/problem/2581 2581번: 소수M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.www.acmicpc.net  문제자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 접근방식 & 주의할점m부터n까지 수를for문을 사용해서 하나씩.. 2022. 10. 9.
[C++] 1292::쉽게 푸는 문제 링크 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 문제 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 동호야 니문제.. 2022. 10. 8.

티스토리툴바