IT세상

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 해결방법은 위와같다 #include using namespace std; int n; void Hanoi(int n, int start, int mid, int end){ // 시작 보조 목표 if(n==1){ cout

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복을 이용하여 풀면 된다 주의할 점 모두 같은 수인지 체크하는 check함수에서 for 문 돌릴때 mapp[x+i][y+j] 확인 divide 함수에서 for문 돌릴때 전체 n이 아니라 나누어진 수 만큼만 돌리면 됨 #include using namespace std; int n; int result[3]; // [0]:-1종이개수, [1]:0종이 개수, [2]:1종이 개수 int..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 두가지 방법으로 풀었는데 표준 라이브러리를 사용하는 방법과 퀵소트를 구현하는 방법으로 풀었다 표준 라이브러리 이용 #include using namespace std; int n, m; vector a; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0; i> x; a..

#include #define MAX_VALUE 9 using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int cnt[MAX_VALUE +1]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); for(int i=0; i

#include using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int main() { ios::sync_with_stdio(0); cin.tie(0); //속도 가속화 for(int i=1; i0; j--){ if(target[j] < target[j-1]){ swap(target[j], target[j-1]); } else break; } } for(int i=0; i

선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 시간 복잡도 : O(N^2) #include using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int main() { for(int i=0; i

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net upper_bound(), lower_bound() [C++] lower_bound, upper_bound (이진탐색)/ 예제 헤더파일 #include lower_bound 찾으려는 value 값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치 리턴 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함 사용법 lower_bound( deve..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 해결 방법 상근이가 가지고 있는 카드를 정렬해준다 이분탐색을 사용한다 #include using namespace std; int n, m; vector a, b; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> x; a.push_back(x); } sort(a.beg..

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..