누적합 응용 - prefix/suffix min/max 배열 이용한 테크닉

1. 문제 29726번: 숏코딩의 왕 브실이 (acmicpc.net) 29726번: 숏코딩의 왕 브실이 숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다. 브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열 www.acmicpc.net 2. 풀이 $$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$ 을 관찰하는 것은 어렵지 않다. 주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다. 이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 ..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 2. 12.
• textsms

코딩테스트 복기 - 당장 행동하지 않고 나중에 필요할 때 행동하는 그리디 알고리즘 테크닉

1. 문제 코딩테스트 연습 - n + 1 카드게임 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 무작위로 뒤섞인 1부터 n까지 카드가 n장 있고, coin개의 동전을 가지고 있는데 처음에 n/3장을 가지고 시작 각 라운드가 시작할때 카드를 2장 뽑는데 카드 1장당 동전 1개를 소모해서 가지거나 버릴 수 있다 가지고 있는 카드에 적힌 수의 합이 n+1이 되도록 카드 2장을 내고 다음 라운드로 넘어간다. 카드를 내지 못하거나 모든 카드를 뽑아 더 이상 뽑을 수 없으면 게임 종료 게임을 가장 ..

• format_list_bulleted 그리디 알고리즘
• · 2024. 2. 10.
• textsms

ABC 334 복기 - 배열에서 원소 하나를 제거해서 두 원소 절댓값 차이의 합을 최소로 만들기(prefix sum, suffix sum)

1. 문제 C - Socks 2 (atcoder.jp) C - Socks 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 N쌍의 양말이 있는데, 이 중 지정된 K개의 양말은 각각 1개를 잃어버린 상태이다. 양말의 색을 1,2,3,...,N으로 표시할때, 현재 상태에서 적절하게 짝을 짓는다. 짝지은 양말이 i번째 색, j번째 색일때 |i-j| 의 value를 가진다. 모든 짝의 value합이 최소가 되도록 만든다면? 양말의 개수 2N-K가 짝수라면 상관없지만 홀수라면 1개를 제외하고 짝을 지어야한다. 직관적으..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 1. 1.
• textsms

경이로운 그리디 알고리즘 5 -인접한 원소간 차이의 최댓값을 최소로 만드는 방법-

1. 문제 11497번: 통나무 건너뛰기 (acmicpc.net) 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 2. 풀이 요약하자면 인접한 원소간 차이의 최댓값이 최소가 되도록 배열을 정렬할때, 그 최솟값을 구하는 문제 단순히 크기 순으로 정렬한다고 하더라도.. [a1,a2,a3,...,an]에서 인접한 원소간 차이의 최댓값은 an-a1이므로, 배열의 최댓값과 최솟값의 차이이므로 이것이 최소일리는 없다 만약 크기순으로 정렬한다면, a1 < a2 < a3 < ... < an일때, 이들이 인접했을때, 원소간 ..

• format_list_bulleted 그리디 알고리즘
• · 2023. 11. 7.
• textsms

의외로 알아내기 어려운 2의 거듭제곱을 더하면 나타나는 특징

1. 문제 27514번: 1차원 2048 (acmicpc.net) 27514번: 1차원 2048 첫 줄에 흐즈로가 정의한 연산을 $0$번 이상 수행해 만들 수 있는 가장 큰 최댓값을 출력하세요. 문제의 답은 $2^{62}$보다 크지 않음이 보장됩니다. www.acmicpc.net 2. 풀이 0이나 2의 거듭제곱으로 이루어진 수열이 있는데, 서로 같은 두 수를 찾으면 하나를 2배 해주고 다른 수는 0으로 바꿔준다 이 과정을 반복했을때, 남아있는 수열의 수 중 최댓값을 찾는 문제 처음에는 걍 수의 위치가 중요한 문제는 아니니.. 수열의 값 a와 그 개수를 value로 해서 dict[a] = value로 만들고 dict를 순회해서 value가 2개 이상 있으면 2배한 dict[2a] += 1 해주고, dict..

• format_list_bulleted 애드 혹 알고리즘
• · 2023. 10. 9.
• textsms

두 종류 물건을 특정 개수만큼 사면서 최소 가격에 사는 그리디 알고리즘

1. 문제 30022번: 행사 준비 (acmicpc.net) 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 2. 풀이 첫번째 상점 가격을 오름차순 정렬하고, A개만큼 산 다음, 두번째 상점 가격을 오름차순 정렬해서, 이미 산 아이템일때, 첫번째 상점 가격보다 저렴한지 비교해서 저렴하면 두번째 상점 것으로 사보고.. 아니면 첫번째, 두번째 합쳐서 정렬해서 처음부터 순회할때, A개를 맞추면 나머지는 두번째 상점에서 다 ..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 25.
• textsms