CodeAngie

문제 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)들을 모두 순회하면서 먼저 계산된 나머지와 연산을..

문제 상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다. 풀이 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다. 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (LIS) 을 구한다면, 겹칠 수 있는 최대 상자의 개수를 알 수 있다. 알고리즘 겹치는 상자의 개수를 담는 dp 를 1로 초기화한다. 상자의 크기가 담긴 box 배열을 순회한다. 해당 상자의 이전에 있는 상자들과 비교하면서 담을 수 있는 상자라면, 이전 상자에 담기는 상자의 개수(dp[j])에 1을 더한 값과 현재 dp[i]에 담긴 값을 비교하여 더 큰 값을 d..

딥러닝 모델을 학습시킬 때 학습 진척도(progress bar)를 살필 수 있는 방법으로 tqdm 패키지가 사용된다. 1. tqdm 패키지 설치!pip install tqdm 2. 기본 예제기본적으로 tqdm에 iteration이 가능한 객체를 입력하면 된다.  tqdm(range(10))from tqdm import tqdmimport timen = 10for i in tqdm(range(n)): time.sleep(1)다른 설정이 없다면 progress bar는 진행도와 시간이 표시된다.진행도(%) | 완료 횟수(i) / 전체 반복 횟수(n) [현재까지 걸린 시간  3. 옵션1) 많이 사용되는 옵션: desc, postfix, unitdesc는 progress bar의 prefix(전위표기법)으..