1149 RGB 거리 알고리즘(dp) 1. 그냥 현재 노드에서 이전의 상태가 X였을때의 최솟값을 저장하는 dp 배열 DP[1000][3] 을 선언하고 DP를 해주면 된다. 2. 첫번째와 마지막이 상관이없으므로 매번 값을 초기화 시켜줄 필요는 없다. 코드 #include <iostream> #define INF 2000000000 u...

11437 LCA 알고리즘 (BFS, LCA) 1. 트리만들기 1. check 배열을 만들고, 1번 노드만 true 표시함 2. 정점 쌍이 들어왔을 때, 둘중에 check 표시된 것이 A, 안된 것이 B라고 할때, B의 부모엔 A를, 깊이엔 A+1을 넣고, check[B] 에 true 표시함 3. true 표시가 끝나고, B에 인접한 정점들을...

11401 이항계수 3 알고리즘(페르마의 소정리, 거듭제곱) 1. 페르마의 소정리 적용 nCk = n! / k!(n-k)! % 1000000007 에서 A = n!, B = k!(n-k)!, p = 1000000007 이라고 할 때 위 식은 (A * B^(-1)) % p 를 성립 페르마의 소정리는 p가 소수일때, p와 서로소인 a가 있으면,...

1107 리모컨 알고리즘(브루트 포스) 1. 0~100만까지 하나씩 올라가며, 되는지 검사하고, 가장 적게 누르는 건지 저장 2. 되는지 검사할 때는, 고장난 버튼을 bool 배열에 저장하여 바로바로 참조가능하게 하고, 뒤에서부터 하나씩 검사하자 헛발질 기록 1. 처음엔 들어온 버튼의 자릿수에 맞게, 모든 숫자를 검사하되 재귀로 수를 하나씩 ...

11066 파일합치기 알고리즘(DP) 1. 긴 한 줄의 파일들을 두조각으로 분리해서 찾는 방식으로 DP를 함 2. 먼저 0, k-1를 넣음 3. (0, k-1)의 파일 크기의 합을 구한 후, (0,0)-(1,k-1), (0, 1)-(2,k-1) ... 로 모든 두 조각을 만든 후, 그 조각의 비용을 구함 -> start == end 일 경우...

11054 가장 긴 바이토닉 부분수열 알고리즘(LIS) 1. 왼쪽에서 오른쪽으로 LIS, 오른쪽에서 왼쪽으로 LIS 후, 모든 점에 대하여 l[i] + r[i] - 1 (길이가 1이면 1일때, 0일경우는 + 1 해줌) 가 최대가 되는 점을 찾고 그점에서의 l[i] + r[i] -1 를 출력하면 됨. 2. 길이가 최대1000이므로 dp로 안해도 ...

11049 행렬곱셈순서 알고리즘(DP) 1. 연속된 원소를 크게 이등분하여 계산할 수 있음 ex) (start ~ i, i+1~end) 2. dp(start, end)는 start에서 end까지의 범위를 계산할 때 최소비용. 3. 현재 비용은, matrixt[start][0]*matrix[i][1]*matrix[end][1] 로 계산할 수 있음. ...

10942 Palindrome 알고리즘(DP) 1. 입력으로 받은 것이 팰린드롬인지 확인 2. 팰린드롬이면 from-to 사이에 있는 모든 건 다 팰린드롬이다. -> DP에 팰린드롬임을 표시 아니면, from-to에서 팰린드롬이 아님을 판별한 곳까지 팰린드롬이 아니다 -> DP에 팰린드롬이 아님을 표시 주의점 아무리 잘 짜도 i...

10830 행렬제곱 알고리즘 (거듭제곱, 행렬곱) 1. 그냥 행렬 거듭제곱으로 풀면됨 주의점 1. 입력의 B를 long long으로 받아야한다 2. AB = A 가 나오도록 하는 B행렬은 대각선이 모두 1이고 나머지는 0인 행렬이다 코드 #include <iostream> #include <cstring> using...

10775 airport 알고리즘(자료구조, 트리를 이용한 이진탐색) 1. 게이트의 개수에 맞게 1~G를 set에 넣음 2. bool형 check 배열에서, gi에 아무것도 없으면 gi에 넣고 set에서 gi 삭제 3. 이미 gi에 들어가 있으면, set에서 upperbound로 gi초과하는 첫번째를 찾음 -> 만약 그 첫번째가 begin...