일직선 상에서 특정 위치에서 거리 합이 최소가 되도록 집을 짓는 문제

18513번: 샘터 N개의 샘터가 주어질때 K채의 집을 지을려고 한다 각 집에서 가장 가까운 샘터까지의 거리를 불행도라고 정의할때 K채의 집의 모든 불행도의 합이 최소가 되도록 집을 짓는다 그 불행도의 합의 최소를 구하는 문제 ------------------------------------------------------------------------------------------------------------------- BFS로 풀 수 있다는데 생각해봐도 감이 잘 안오더라고... 평소 BFS문제랑 조금 달라서 그런지 샘터 위치 x에서 왼쪽 오른쪽으로 -1,1만큼 봐서 비어있으면 x-1, x+1에 집을 짓고 다시 x-1에서 왼쪽 오른쪽으로 -1,1만큼 x-1,x에서 비어있으면 집을 짓고 x+1에..

• format_list_bulleted DFS BFS 정복기
• · 2025. 4. 5.
• textsms

문자를 하나만 바꾸거나, 처음부터 연속된 k개를 바꿔서 전부 같은 문자로 바꾸는 다이나믹 프로그래밍

2806번: DNA 발견 A나 B로 이루어진 문자열에서 첫번째 연산은 하나의 문자를 A는 B로, B는 A로 바꾸는 것이다. 두번째 연산은 처음부터 연속된 K(1  예를 들어 ABBA라면, B 2개를 각각 A로 바꾸면 AAAA가 되고 처음부터 3개의 문자 ABB를 뒤집어서 BAA로 바꾸고, BAAA에서 첫번째 문자 B를 A로 바꾸면 2회만에 AAAA로 된다. 이러한 두 연산으로 모든 문자를 A로 바꾸고 싶다 가능한 최소 연산 횟수는? ----------------------------------------------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 23.
• textsms

인접한 원소의 곱의 합이 최대가 되도록 수열을 만드는 방법

16209번: 수열 섞기 수열 a1,a2,...,an이 주어질때 인접한 원소들의 곱 a1a2 + a2a3+... + an-1an이 최대가 되도록 수열을 섞고 싶다 그렇게 섞은 수열 하나만 구한다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 적어도 양수는 양수끼리, 음수는 음수끼리 곱해야 한다는 것을 생각할 수 있다 또한 절댓값이 큰 것끼리 곱해야 커진다는 것도 생각할 수 있다 양수 그룹에서 큰 값들을 먼저 찾아서 a1 > a2 > .... > an이라고 한다면... a1 a..

• format_list_bulleted 그리디 알고리즘
• · 2025. 2. 20.
• textsms

똑같은 원소를 연속해서 사용하지 않도록 최대한 쓰는 놀라운 그리디 알고리즘

25635번: 자유 이용권 i번째 놀이기구 이용권의 횟수가 A[i]로 주어진다 모든 놀이기구를 이용하고 싶은데 연속으로 같은 놀이기구를 사용하지 않는다 최대 몇번 사용가능한가? A = [1,1,3]이면 3번, 2번, 3번, 1번, 3번으로 5번 가능하다 처음에 생각하기에는 무조건 큰 값끼리 모아서 쌍으로 이용하면 된다고 생각을 했는데 A = [1,2,3,4,5]라고 한다면  5번 이용가능한거랑 4번 이용가능한거 모아서 5 4 5 4 5 4 5 4 이렇게 하면 8번 쓰는거고 5가 1번 남고 [1,2,3,0,1]에서  3,5 해서 3번이 2번 남고 [1,2,2,0,0]에서 3번 2번 가져와서 3,2,3,2 해서 [1,0,0,0,0] 해서 1번을 쓰면 된다는 식으로 n = int(input())A = list..

• format_list_bulleted 그리디 알고리즘
• · 2025. 1. 21.
• textsms

(두 위치의 거리 * 두 위치의 원소 중 최솟값)의 최댓값을 투포인터로 찾는 방법

22945번: 팀 빌딩  n명이 한줄로 서있을 때 2명을 골라 그 2명 사이의 사람 수 * min(첫번째 사람의 능력치, 두번째 사람의 능력치)의 최댓값을 찾는 문제 [1,4,2,5]이면 A[1] = 4, A[3] = 5이고 두 사람 사이에는 1명 있고 둘 중 최솟값은 4니까 4가 최댓값이다 투 포인터로 해결할 수 있다해서 연습삼아 풀어볼려했는데 기존에 알던 투 포인터 풀이는 안먹히니 답이 없다 인덱스랑 같이 넣어서 정렬해야하나 일단 정렬이 안되어있고 포인터 움직여도... min값이 커졌다 작아졌다 하는데 근데 0번과 n-1번에 포인터를 두고 서로 간격을 좁혀가면 된다는데 그래도 어떻게 해야하는지 고민되더라고 A[i], A[i+1], A[i+2], A[i+3], ...., A[j] i번과 j번을 가리키고..

• format_list_bulleted 투 포인터 알고리즘
• · 2025. 1. 7.
• textsms

m개의 원소를 조건에 맞게 n개의 원소에 배치하는 방법

C - Kaiten Sushi  C - Kaiten SushiAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  i번째 사람의 미각 점수는 A[i]로 주어지고, j번째 초밥은 맛 점수가 B[j]로 주어진다. j = 1,2,..,m번 초밥이 1번부터 n번 사람에게 순서대로 주어지는데 A[i]  각각의 초밥이 어떤 사람에게 먹어지는지 결정한다. n,m  예를 들어 A = [3,8,2], B = [5,2,1]인데 B[0] = 5가 1번 사람에게 주어질때, A[0]  B[1] = 2가 1번 사람에게 주어지는데, A[0] > B[1]..

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