![]()
문제 문제링크: https://www.acmicpc.net/problem/30961 풀이방법 문제의 요구사항은 길이가 "1" 이상인 모든 부분수열 각각의 합을 구하여 모두 XOR한 합을 구하는 것이다. 해당 문제를 보자마자 바로 에드 훅 문제라는것을 생각했지만. 생각보다 푸는데 오랜시간이 소요되었다. 우선 문제를 풀기 위해 XOR 의 특징을 이용하기로 했다. 같은 수 X 를 2^N 번 XOR 연산하면 그 수는 0이 된다. 해당 문제에서 정의하는 부분수열은 인접하지 않아도 되었기 때문에 입력으로 주어진 배열을 오름차순으로 정렬하여 배열을 분석할 수 있다. 2, 3, 1 -> 1, 2, 3 풀이를 좀더 쉽게 생각하기 위해 아래와 같은 배열이 있다고 가정한다 1, 2, 3, 4, 5 최대값의 위치를 M 최소값..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이시간 설계: 160분 구현: 20분 문제 종류 스택, 자료구조 풀이 방법 이 문제의 요구사항은 다음과 같이 정의된다. 1. 두개의 인덱스를 결정한다. (A,B) 2. 두개의 인덱스 사이에 있는 값들은 arr[A] > val and arr[B] > val 을 동시에 만족해야한다. 예를들어 배열이 4,2,3,5 와 같은 형태의 경우 가능한 쌍은 아래와 같다 (4,2),(4,..
