본문 바로가기

백준84

[2559] 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 누적합 문제이다. 인덱스 1부터 i까지의 누적합을 A[i]에 담았다. 그 다음, K를 활용하여 연속적인 날짜의 수를 구하고, 최댓값을 갱신해주며 문제를 풀었다. 초기 최댓값은 A[K]로 설정하였다. 그것이 첫 연속적인 날짜 수의 합이기 때문이다. 그림으로 설명하면 위와 같다. #include #include using namespace std; int N, K; int A[100001.. 2023. 1. 8.
[10828] 스택 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택을 직접 구현해보는 문제이다. 크기가 1,0001인 배열을 선언하고 start, end 인덱스를 바꿔주며 값을 넣었다. 전체 코드이다. #include using namespace std; int N; struct stack_ { int start = 1; int end = 0; int A[10001]; void push(int value) { end++; A[end] = v.. 2023. 1. 7.
[12015] 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 11053번 가장 긴 증가하는 부분 수열 문제와 비슷하다. 배열이 커져서 O(n^2) 알고리즘을 못쓰게 된 것이 좀 다르다. 사실 모르겠어서 폭풍 구글링을 진행했다. LIS 알고리즘 너무 어렵다 ㅠㅠ algorithm 헤더에 있는 lower_bound를 이용하여 문제를 풀었다. lower_bound : 원하는 수 이상인 수가 처음으로 등장하는 위치를 반환 물론 배열을 빼줘야된다(-DP). 아니면 .. 2023. 1. 6.
[10844] 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제인데 한참을 헤매다가 다른 사람의 풀이를 참고하였다. 직접 써내려가면서 규칙을 찾아보려 했으나 N=4까지만 보고 규칙을 정한 탓에 틀려버렸다. for (int i = 3; i > N; /* 초기값 설정 */ for (int i = 0; i 2023. 1. 4.
[11053] 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP문제이다. for문 하나로 어떻게 풀지? 끙끙대다가 포기하고 LIS 알고리즘에 대해 검색해보았다. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) : 일부 원소를 골라내어 만든 부분 수열 중, 각 원소가 전 원소보다 크고(증가), 그 길이가 최대인 부분 수열 크게 O(n^2)로.. 2023. 1. 3.
[1463] 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 오랜만에 다이나믹 프로그래밍 문제! 먼저 범위를 설정하고 메모이제이션을 이용해야 하므로 배열을 선언해주었다. int A[1000001]; A[0]은 안 씀! 그리고 직접 써보면서 규칙을 찾아보았다. 직접 배열을 채워보면서 규칙을 찾았다. 1을 빼고 바로 전 값의 A[i-1]을 더하는 경우가 있고, 3을 나누고 A[i/3]을 더하는 경우가 있고, 2를 나누고 A[i/2]을 더하는 경우가 있었다. 그리하여 아래와 같은 규칙을 완성하였다. 이를 코드로 작성하면 아래와 같다. for (int i = 4; i > N; .. 2023. 1. 2.
[1912] 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net DP 문제이다. 시간 제한이 1초라서 이중 for문은 안되겠구나.. 생각했다. 근데 처음에 이중 for문으로 풀었다.. 2시간 삽질의 서막 누적합을 배운지 얼마 안돼서 누적합을 이용하여 문제를 풀려고 했다. #include #include #include using namespace std; int N; int A[100001]; // A[i] = 1~i까지 더한 값 int R[100001]; int mai.. 2022. 11. 18.
[2263] 트리의 순회 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 분할정복 문제이다. 일단 트리의 순회 3 종류를 알아야 한다. 중위 순회는 left -> root -> right 후위 순회는 left -> right -> root 전위 순회는 root -> left -> rigjt 순서이다. 우리가 받는 정보는 중위 순회와 후위 순회이다. root를 기준으로 left/right를 나누어서 계속 탐색하면 된다. 하지만 중위 순회 정보만으로는 어느 것이 root 노드인지 알 수 없다. 그러.. 2022. 11. 17.
[1891] 사분면 https://www.acmicpc.net/problem/1891 1891번: 사분면 첫 줄에 이동시키려는 사분면 조각 번호의 자릿수를 나타내는 정수 d와, 그 사분면 조각의 번호가 주어진다. (1 ≤ d ≤ 50) 둘째 줄에는 이동의 내용을 나타내는 두 정수가 x, y가 주어진다. (|x|, |y| www.acmicpc.net 재귀를 사용하였다. 사분면을 좌표로, 좌표를 사분면으로 만드는 함수를 작성하였다. 일단 string으로 사분면 조각의 번호를 받고 int형 배열에 나눠 담아주었다. for (int i = 0; i < d; i++) { A[i] = input[i] - '0'; // char to int } 그 다음 생기는 좌표의 범위를 계산해주었다. d=1일 때는 2*2 배열이 생성되고, d=3일.. 2022. 11. 14.
[2448] 별 찍기 - 11 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀 문제이다. 4시간동안 삽질하다가 풀었다. 비어있는 공간을 중심으로 코드를 짜보기도 하고, '*'을 중심으로 코드를 짜보기도 했는데, 결국은 다 구현하지 못했다. 최후의 방법은 삼각형 맨 위의 꼭짓점의 좌표 정보를 담고 재귀를 진행하는 것이었다. 말보다는 그림이 더 편할 것 같다! 삼각형 맨 위의 꼭짓점에서 위쪽/왼쪽/오른쪽의 삼각형이 다시 재귀함수로 들어간다. 이 역시 맨 위의 꼭짓점 좌표 정보가 들어간다. 파란색 동글 -> 하늘색 동글 이런식.. 2022. 11. 13.

티스토리툴바