CodeAngie

문제 x와 k가 주어졌을 때, 다음 식을 만족하는 k번째 y를 구하는 문제이다. x + y = x | y 여기서 |는 비트 연산자 OR를 의미한다. 풀이 x + y와 x | y가 같다는 것은 2진수로 바꾸었을 때, 1의 위치가 서로 다르다는 것을 의미한다. 예를 들어 x가 5(101) y가 2(10)이라면 101 + 10 = 101 | 10 = 111로 같다. 이때 y를 구하는 것임으로 x를 기준으로 y를 설명하자면, x가 1이면 y는 0을 가지고 x가 0일 때 y는 1 혹은 0을 가질 수 있다는 것이다. k번 째 y는 1 혹은 0이 들어가는 자리를 조절하여 구할 수 있다. 첫 번째 y는 x가 0인 곳에 1(1)이 들어가면 되고 두 번째 y는 x가 0인 곳에 2(10)가 들어가면 된다. 위의 그림에서 검..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 풀이 DP를 사용하여 LIS를 구하는 기존 문제에 부분 수열의 길이뿐만 아니라 부분 수열을 요소까지 출력하는 문제이다. 따라서 증가하는 부분 수열의 요소를 담는 것을 함께 구현해야 한다. 증가하는 부분 수열의 요소를 담는 리스트를 생성하고 dp가 증가할 때 함께 업데이트 되도록 한다. 알고리즘 n과 a 수열을 입력받는다. 1로 초기화된 dp를 생성한다. 부분 수열의 요소를 담을 b 리스트를 생성한다. A 수열에서 뒤의 요소가 앞의 요소보다 크고 부분 수열의 길이도 더 길어질 때, 부분 수열의 길이를 업데이트 하면서 부분 수열의 요소도 업데이트 해준다. 가장 긴 부분 수열의 길이를 찾아 출력하고, 해당 위치와 동일한 부분 수열의..

문제 n개의 1차원 숫자 배열이 주어졌을 때, 연속된 부분합이 m으로 나누어 떨어지는 경우의 수를 구하는 문제이다. 풀이 부분합을 m으로 나누었을 때 나누어 떨어지는지가 문제임으로 나머지끼리의 연산을 통해 문제를 풀 수 있다. 특히 1차원 부분합은 누적합의 뺄셈을 통해 구할 수 있음으로 $ partSum = prefixSum[j] - prefixSum[i]$ $( i < j ) $ 나머지가 같은 누적합의 뺄셈 계산을 통해 m으로 나눈 나머지가 0이 되는 부분합을 구할 수 있다. 부분합을 구할 때는 항상 뒤에 위치한 j번째 누적합에 i번째 누적합을 빼야한다. (i < j) 즉, 나머지의 수가 같은 누적합의 조합을 통해 나머지가 0이 되는 부분합의 경우의 수를 구할 수 있다. $_nC_2 = \frac{n ..

문제 새로운 언어로 암호화된 문장을 해석하는데 드는 비용의 최솟값을 구하는 문제이다. 이 문장은 연속된 단어의 연결로 이루어져 있으며, 단어는 0번 이상 쓰일 수 있다. 또한 각 단어는 알파벳의 순서를 바꾸어 암호화되었을 수 있다. 이러한 문장을 해석하는 비용은 원래 단어의 위치와 다른 위치에 있는 알파벳 개수만큼 든다. 예를 들어 원래 단어가 one 이라면, oen은 비용이 2만큼, neo는 비용이 3만큼 든다. 풀이 암호화는 한 단어 내에서 알파벳의 위치만 변한 것이다. 따라서 문장 내에 주어진 단어가 포함된다면 그 단어의 길이만큼 문장을 잘랐을 때, 주어진 단어의 알파벳을 정렬한 결과와 문장에서 잘린 부분의 알파벳 정렬 결과가 동일해야 한다. 정렬 결과가 같다면 주어진 단어를 만들 수 있음으로 해석..

문제 문자를 직접 타이핑하는 방법은 s초, 복사&붙여넣기 방법은 t초가 걸릴 때, 같은 말을 n번 반복해서 입력하는데 걸리는 최소 시간을 구하는 문제이다. 풀이 같은 말이 c번 적혀있고 추가로 c번 작성한다고 한다면 (2배로 만든다면) 위의 그림과 같이 s초씩 c번 작성하는 방법과 t초동안 한 번에 복붙하는 방법이 있다. 즉, 최소 시간을 만들기 위해서는 문자를 두배로 만들 때, 두 가지 방법 중 더 적은 시간을 소요하는 방법을 선택해야 한다. 같은 말을 n번 작성하는데 걸리는 시간을 계산할 때, 작성된 글 맨 마지막부터 그리디 알고리즘 방식으로 생각하면 쉽다. 남은 횟수가 홀수일 경우에는 복붙 방법을 사용할 수 없기 때문에 남은 횟수를 1 줄이고 s초를 더한다. 남은 횟수가 짝수일 경우에는 남은 횟수를..

문제 10000 이하의 자연수로 이루어진 n 길이의 수열에서 부분합이 s 이상이 되는 것 중 최소 길이를 구하는 문제이다. 풀이 이 문제는 1차원 배열의 부분합을 구하여 크기를 비교하고 최소 길이를 구하면 된다. 누적합을 구하면서 해당 위치 이전까지의 부분합 중 s 이상인 경우, 최소 길이를 업데이트한다. 예를 들어 4번째 칸까지 누적합을 구했을 때, s 가 7이라면 최소 길이는 3이 된다. 알고리즘 누적합을 담을 dp list를 n+1 길이로 생성한다. 최소 길이를 담을 ans 변수를 생성한다. for 문을 n 번 돌면서 누적합을 계산한다. 최소 길이에 맞춰 부분합을 계산하고 만약 부분합이 s 보다 작다면 이후에도 더 작을 것임으로 중단해준다. 만약 s보다 크다면 최소 길이를 줄일 수 있다는 의미임으로..

문제 그래프의 정점을 두 집합으로 분할할 때, 인접한 정점끼리 서로 다른 집합에 포함되는 그래프를 이분 그래프라고 한다. 주어진 그래프가 이분 그래프인지 판별하는 문제이다. 풀이 이분 그래프인지 확인하기 위해서 정점들을 두 가지 색으로 칠할 때, 인접한 정점끼리 서로 다른 색으로 칠할 수 있는지를 확인하면 된다. 즉, 인접한 정점이 같은 색이라면 이분 그래프가 아닌 것이다. 예를 들어 a를 노란색(1)으로 칠한다면, a와 연결된 b,c,d를 초록색(2)으로 칠하는 것이다. 그 다음 b,c,d에 연결된 인접한 정점들을 다시 노란색(1)로 칠하다가 이미 다른 색으로 칠해진 정점을 만났을 때, b,c,d와 같은 초록색(2)이 칠해져 있다면 이분 그래프가 아니라고 판별할 수 있다. 반대로 모든 정점들을 방문해도..