꾸준함

백준 15989번 1, 2, 3 더하기 4

문제 링크입니다: https://www.acmicpc.net/problem/15989 간단한 DP 문제였습니다.[1, 10000]까지 경우의 수를 DP를 통해 미리 다 구해놓은 후 정답을 출력하면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

백준 2670번 연속부분최대곱

문제 링크입니다: https://www.acmicpc.net/problem/2670 그리디 하게 접근한 문제였습니다.구간을 점차 확장하면서, 현재 구간의 연속 부분곱보다 현재 구간의 끝에 위치한 숫자가 큰 경우, 구간의 시작을 초기화하는 방식으로 문제를 해결했습니다. 문제의 예제 입력을 예로 들자면 다음과 같습니다. 구간구간의 연속부분곱현재 구간의 끝에 위치한 숫자연속부분최대곱[0, 0]1.11.11.1[0, 1]0.770.71.1[0, 2]1.0011.31.1[2, 2]1.31.31.3[2, 3]1.170.91.3[2, 4]1.6381.41.638[2, 5]1.31040.81.638[2, 6]0.917280.71.638[2, 7]1.2841921.41.638[7, 7]1.41.41.638   개발환경:..

문제 링크입니다: https://www.acmicpc.net/problem/14627 전형적인 이분 탐색 문제였습니다.한 가지 주의할 점은 파닭을 C개 만든 이후부터는 남은 파를 모두 라면에 넣어야 한다는 점입니다. 예시 입력3 5101010 예시 출력5  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net set 자료구조를 적절히 사용하면 쉽게 풀 수 있는 문제였습니다. 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net lower_bound를 적절히 사용하면 쉽게 풀 수 있는 문제였습니다. 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 백준 12100번 2048 (Easy)와 달리 N이 10이기 때문에 단순 백트래킹만으로는 TLE가 발생하는 문제였습니다. 따라서 적절한 가지치기가 필요했으며 가지치기하는 기준은 다음과 같습니다. 보드 위에 있는 전체 블록을 한 방향으로 이동시켰을 때 블록 상태가 변하는지 여부 현재까지 구한 블록의 최댓값보다 다음 보드 상태에서 기대할 수 있는 블록의 ..

문제 링크입니다: https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제의 핵심은 정확히 d일에 강연을 하는 것이 아니라 d일 안에 강연을 하는 것이었습니다. 알고리즘은 아래와 같습니다. 1. 주어진 p와 d를 d를 기준으로 오름차순으로 정렬합니다. 2. 최소힙을 생성하고 정렬된 순서대로 p를 힙에 넣어줍니다. 2.1 단, 힙의 크기가 넣어준 p의 쌍인 d를 초과할 경우, 힙 내에서 가장 작은 p값인 pq.to..

문제 링크입니다: https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net x와 y 값이 최대 10억이기 때문에 boolean 배열을 선언한 뒤 마킹하는 식으로 풀 수 없는 문제였습니다. 이에 따라 {x, y} 쌍을 저장하는 벡터를 선언하고 오름차순으로 정렬한 뒤 라인 스위핑 기법으로 푸는 문제였습니다. 현재 구간의 y보다 다음 구간의 x가 더 클 경우 현재 [x, y) 길이를 더함 현재 구간의 y가 다음 구간의 x와 y..

문제 링크입니다: https://www.acmicpc.net/problem/14729 14729번: 칠무해 조(Joe)는 중앙대학교 교수이고, 논리회로 설계 과목을 담당하고 있다. 그는 수업을 하면서 7명의 학생을 제외한 나머지 학생들에게 좋은 학점을 주겠다고 약속을 하였다. Joe 교수님을 돕기 위해 www.acmicpc.net 우선순위 큐를 이용하면 쉽게 풀 수 있는 문제였습니다. 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 스택과 배열을 이용하면 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 왼쪽 괄호이면 해당 인덱스를 스택에 넣어줍니다. 2. 오른쪽 괄호이고 유효한 괄호 쌍일 경우 ')' 인덱스와 스택의 top에 위치한 '(' 인덱스를 꺼내와 correct 배열에 true로 표기합니다. 3. 주어진 문자열에 대해 2번 과정을 거친 후 correct 배열에서 연속..