목록알고리즘 (76)

키베이루's diary

[C++] 백준 1449번 수리공 항승

1) 문제설명 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 2) 아이디어 입력받은 배열을 오름차순으로 정렬하고 앞에서 뒤를 뺀 결과만큼 테이프를 소모한다. 그리고 테이프를 모두 소모하면(테이프의 길이가 1보다 작을 경우) 테이프를 다시 리셋시켜준다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; ..
알고리즘/Greedy 2022. 5. 31. 23:29
[C++] 백준 2847번 게임을 만든 동준이

1) 문제설명 https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 2) 해결방법 반복문을 2개 이용하여 입력받은 배열이 오름차순이 될 때까지 뒤에서부터 1씩 빼주고 그 과정을 진행할 때마다 카운트를 +1씩 늘려준다. 이후 카운트를 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long dp[1000..
알고리즘/Greedy 2022. 5. 31. 05:09
[C++] 백준 18870번 좌표압축

1) 문제설명 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2) 해결방법 2개의 벡터에 인덱스와 값을 저장해서 값을 변환 한 뒤 인덱스에 맞게 다시 정렬하는 방법을 사용했다. pair를 사용하여 두 개의 벡터 (v1, v2)를 선언, v1의 값을 오름차순으로 정렬한다. 오름차순으로 정렬한 v1에서 첫 번째 값과 두 번째 값이 같다면 같은 순위이고 두번째 값이 더 크다면 순위가 +1 되기 때문..
알고리즘/기타 2022. 5. 26. 16:42
[C++] 백준 10610번 30

1) 문제설명 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 2) 해결방법 입력을 하나씩 char형으로 받은 후에 int 형으로 변환한다. 그 후 입력받은 값의 합을 저장한 후에 내림차순으로 정렬한다. 입력받은 값의 합이 3의 배수이면 내림차순으로 출력하고 3의 배수가 아니면 -1을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using n..
알고리즘/기타 2022. 5. 26. 03:36
[C++] 백준 1927번 최소힙

1) 문제설명 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2) 해결방법 O(n)의 시간을 맞춰야 하므로 우선순위 큐를 이용하여 구현한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; /* */ int main() { int n; priority_queue pq; cin >> n; for (..
알고리즘/기타 2022. 5. 23. 23:34
[C++] Deque

Deque는 Queue와 Stack이 자료를 한 방향에서만 처리할 수 있는 것과는 다르게 앞과 뒤에서 모두 데이터를 삽입, 제거할 수 있다. Deque의 삽입과 제거는 Queue, Stack 과 같이 모두 O(1)의 시간이 소요된다. Deque와 비슷한 자료구조로는 List가 있는데 List의 경우 앞 or 뒤에서 데이터를 처리할 경우 O(n)의 시간이 소요되므로 경우에 따라서는 Deque의 성능이 압도적으로 좋아질 수 있다. C++에서의 Deque 사용법 1) deque를 헤더파일에 추가한다. #include 2) deque 선언 deque 이름; 3) deque의 여러 기능 deque dq로 선언 이후 dq.push_front(원소) : dq의 첫 번째 원소 앞에 삽입 dq.push_back(원소) ..
알고리즘/기타 2022. 5. 23. 16:44
[C++] 백준 17298번 오큰수

1) 문제설명 백준 Online Judge 17298번 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 2) 해결방법 배열의 오른쪽 부터 스택에 넣고 스택의 값과 배열의 값을 비교하여 새로운 배열에 큰 수를 집어 넣는다. 3) 코드 #include #include #include #include #include #include #include using namespace std; long long arr[1000001]; long long brr[..
알고리즘/기타 2022. 5. 23. 16:13
[C++] 백준 15903번 카드 합체 놀이

1) 문제설명 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 2) 해결방법 처음 입력값 두 개를 더해서 저장한 후 그 값을 다시 입력값에 저장한다. 이후 반복문을 돌면서 오름차순으로 계속 정렬을 한 후 다시 과정을 반복한다. 3) 코드 #include #include #include #include #include #include using namespace std; long long arr[500002]..
알고리즘/Greedy 2022. 5. 22. 06:47
Prev 1 ··· 6 7 8 9 10 Next