본문 바로가기

algorithm/baekjoon24

[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++] 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++] 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.
[C++] 1978::소수찾기 링크 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 1978::소수찾기 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 접근방식 n을 입력받은 뒤 차례로 n개의 수를 입력받고 각 숫자를 1부터 나누기 했을때 약수의 개수가 2개인 소수의 개수를 찾아내었다. 주의할 점 1. 1부터 1씩 키워가며 약수를 구하는 과정에서 nums[i]본인까지 나누어주어야 한다. > n; int * num = new int[n]; //올바른 코드 int n; cin >> n; int nums[n];.. 2022. 10. 8.
[C++] 2693번::N번째 큰수 문제링크 https://www.acmicpc.net/problem/2693 2693번: N번째 큰 수 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000 www.acmicpc.net 문제 배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오. 배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다. 접근방식 T를 입력받아서 2차원 배열을 동적할당해주기만 하면 어렵지 않은 문제였다. 그 뒤로는 sort 함수를 사용하여 오름차순 정렬을 하고 출력만 하면 된다. 주의할 점 C++에서 동적할당은 C언어와 달리 m.. 2022. 10. 7.
[C++] 2609번 최대공약수 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 접근방식 입력받는 두 수를 N1, N2라고 할 때 그 중 큰수를 commonMultiple, 작은수를 commonDivisor 값에 넣는다. commonDivisor 값을 1씩 줄여가며 최대공약수를 찾아내고 commonMultiple 값을 1씩 늘려가며 최소공배수를 찾아냈다. 코드 #include using namespace std; //backjoon 2609 최대공약수.. 2022. 10. 7.

티스토리툴바