★공부일기★

이 문제는 N과 M(3)에서 조금 더 추가된 내용으로 내가 고른 수열이 비내림차순으로 만들어야 한다. 따라서 나는 for문을 한 번 더 돌려 비내림차순인지 확인하고 만약 비내림차순이 맞으면 print하고 아니면 print하지 않는 것으로 나타내었다. https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #include using namespace std; int arr[8] = { 1,1,1,1,1,1,1,1}; i..

이 문제는 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 M개를 고른 수열을 나타낸다. 우선 수열이 나올 수 있는 총 갯수를 m^n을 통해 cnt로 구하고 cnt만큼 for문을 돌려 크기가 7인 배열을 사용하여 끝자리부터 1씩 더해서 올라간다. https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #include using namespace std; int arr[7] = { 1,1,1,1,1,1,1 ..

이 문제는 DFS로 재귀로 문제를 풀 수 있었다. 우선 x기준 4방향, y기준 4방향을 배열에 넣어주고 현재 보고 있는 기준으로 다 돌려보고 배추가 있는지 찾고 있다면 바로 들어가서 탐색하고 나온다. 처음에는 stack에 넣어서 돌렸는데 시간초과가 났다. 그래서 재귀로 바꾸었더니 해결할 수 있었다. www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #include #include using namespace std; vector way; int m, n, k; int ar..

이 문제는 소수를 찾는 것이 핵심이였다. 나는 우선 300000까지의 소수를 모두 구한 다음 for을 통해 소수의 갯수를 구하는 방법을 사용하였다. 소수 구하는 방법은 에라토스테네스의 체를 사용하였다. www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net #include #include using namespace std; int dp[300000]; int main() { // 소수 구하기 dp[0] = 1, dp[1] = 1; for (int i = 2..

이 문제는 2중 배열을 만들어 다 구한 다음 할 수도 있겠다라는 생각을 했지만 시간이 너무 오래걸릴 것 같아서 포기했다. 그래서 규칙을 찾아보니 1, 2~3, 4~6, 7~10, 11~15, 16~21, ... 1씩 커지는 순으로 대각선으로 연결되어 있다는 것을 확인할 수 있었다. 그래서 찾고자 하는 숫자까지 part를 찾은 다음 끝 점에서 찾고자 하는 수까지 규칙적으로 줄어들거나 들어남을 파악하여 더해주거나 빼주어 문제를 해결하였다. www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net #include using namespace std; int main() { int cnt = 1; int ..

이 문제는 증가하면서 감소하는 부분의 가장 긴 수열을 찾는 문제였다. 단순히 증가하고, 감소하는 문제는 LIS 알고리즘을 이용하여 손쉽게 구할 수 있었다. 하지만 이 문제는 두 부분을 모두 찾아야했다. 그래서 생각해낸 방법이 증가하는 부분, 감소하는 부분을 모두 구하고 두 배열을 더해 가장 긴 부분을 찾는 방법을 사용했다. 증가하는 부분의 dp 1 5 2 1 4 3 4 5 2 1 1 2 2 1 3 3 4 5 2 1 감소하는 부분의 dp 1 5 2 1 4 3 4 5 2 1 1 5 2 1 4 3 3 3 2 1 두 dp의 합 1 2 2 1 3 3 4 5 2 1 1 5 2 1 4 3 3 3 2 1 2 7 4 2 7 6 7 8 4 2 여기서 8이 가장 긴 부분 수열이지만 같은 수가 증가하는 수열과 감소하는 부분의..

이 문제는 조금 난이도가 있는 문제였다. maxheap과 minheap을 만들어 minheap의 top과 maxheap의 top은 가운데 값이 된다. 그 두개를 바꾸어 push해주며 maxheap 즉 가운데 값 중 작은 값을 출력한다. www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net #include #include using namespace std; priority_queue maxheap; priority_queueminheap; int ..

이 문제는 절댓값을 다뤄야했다. 그래서 priority_queue를 pair를 사용해 두가지 정보를 입력할 수 있도록 하였다. queue의 first에는 절댓값 즉 수의 크기를 넣어주고 second에는 음수면 0 양수면 1로 넣어주어 절댓값이 같더라도 음수를 더 먼저 올릴 수 있도록 하였다. www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net #include #include using namespace std; priority_queue p..

이 문제는 오름차순으로 정렬되기 때문에 priority_queue에 less를 입력하였다. www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net #include #include using namespace std; priority_queue pq; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i < n; i++) { int num; ..

이 문제는 priority_queue를 이용하여 푸는 문제였다. 처음에 계속 시간초과가 나서 실패하였는데 ios_base::sync_with_stdio(0);과 cin.tie(0);을 입력해주었더니 해결되었다. www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net #include #include using namespace std; priority_queue pq; int main() { ios_base::sync_with_stdio(0); c..