11232번: Shuffles (acmicpc.net) 주어진 수열이 최소 몇번의 shuffle로 이루어진 수열인지 구하는 문제 셔플방법은 수열에서 어떤 특정 지점에서 두 부분으로 나누고 두 부분을 순서를 유지한채 섞는 것이다. 1 2 3 4 5라면.. 1 2 3 4 5로 나누고 1 4 2 5 3 처럼 섞는 것 주어진 수열에서 어떤 특정 지점 k에서 나뉘었다고 한다면, 2개의 부분 수열 1,2,3,...,k k+1,k+2,...,n으로 나뉘고 이것이 섞일 것이다. 이렇게 섞인 수열에서 또 한번 나누면 최대 4개의 부분 수열 1,2,3,..,k1 k1,k1+1,...k k+1,k+2,..k2 k2+1,k2+2,...,n으로 구해진다. 여기서 또 한번 나누면 최대 8개의 부분 수열을 얻을 수 있다. ...
18668번: Find the Vertex (acmicpc.net) 무방향 연결그래프가 주어지고, self-loop나 multiple edge가 없다. 정점의 번호가 1번부터 n번까지 되어있고, 시작정점 s번에서 다른 정점까지의 거리를 3으로 나눈 나머지가 배열로 주어진다. 여기서 s가 무엇인지 찾는 문제 n,m 제한이 50만이다보니, 하나하나 해보기는 어렵다. 일단 거리 배열에서 0인 값인 정점 번호가 일단 정답 후보가 될 것이다. 시작정점 s에서 거리가 3,6,9,... 3의 배수여도 0이기 때문에 정답이 아닌 정점이 있을 수도 있다. 또 하나 알 수 있는 점은, 시작정점 s라면 인접한 정점까지 거리는 무조건 1이다. 물론 위 그림과 같이 s에서 인접한 3개 정점과 똑같이 인접한 어떤 정점 A..
F - Double Sum (atcoder.jp) F - Double SumAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제는 매우 간단하다 A1,A2,A3,...,AN이 주어지면, $$\sum_{i = 1}^{n} \sum_{j = i+1}^{n} max(A_{j} - A_{i},0)$$을 구하는 문제 n제한이 40만이라 단순하게 풀면 당연히 시간초과... 1. max(a,b) = (|a-b| + a+b)/2 방법은 많이 있던데 아주 간단하고 경이로운 솔루션이 있어서 복기해본다 배열 A에 대한 함수 f를 다음과 같이..
1. 문제 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 핵심은 눈치 잘 챘는데.. 시간의 압박에 못이겨서 그런건지 시간초과에서 못벗어났다.. 다시 풀어보니까 시간복잡도를 생각해서 기본에 충실하게 DFS 그래프 탐색을 구현한다면 생각보다 쉽게 풀 수 있더라고 평면에 도넛, 막대, 8자모양 그래프가 여러개 있는데.. 이 그래프와 무관한 하나의 정점을 생성하고 이 정점과 각 그래프의 임의의 정점 중 하나에 연결시켰다 무관한 하나의 정점 번호와 도넛, 막..
1. 모든 원소 쌍의 XOR 합 $A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제 단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다. 결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다. 그런데 V를 2진수로 나타낸다면.. $$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다. 여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다. 만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대..
1. 연속하는 부분열에 대한 XOR n개의 음이 아닌 정수 $A_{1}, A_{2}, ... , A_{n}$에 대하여 L번부터 R번까지의 XOR $A_{L} \oplus A_{L+1} \oplus ... A_{R}$의 값은? 만약 $V_{0} = 0, V_{i} = A_{1} \oplus A_{2} \oplus ... \oplus A_{i}$라고 하자. $V_{L-1} = A_{1} \oplus A_{2} \oplus A_{3} .... \oplus A_{L-1}$이다. 그러면, $0 \oplus x = x, x \oplus x = 0$이므로.. 0을 xor해도 값이 달라지지 않는다. $$A_{L} \oplus A_{L+1} \oplus ... A_{R} = 0 \oplus (A_{L} \oplus A_..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
