CodeAngie

문제 새로운 언어로 암호화된 문장을 해석하는데 드는 비용의 최솟값을 구하는 문제이다. 이 문장은 연속된 단어의 연결로 이루어져 있으며, 단어는 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보다 크다면 최소 길이를 줄일 수 있다는 의미임으로..

배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘이다.배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다.미리 구해둔 누적합을 통해 배열 중 특정 구간의 부분합을 쉽게 구할 수 있다.값을 미리 저장해 두는 점이 DP와 유사하다.배열의 값들이 변하지 않음1. 1차원 누적합 알고리즘1.1. 1차원 누적합그림과 같이 앞에서부터 차례대로 누적된 합계를 prefixSum 배열에 저장한다.첫 번째(0) 값은 arr 값과 prefixSum 값이 동일하다.현재 위치(i)의 arr 값에 prefixSum 배열에 저장된 직전 위치(i-1)까지의 합을 더하여 현재 위치의 누적합을 구하여 prefixSum에 입력한다.점화식은 다음과 같다.prefixSum[i] = prefixSum[i-1] ..

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

인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..

문제 각각의 일을 끝내는 데 걸리는 시간(일)이 담겨 있는 A 배열이 주어졌을 때, 일의 순서를 바꾸어 헬스장에 갈 수 있는 경우는 YES, 갈 수 없다면 NO를 출력하는 문제이다. 문제 조건 오늘은 월요일이다. 금요일에 일을 끝내야 헬스장에 간다. 풀이 일주일은 7일이기 때문에 월요일부터 일요일을 0에서 6으로 둔다. 월요일에 일을 시작해서 금요일에 끝나려면 7로 나누었을 때 나머지가 4인 날이 있는지 확인하면 된다. 따라서 숫자의 조합에 따라 합계를 7로 나눈 나머지가 4가 되는 경우가 있는지 살핀다. 시간에 대한 연산과 나머지에 대한 연산의 결과가 같다는 것을 활용한다. ex) (15+ 9) % 7 = (1 + 2) % 7 = 3 A 배열의 요소(a)들을 모두 순회하면서 먼저 계산된 나머지와 연산을..