목록전체 글 (179)
有希
백트래킹은 항상 어렵다. 익숙하지 않아서 인듯 아래에 설명이 잘 되어있다. https://leetcode.com/problems/permutations/discuss/1961596/C%2B%2B-oror-Easy-to-Understand-with-Diagram-oror-0-ms-oror-Backtracking 눈여겨 보아야 할 점은 j는 i부터 시작이라는 점이다. 즉, 자기자신과 swap을 함으로써 모든 경우를 포함시킨다. 123을 생각해보면 for 루프를 돌면서 123 213 321 을 tracking함수에 num으로 넘기고 i는 1이 된다. 123을 생각해보면 j=i, 즉 1인 상태에서 swap 123 2인 상태에서 132 가 된다. 이제 i를 2로 만들어서 넘기면 if문에 의해 123 132가 re..
문제에서 O(log n) 이라고 했으니 이진탐색으로 풀어야 한다. 가장 작은 idx와 가장 큰 idx 를 골라내어야 한다. 가장 작은 경우: mid값이 target보다 크거나 같다면 right를 mid-1로 지정하고, 아니라면 left를 mid+1로 지정한다. 이 이유는 같은 경우에도 왼쪽에 더 작은 값이 있는지 봐야하기 때문이다. 가장 큰 경우: mid값이 target보다 크다면 right를 mid-1로 지정하고, 아니라면 left를 mid+1로 지정한다. 이유는 left right가 겹칠때까지 전부 찾은다음 target의 가장 큰 idx를 찾아야 하기 때문이다. if문에서 같으면 무조건 갱신하는 것 또한 중요하다. class Solution { public: vector searchRange(vect..
이 문제는 세번째 접하는건데, 아예 이 풀이로 머리가 굳어서 다른 풀이로 풀려고 하면 몸에서 사리가 나온다... 1. 첫번째와 두번째 Node중 작은 값을 시작값으로 정한다. 2. 두 노드중 작은 쪽의 값을 계속해서 이어 붙인다. 3. 두 노드 중 한 쪽이 먼저 끝나면 남은 쪽을 쭉 이어 붙인다. 임베디드 관련해서 메모리를 한톨이라도 더 아끼려면 양 쪽의 노드에서 값만 추출해오고 추출당한 녀석은 delete로 밀어버리거나 하는 최적화가 생각나는데, 데스크탑 환경에서는 굳이? 싶다. SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) { //list1 pointer SinglyLinkedListN..
외국인의 풀이. 잘 짜여져 있다. 철근 콘크리트 같은 느낌. 재귀는 익숙한 dfs가 아니면 언제나 어렵다. 1. 재귀 풀이에는 항상 기저 조건이 필요하다. 기저 조건은 길이가 1이면 그대로 return한다. (문제에서 말하는 super) 2. sum을 준비한다. 오버플로우 대비해서 long 선언 3. 주어진 문자열 숫자들의 합을 구한다. 그 이후 k만큼 곱해주면 된다. 굳이 문자열을 k만큼 곱해서 늘린다음 순회할 필요가 없다. 이 부분에서 깨달음을 얻었다. 4. 그리고 다시 long을 string으로 변환해서 재귀호출한다. int superDigit(string n, int k) { if(n.length() == 1 && k == 1) return n[0] - '0'; long sumN = 0; for(..
n x n 행렬이 주어진다. 1. 행 단위로 정렬하고 2. 모든 '열'이 알파벳 순 정렬돼 있는지 확인해서 하나라도 안 돼 있다면 "NO" 반환 아니라면 "YES" 반환한다. 아무리 쉬운 문제라도 처음 보면 해석에 조금 시간이 걸리는건 어쩔 수 없나보다. 피아노 초견도 연습안하면 어렵듯이... string gridChallenge(vector grid) { //arrange row for(int i=0; i
나는 %연산으로 했었는데, 다른 사람들의 코드를 보다보니 깔끔하고 군더더기 없는 코드가 있었다. 앞으로 이런 류는 이렇게 풀어야겠다 string caesarCipher(string s, int k) { k = k % 26; for(int i = 0 ; i = 65 && s[i] 90) s[i] -= 26; s[i] += k; } else if(s[i] >= 97 && s[i] 122) s[i] -= 26; s[i] += k; } } return s; }
두 가지 어려움이 있다. 영어 그리고 알고리즘 문제 -_- 2명이 번갈아가며 수행하고 항상 1번이 먼저 한다. 1번은 타워의 높이의 약수만큼 덜어내거나 높이가 1이 되도록 덜어낼 수 있다. 1,2번이 번갈아가며 수행할 때 자기 차례때 모든 타워의 높이가 1인 상태이면 패배한다.(타워 높이 1을 만들면 그 타워는 더이상 건들지 못한다) 예외 사항부터 처리한다. 모든 타워의 높이가 1이라면? 처음 시작이 1번이고, 더이상 덜어낼 수 없으므로 2번 승리 타워의 개수가 짝수개이다 -> 타워 개수 2개 놓고 생각해보면 된다. 무조건 2번이 이긴다. 모든 타워의 높이가 같으므로 짝짝 홀홀만 고려하면 된다. 마찬가지로 홀수개이다 -> 무조건 1번이 이긴다 이를 코드로 옮기면 다음과 같다. int towerBreake..
고친 부분: int mid = (n+1)/2; int ed = n - 1; ed = ed + 1; 1 2 3 4 5 6 7 8 9 10 11 을 생각해보자 일단. mid를 저렇게 정하면 한 칸 오른쪽으로 가버린다. 그리고 mid와 끝을 바꾸면 1 2 3 4 5 11 7 8 9 10 6 이 된다. 아래 while을 보면 swap해주고 있음을 알 수 있다. 문제처럼 바꾸려면 6은 냅두고 7 10을 바꾸고 8 9를 바꾸면 된다는 걸 음...한 번 코드를 따라가보면 잘못된 코드지만 직관을 얻을 수 있다. 그러면 어디를 수정해야 할지가 뻔히 보인다. 처음 int ed를 정하는 부분에서 n-1을 하면 6이 걸리니 n-2로 해줘야 하고, 바꿀 때마다 st는 한 칸 오른쪽으로 ed는 한 칸 왼쪽으로 가야 함을 알 수 ..
Day 2 Interview Questions Mock Test . 행렬의 행과 열을 이리저리 회전시키고 1/4로 쪼갰을 때의 좌상단의 위치한 녀석의 최대 합을 구하는 문제. 처음에는 못 풀었다. 두번째 시도에 풀었다. 4x4 행렬을 생각했을 때, 0번째 '열'을 뒤집고 나면 3,0에 위치한 녀석은 다시 못 쓸것이라 생각했다. 근데 그게 아니고 3번째 행을 뒤집고 4번째 열을 뒤집고 다시 2번째 행을 뒤집으면 원래 1,0에 위치한 녀석을 다시 원래 위치로 돌릴 수 있다. 큐브를 좀 했던 사람이라면 쉽게 풀었을거 같지만 나는 큐브를 진짜 싫어했었어서 저 직관을 얻기까지 꽤 고전했다. 즉, 어떤 위치 [i,j]에 위치한 원소의 최대값은 다른 녀석들에 종속적이지 않다. 독립적으로 구할 수 있다는 직관을 믿고 ..