IT세상

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 유의사항 자른 길이의 합을 구할때 나무가 자르는 길이보다 큰 경우에만 수행이 되도록 조건을 넣어주어야 한다 자른 길이와 길이의 합은 long long int 형으로 선언해주어야 한다 #include using namespace std; int n, m; vector v; int main(void) { ios::sync_with_stdio(0); cin.tie..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net dfs를 활용하여 풀었다 #include using namespace std; int n; int graph[26][26]; vector num; int sum = 0; bool dfs(int x, int y){ // 범위 밖인 경우 if(x=n || y=n){ return false; } if(graph[x][y] == 1){ // 집인 경우 sum += 1; // 집 수 +1 graph[x][y..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제풀이 방법 길이는 int 형의 범위를 넘어가기 때문에 long long int 형으로 선언해준다 (개수는 상관없음) 문제에서 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 의 예시를 보면, 만들어지는 랜선의 개수를 셀 때 랜선의 길이를 빼는것이 아니라 나눈 몫을 더해주어야 한..

lower_bound, upper_bound 설명 https://develop-me-z.tistory.com/114 [C++] lower_bound, upper_bound (이진탐색) 헤더파일 #include lower_bound 찾으려는 value 값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치 리턴 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함 사용법 lower_bound( develop-me-z.tistory.com #include using namespace std; int n, x; vector v; //값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수 int countByRange(vector& v, int leftValue,..

헤더파일 #include lower_bound 찾으려는 value 값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치 리턴 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함 사용법 lower_bound(arr, arr+n, value); // 배열 lower_bound(v.begin(), v.end(), value); // 벡터 lower_bound 의 반환형은 iterator이기 때문에 인덱스를 알고싶은 경우 lower_bound(arr, arr+n, value) - arr; // 배열 lower_bound(v.begin(), v.end(), value) - v.begin(); // 벡터 이렇게 사용하면 된다 upper_bound 찾으려는 value 값을 초과하는 숫자가 배열..

파라메트릭 서치(Parametric Search) : 최적화 문제를 결정문제(예/아니오)로 바꾸어 해결하는 기법 #include using namespace std; int n, m; vector arr; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0; i> x; arr.push_back(x); } // 이진 탐색을 위한 시작점과 끝점 설정 int start = 0; int end = 1e9; // 이진 탐색 수행(반복적) int result = 0; while(start

1e9 = 1*109 = 1000000000 (십억) 2e9 = 2*109 = 2000000000 (이십억) 을 표현할 때 쓴다 2e9 는 int 범위 내에서 무한대 값을 나타낼 때 사용한다

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시간 복잡도 : O(logN) binarySearch 함수에서 vector 함수를 가져오는 경우 꼭 & 를 써준다 #include using namespace std; int n, target; vector arr; int binarySearch(vector& arr, int target, int start, int end){ while(start target) end = mid - 1; // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else start = mid + 1; } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); // 원소의 개수(n)과 ..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에는 예제 보고도 문제가 이해안됐는데 이런 뜻이었다 bfs를 이용해서 풀었고 처음에는 출력하는 부분에서 endl 을 썼는데 시간초과가 떴다 그래서 "\n"으로 바꿨더니 통과했다 #include using namespace std; int n; vector graph[100001]; int parent[100001]; void bfs(int n){ queue q; q.push(n); while(!q.empty()){ int x = q.front(); q.po..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 처음에는 n보다 작은 제곱수 중 가장 큰 제곱수부터 차례로 빼는 방법을 사용했는데 그러면 43같은 반례가 나왔다 ex) 43 = 6² + 2² + 1² + 1² + 1² (5개) 43 = 5² + 3² + 3² (3개) 그래서 dp[n]은제곱수 항의 최소개수로 정하고 n에서 작은 제곱수부터 빼주면서 dp[n] = dp[n - 제곱수] + 1 의 최소값을 구했..