목록Algorithm (121)
블로그 옮겼습니다
12if(n == (n&-n)) printf("2의 거듭제곱!");else printf("2의 거듭제곱 아님!");cs 이유를 설명하자면 2의 거듭제곱은 어떤 한 비트만 켜져있을 것이다.n & -n 은 n에서 켜져있는 가장 아래의 비트만 켜진 수이다.그렇기 때문에 2개 이상이 켜져있다면 n & -n와는 절대 같아질 수 없는 것이다.그리고 n에 비트가 하나만 켜져있다면 n & -n 은 그 비트만 켜진 수가 되므로 같게되는것이다. +그리고 & 연산자보다 == 연산자가 더 우선순위가 높으므로 괄호를 감싸는것을 잊으면 큰일난다..
문제링크 모든 자연수를 \(1+2+4+.....+2^{k-1}+r\) 로 분해할 수가 있는데M개의 수를 이 방식대로 분해하여 분해된 요소들을 모두 모아 정렬한 결과인 sequence를 A라고 해보자. \(1\leq{N}\leq{10^5}\)\(1\leq{a_i}\leq{10^{12}}\) sequence의 크기 N과 N개의 elements 로 이루어진 A의 원소들 ai 가 입력으로 들어온다. 이 A를 다시 분해하기 전의 원래의 수로 복원하려고하는데 복원하는 방법은 여러가지가 있을 것이다.복원의 결과로 나온 수가 K개일 때 K가 될 수 있는 수는 여러가지가있을 것이다. 이 때 이 가능한 K들을오름차순으로 모두 출력하는게 문제의 질문이다. 우선 k+1 개의 수를 \(1+2+4+.....+2^{k-1}\) 의..
\(1\leq{N}\leq{50}\)\(0\leq{K}\lt{2^N-1}\)괄호 문자열(correct parenthese sequence)의 정의는 이미 잘 알려져 있다.그리고 어떤 문자열 S가 '(' 와 ')' 로만 이루어져있는데 괄호 문자열이 아니라면 이것을 괄호ㄴㄴ문자열이라고 정의한다.N과 K가 주어진다. 길이가 N인 괄호ㄴㄴ문자열들을 사전순으로 정렬했을 때 K번째인 문자열을 찾는 문제이다.인덱스는 0부터 시작한다는 것에 주의하자. 우선 괄호 문자열의 개수를 구하는 방법을 알아보자.dp[i][j] : 이미 i개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 j 개일 때 괄호 문자열의 수dp[i][j] = dp[i-1][j] + dp[i-1][j+1]왜냐하면 각각의 위치에서는 괄호를 열거..
우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 우선 내가 아는 K번째 원소를 찾는 방법들을 구체적으로 써보자면(사실 내가 파라메트릭서치라고 표현하는것도 역시 바이너리 서치인데, 구분을 위해 다르게씀)(그리고 값의 범위가 큰 경우에는 좌표압축은 이미 했다고 가정한다.)1. 벡터+sort2. k번째 원소 세그먼트트리3. k번째 원소 BIT4. BIT + 파라메트릭서치 + 바이너리서치5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치6. 2D 세그먼트트리 이것 이외에도 버킷으로 어찌저찌하는 것도있는것같은데 잘모르겠다. 이것들 중에서 쿼리가 들어와..
boj.kr/9426 \(1\leq{N}\leq{250000}\) \(1\leq{K}\leq{5000}\) \(K\leq{N}\) \(0\leq{a_i}\leq{65535}\) 이 문제는 N개의 수와 구간의 길이 K가 주어졌을 때 N-K+1 개의 연속된 구간의 중앙값을 모두 더하여 출력하는 문제이다. 중앙값의 정의는 (K+1)/2 번째로 작은 수이다. naive 하게 생각해보면 O(N)개의 구간에 대해 정렬하여 가운데값을 구하는데 O(NlgN) 이므로 O(N^2lgN)이 든다. 근데 O(N^2)도 시간안에 돌아가기 힘들다. 어떻게할까? 펜윅트리에 수가 현재 길이 K의 구간안에 하나 들어갈 때마다 수 자체를 인덱스로 1업데이트하고 구간에서 사라지면 -1업데이트하는식으로 생각해보자. 그럼일단 0번째인덱스부터..
\(2\leq{len}\leq{2500}\) 이 문제는 길이 len 의 correct parentheses sequence 가 주어졌을 때 왼쪽에 있는 '열린 괄호'를 하나와 임의의 위치에 있는닫힌 괄호 하나, 총 두개를 지우는 행위를 빈 문자열이 될 때 까지 반복하는 방법의 수를 구하는데, 지울 때 마다 지운 직후에도 correct paranthese sequence 이도록 지우는 방법의 수를 구하는 문제이다. 우선 이 문제를 좀 더 간단하게 바꿔보자. 왼쪽에서부터 열린괄호 하나와 닫힌괄호 하나를 지워나가는 것은 결국열린괄호 하나와 닫힌괄호 하나를 매칭시키는 것과 같다고 볼 수가 있다. 물론 한 쌍을 지워도correct parentheses sequence 이도록 말이다. 그럼 주어진 제약조건을 만족하..
문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{c}\leq{10^9}\) 노드의 개수 N, 엣지의 개수 M, 각 엣지에는 색 c 가 부여된다. 색은 정수로 주어진다. 엣지는 양방향이다.두 노드 사이에 엣지는 여러개 있을 수 있다.출발점은 1번노드, 도착점은 N번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.출발점부터 도착점까지 최단경로로 갈 때의 색의 sequence 를 구하는 문제. 만약 최단경로가 여러개라면사전순으로 앞서는 sequence 를 구하는 문제이다. 우선 priority_queue 를 사용해 다익스트라를 하듯이 거리와 색의 우선순위에 따라 도착지까지 가면서색의 seqeunce 를 구해주면 될..
예를 들어vector v[3] 이 있고v[0] = {2, 5, 9, 3}v[1] = {0, 7, 4}v[2] = {1, 6, 8} 일때, 각각의 벡터를 정렬한 뒤 벡터들은 사전순으로 정렬 하려면그냥 sort(v, v+3) 을 하면 알아서 한꺼번에 정렬됨
문제 링크 이 문제는 일단 모빌이 주어진다. 모빌이란, 막대기가 있고 막대기의 양쪽에 모빌또는 물체가 달린다.모빌의 깊이는 최대 16이다. 이때 각 모든 막대기의 양옆에 달린 덩어리 두개가 균형을 이루게 만들기 위해최소 몇개의 물체나 무게를 변경해야 하는지 구하는 문제이다.예를들어,이런 모빌이 있다면 7을 3으로 만들면 모든 막대기에서 균형이 맞게되므로 답은 1이다.3을 7로, 6을 14로 바꿔도 균형을 이루지만 최소의 개수가 아니기 때문에 답이 아니다. 그러면 결국 전체 모빌의 무게를 x로 만들려고 할때 각 덩어리의 무게는 다음과 같이 만들어 주어야 한다. 그렇다면 x를 정해주고 재귀적으로 따라 내려가면서 각각의 덩어리에 대해 되어야 하는 무게와 현재 물체의 무게가같다면 바꾸어 주어야하는 것이기 때문에..
문제 링크 \(1\leq{V}\leq{10^3}\)\(1\leq{E}\leq{V\cdot(V-1)/2}\)\(1\leq{T}\leq{10}\) 도시의수 V와 검사해야 할 도로의 수 E가 주어지고, E개의 줄에 대해 도로가 잇는 두 도시 a b 가 주어진다.모든 두 도시 간에는 도로가 있으며, 각 도로를 지나는데 드는 시간은 T이다. 도로를 검사하는 검사자가 주어진 E개의 도로를 모두 지나야 한다. 이 때 최소 시간을 구하는 문제이다. 모든 엣지의 가중치가 T로 같은 것이기 때문에 이 문제는 결국 최소의 간선을 지나면서 주어진 간선을 모두 지나는문제를 풀고 T를 곱하면 된다. 최소의 간선을 지나려면 주어진 간선들을 딱 한번씩만 지나고주어진 간선 외의 간선은 가능한한 지나지 않으면 될 것이다. 주어진 간선만..