공부중의 블로그

차이값을 주어진 값 이하로 맞추면서, 원래 배열에서 최소 한도로 움직이도록 해야 한다. 그 바꾼 값을 반환하자. ex )[1,4,2,3]target = 1;>> ans :[2,3,2,3]바꾼 양 : 2 >>> ans = 2 ** 솔직히 이 문제는 "최적 값을 구하시오" 그리고 "숫자 상한이 100이다" 에서 - 아 이 문제는 DP구나 가 바로 떠올라서 완전 탐색으로 넘어갈 생각을 했어야 한다. 뭐 그리디 한두번은 해볼 수 있었겠지만 안정적으로 DP를 해놓고 찾았을꺼다. ** 솔루션 : 그리디 솔루션 : 한쪽 끝에서부터 생각해 보자. 한도 내로 맞추기 위해서 1을 움직일까 4를 움직일까?아님 중간으로 맞출까?일단 움직이는 총량은 같다. 어찌됬든, 차이를 그렇게 만들어야 하기 때문. 그럼 그 다음 값이 무엇..

스트링 A를 순서를 유지한채 B 사이사이에 끼워넣는 모든 경우의 수를 출력하자. ex) AB 와 CD의 경우 ABCDACBDACDBCABDCADBCDAB 솔루션: 매 경우에 대해 둘중 한쪽의 첫 문자를 새로운 문자열에 끼워넣는다. 한쪽을 다 썼으면 나머지 한쪽을 전부 넣는다. 양쪽을 모두 썼으면 그걸 출력한다. void printall(unordered_set & res, string A, string B, int iA, int iB, string maker){ if(A.size()==iA&&B.size()==iB){res.insert(maker);return;}if(A.size()!=iA){printall(res,A,B,iA+1,iB,maker+A[iA]);} if(B.size()!=iB){printa..

딕셔너리에 주어진 스트링 중에서 목표 string까지 하나씩 바꾼 시퀀스를 구해야 한다.아래 내용물들이 딕셔너리에 주어진다고 가정할 떄,CAT -> DOG CAT -> COT -> DOT -> DOG 이다 ( 아무거나 구해도 된다 ) 솔루션 : 우선, 두 시퀀스 중 서로 다른 문자는 무조껀 바꿔야 한다. 그 갯수를 N/k개라고 하면, 서로 다른 가능한 조합의 갯수는 2^N/k 개이다. 근데 그 조합들을 순서대로 짠다고 하면 결국 몇 경우가 없을 것 이 아니라.. 오히려 N/k개를 선택하는 조합의 갯수는..!! O(N/k!) 무려 이렇게 된다능.. 조합의 갯수보다 더 많다 ㅋㅋ.. 근데 딕셔너리에 존재하는 것들의 갯수가 한정적이고, 한 경우만 찾으면 되니까,, 각 점에 대해 바꾸는 경우로 생각해 보면 DF..

두 배열이 있을때, 각 배열에서 하나씩 꺼낸 수의 합 중에서 K번째로 작은 원소합을 구해보자. 우선 나이브하게 : N^2 개의 원소가 존재하니 O(N^2) 가 상한이다.( 합을 전부 나열한 뒤, partition select ) 어 이거 근데 문제가 그 양방향 정렬 된 행렬에서 K번째 찾기랑 문제가 같네..!! 4 7 8 11 135 9 15 19 21 9 12 13 16 1812 16 22 26 2813 17 23 27 2916 20 26 30 3218 22 28 32 34 있으면, 이렇게 양방향 증가하는 수열은 왼쪽 끝 아래에서 시작해서, 는 아니였음.. ㅠㅠ 새롭게 관찰하니, 대각선 내의 순서는 정해지지 않지만, 대각선 단계별로 무조건 순서는 강제된다. 왜냐면 좌우 증가기 때문에 대각선 레벨이 달라..

13 * 29 : 13*13 2개, 3*3 4개 1* 1 3개 = ans : 9 풀이 : 아무래도 짧은 변을 한 변으로 하는 정사각형을 긴 쪽으로 할 수 있는 만큼 만든 후에, 남은 길이를 재귀적으로 호출하면 된다.base case는 한쪽 길이가 1이면 조각의 수는 긴 쪽 길이이다. int findsquares(int M, int N){// base caseif(N==1) return M;// general caseint count = M/N;return count + findsquares(N,M%N);} 시간 복잡도 .. O(log 루트N) 쯤 되지 않을까? 작은 것 보다 작게 만드니까 작은 것으로 만든다고 가정하면 대략 logN이고..

0과 1로 구성된 N*N 행렬이 있다. 여기에서 가장 큰 십자가 모양을 찾아보자. 1 1 111 1 1 (대칭적이고 너비가 1인 십자가) 풀이 : preprocessing을 하면 빠르다.각 점에 대해 동서남북으로 이어진 길이를 가진 행렬 4개를 만든다.만드는 방법은, 현위치가 0이면 전부 0현위치가 1이면 동서남북의 인접한 값 + 1각 점은 한번씩만 채워질꺼라 O(N^2) 그리고 그 값을 기반으로 한 점에서의 가장 큰 십자가는 4개의 값 중에서의 4*(최솟값-1) 이다. https://www.careercup.com/question?id=5678853664014336

처음에는 3또는 5만 소인수로 갖는 것들의 합 구하기로 생각해서, 3의 거듭제곱 중 가장 작으면서 큰거 i, 5의 거듭제곱 중 가장 작으면서 큰거 j 라고 하면 (i,j) 2중 for 루프의 모든 숫자들 중 N 보다 작은 것들을 전부 더해나갈 생각이었다. 갯수는 log^2N 이고 각각에 대해 합을 구하는건 단계별로 3씩 곱해나가는 셈이니까 1이 걸려서 총 시간 복잡도는 O(log^2N) 쯤 되겠다. --- 근데 이 문제는 "3 또는 5의 배수" 이기 때문에.. 10 이면 3 6 9 = 185 = 5tot : 23 매우 자명하게 3 total = N/3 * (N/3*(N/3+1)/2)5 total = same but 5그리고 이 둘의 합을 하면 중간에 15의 배수가 겹치므로15 total = same bu..

struct Node {int val; vector children;} 솔루션 : recursive 는 원래꺼랑 거의 같다.class Node{ ArrayList children; int val; } public static ArrayList getPostOrder(Node root){ ArrayList results = new ArrayList(); if(root == null){ return results; } for(Node child : root.children){ results.addAll(getPostOrder(child)); } results.add(root); return results; }iterative는 스택을 사용하는 듯 이건 preorder인데 inorder이나 postorder은..

행렬은 행과 렬이 정렬되어 있고, 0 또는 1만 들어갈 수 있다.0의 갯수는? ex ) 0 0 10 1 11 1 1>> ans : 3 유명한 숫자찾기 문제처럼, 왼쪽 아래서 시작해서 0을 만날때까지 위로 올라가다가, 0을 만나면 오른쪽으로. 다시 위로 ... 이런 식으로 가면서 0의 갯수를 센다. 현재 위치가 행렬을 벗어나면 그만 세고 종결한다. O(N)

배열 내의 어느 숫자에 대해 그 왼쪽의 숫자들은 더 작고, 오른쪽의 숫자들은 더 큰 숫자들을 찾아보자. BST 2개를 만들어서 서로 주고 받는다 >> O(NlogN) 저번에 사용했던 min(max) 값 추적할 수 있는 스택을 사용하면..!!O(N) 알고리즘을 얻을 수 있다. 재귀적으로 해결 가능하다고 합니다 FindElement(int[] arr, int MaxTillNow, int currentIndex) { if(currentIndex == 0) { return FindElement(arr, arr[currentIndex], currentIndex + 1); } if(currentIndex == arr.Length-1) { return arr[currentIndex]; } int minTillNow ..