kyjdummy 님의 블로그

문제 : https://www.acmicpc.net/problem/17033 [ 문제 요약 ]노드와 질의 가 주어지며, 각 노드에 대해 초깃값이 주어집니다.1 i v 입력 : i 노드의 값을 v로 변경2 i j 입력 : i 노드부터 j 노드까지 경로의 모든 값들을 XOR 하여 출력[ 테스트 케이스 설명 ]5 5 // 노드개수N(2 [ 문제 해설 ]이 문제를 풀기 위해서는 HLD 알고리즘을 사용해야 합니다. HLD 알고리즘 관련 설명은 아래 링크의 [ 문제 해설 ]에 설명되어 있으니 참고 부탁드립니다.https://kyjdummy.tistory.com/21HLD 알고리즘을 사용해 트리를 세그먼트 트리에서 사용할 수 있도록 체인으로 분할 후 각 범위에 맞게 XOR 값을 출력해 주면 되는 전형적인 HLD ..

문제 : https://www.acmicpc.net/problem/13512[ 문제 요약 ]트리가 주어지고, 처음엔 모든 노드가 흰색이라 생각한다.쿼리는 2가지로, 1 i와 2 v가 입력된다.1이 입력되면 i 번 노드의 색을 반전(흰 →검, 검→흰) 2가 입력되면 1번 노드부터 v 번 정점으로 가는 경로에 존재하는 첫 번째 검정 정점의 번호를 출력 [ 테스트 케이스 설명 ]9 // 노드개수 2 [ 문제 해설 ]이 문제는 기본적인 HLD 알고리즘으로 풀 수 있습니다. HLD 알고리즘에 관한 설명은 아래 링크 [문제 해설]에서 확인할 수 있습니다.https://kyjdummy.tistory.com/21문제에서 원하는 출력은, 1번 노드에서 v 노드로 갈 때 첫 번째 노드의 번호입니다. 이를 위해 세그먼트..

문제 : https://www.acmicpc.net/problem/16993 [ 문제 요약 ]배열의 초깃값이 주어지고, 범위가 주어질 때, 그 범위 사이에서 가장 큰 부분합을 구하는 문제입니다. [ 테스트 케이스 설명 ]10 // 수열의 크기 N(1 [ 문제 해설 ] 이 문제는 별도의 자료구조를 만들어 풀 수 있습니다.class Node{ int left, right, sum, max; Node(int l, int r, int s, int m){ left = l; right = r; sum = s; max = m; }} 위 와 같이 트리의 노드 하나당 left, right, sum, max 값을 갖도록 만듭니다. 각각의 원소 의미는 아래와 같습니다. left : 해당 객체가 표현하..

문제 : https://www.acmicpc.net/problem/2336 [ 문제 요약 ]A가 B보다 3가지 성적이 모두 좋다면 A는 대단한 것이고, 이 A보다 대단한 학생이 없으면 A를 굉장하다고 합니다. 여기서 굉장한 학생의 수를 구하는 것입니다.[ 테스트 케이스 설명 ]10 // 학생 수 1 [ 문제 해설 ] 문제를 간단하게 말해서 3개 과목 모두 나보다 순위가 작은 사람이 없으면 나는 굉장한 학생이 되는 것입니다. 그래서 입력이 3줄로 들어올 때, 한 학생의 3가지 과목 순위를 담을 객체를 만들어, 각 학생마다 순위들을 몰아서 하나의 객체에 저장해 놓습니다. 그럼 하나의 객체에는 과목(1), 과목(2), 과목(3)의 순위가 각각 들어가 있을 텐데, 이를 과목(1)의 순위 기준으로 오름차순 정렬합..

문제 : https://www.acmicpc.net/problem/14855[ 문제 요약 ]간단히 말해, 밀가루의 총량이 주어지고, 밀가루 양 안에서 만두를 만들 때, 가장 크게 이득을 취할 수 있는 금액이 얼마인지를 묻는 문제 [ 테스트 케이스 설명 ] 10 2 2 1// 밀가루그램N(1 [ 문제 해설 ]코드는 2가지로 제공합니다. 처음 코드는 논리적으로 이해하기 쉽게 2차원 배열로 제시하고, 그 후 코드는 이를 더 최적화한 코드가 제시됩니다. 문제에서 입력이 너무 다양하게 많이 들어와 복잡할 수 있으나, 하나하나 뜯어 생각하면 간단합니다. 각 행마다 만두 속 총량과, 만두 하나를 만드는데 필요한 만두소가 따로 주어지는데 이건 두 변수를 “만들 수 있는 만두 개수”라는 개념으로 합칠 수 있습니다. 만..

문제 : https://www.acmicpc.net/problem/2994 [ 문제 요약 ]공연의 전체 시간 T(최대 5,000분)와 멤버의 수(최대 500)이 주어집니다.각 멤버는 공연 시간 내에서 정해진 길이의 휴식 시간이 필요합니다. 단, 공연 중 동시에 최대 2명까지만 휴식을 갈 수 있습니다.답이 항상 있는 경우만 주어집니다.각 멤버의 순서대로 언제 휴식을 갈지 휴식 가는 시간을 멤버마다 출력하면 됩니다. 답은 여러 개일 수 있으므로 그중 하나만 출력하면 됩니다. [ 테스트 케이스 설명 ]8 3 // 총시간(1 [ 문제 풀이 ] 배낭 2개에 각 멤버를 채우는 방식으로 해결할 수 있습니다. 먼저 하나의 배낭에 멤버들의 휴식 시간을 최대한으로 집어넣습니다. 그렇게 되면 선택되지 않은 나머지 멤버들은..

문제 : https://www.acmicpc.net/problem/13925 [ 문제 요약 ]배열의 초깃값이 주어지고, 명령어가 주어졌을 때, 명령어에 따라 배열의 값을 수정하는 것입니다.명령어 코드가 1일 때는 x, y 범위의 모든 값에 주어지는 값을 더하고, 2는 곱하는 것이고, 3은 주어지는 값으로 해당 범위 값들을 모두 대체하는 것입니다. [ 테스트 케이스 설명 ]4 // 배열 원소 개수 1 [ 문제 풀이 ]이 문제는 크기가 최대 10억 인 값들을 갖는 배열에 대해 구간 합 쿼리와, 구간 더하기, 구간 곱하기, 구간 대입의 쿼리를 실행해야 합니다. 배열의 크기와 쿼리 개수가 최대 10만이기 때문에 단순 반복 업데이트로는 시간 초과가 발생합니다. 그래서 느리게 갱신되는 세그먼트 트리라는 강력한 자..

문제 : https://www.acmicpc.net/problem/6066 [ 문제 요약 ]목표 건초더미 무게가 주어지고, 각 업체들의 개수가 주어집니다.각 업체들에서 건초 더미를 무제한으로 가져올 수 있고, 업체들마다 건초더미의 무게당 가격이 주어집니다. 건초 더미는 나눌 수 없고 덩어리로 사야 됩니다.이때, 목표 건초더미 무게(초과 상관없음)를 달성하기 위해 드는 최소 가격을 출력 [ 테스트 케이스 설명 ]2 15// 업제개수(1 [ 문제 풀이 ]한 업체의 건초 더미를 무제한으로 살 수 있으므로 무한 배낭 문제입니다. 그리고 건초 무게를 초과해서 달성해도 비용만 최소 면 상관없기 때문에 dp 식을 구할 때, 현재 for 문의 값으로 미래 무게를 구해야 합니다. 이 부분은 코드로 봐야 합니다. dp 구..

문제 : https://www.acmicpc.net/problem/5909 [ 문제 요약 ]건초더미들과 그 무게들이 주어질 때, 건초더미들을 3개의 그룹으로 나누고, 3개의 건초 더미 중 최댓값이 최소가 되도록 한다. [ 테스트 케이스 설명 ] 8 // 건초더미 개수 1 [ 문제 해설 ] 문제는 세 그룹으로 분할하는 문제지만, 세 그룹을 모두 고려하는 것은 상태가 너무 많아 효율적으로 풀기 어렵습니다. 대신, 두 그룹의 합에 대해 동적 계획법(DP)을 적용하여 만들 수 있는 가능한 합들을 기록하고, 나머지 세 번째 그룹은 전체 합에서 두 그룹의 합을 빼서 자동으로 결정되는 방식으로 접근합니다. 일반 배낭 문제에서는 가치의 최대화를 목표로 하지만, 이 문제에서는 세 그룹 중 가증 큰 합(즉, 불균형 정..

문제 : https://www.acmicpc.net/problem/1231  [ 문제 요약 ]초기 자본이 주어지면, 일자가 증가함에 따라 주식을 사고팔 때, 마지막 날 얻을 수 있는 최대 이익을 구합니다. [ 테스트 케이스 설명 ] 2 3 10 // 주식수(1  [ 문제 풀이 ] 이 문제는 그리디 하게 풀어야 합니다. 각 날짜마다 얻을 수 있는 차익의 최대 금액을 구하고, 그 날짜마다 구한 최대 이익을 초기 자금 M에 계속 더해나가고  결과 적으로 M을 출력해 주면 됩니다. 예를 들어 위 테스트 케이스처럼 3일이 주어지면, 이득이 발생하는 일자는 2일부터입니다. 그 이유는 1일 날은 사기만 하고, 팔지는 않기 때문에 결국 추가 이익이 없기 때문입니다. 그래서 반복문을 생각할 때 차익이 발생하는 2일부터..