ALGORITHM (45) 썸네일형 리스트형 [C/LeetCode] Swapping Nodes in a Linked List Daily LeetCoding Challenge April, Day 4 문제 linked list에서 앞에서 K번째, 뒤에서 k번째 요소를 swapping 아이디어: 직접 탐색 + linear 순회 먼저 linked list안에 몇개의 node가 있는지 확인해야 한다. 그래야 뒤에서 부터 몇번째는 몇번의 loop를 돌아야 하는지 계산 가능하기 때문. 총 n개의 node가 있다고 하면 (n-k+1) 번의 loop를 돌면 뒤에서부터 K번째 요소이다. 이 둘의 값을 바꾸면 된다. 예외 사항 1. K == 0 2. head == NULL 하지만 문제에서 1val; temp = head; index = 1; while (index++ next; val2 = tem.. [C/LeetCode] Valid PalindromeⅡ Daily LeetCoding Challenge April, Day 2 문제: Palindrome 가능 여부 확인 이때 최대 1개의 글자를 삭제 가능하다. 아이디어: Brute Force 문자를 제거할 수 있다는 것은 앞에서 비교할 때는 index+1, 뒤에서 비교할때는 index-1 하는 것이므로 두가지의 가능성이 있다. 따라서 둘 중에 하나가 true라면 palindrome인 것이다. 완성 submission: 44ms / 9.1MB bool checkValid(char *s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end--; } return true; } bool validP.. [C/LeetCode] Search a 2D Matrix Daily LeetCoding Challenge March, Day 30 문제: 2 dimension matrix 안에 target number 존재 유무 bool return 하기 이때 2차원 matrix의 특징 - 각 row는 오름차순 - next row first column value > previous row last column value 아이디어: Binary Search + Brute Force in row search row를 반복문으로 돌면서 첫 번째 value와 값을 비교하고 같으면 return, value > target 인 경우 이전 row에 대해서 값이 있거나 없다는 뜻이므로 그때 binary search 진행 예외 처리: last row 마지막 row는 반복문에 걸리지 않기 때.. [C/LeetCode] Search in Rotated Sorted Array II Daily LeetCoding Challenge March, Day 28 문제 정렬이 되어있는 배열을 (중복 가능) k 번 rotation 돌게 된 상태로 입력 받는다. 이때 몇번 회전되었는지는 모름 이 회전된 배열 안에 target number가 있는지 없는지 판별하는 것이다. 문제는 쉬움 그냥 배열 안에 요소가 있는지 없는지 확인하는 것임 따라서 접근 가능한 알고리즘은 많은데, rotation 된 특성을 활용해서 짜는 것이 문제의 핵심이다. 아이디어: Binary Search 이진 탐색을 쓰는데, 일단 어디서 회전 되었는지 알아야 하기 때문에 배열을 한번 검사해서 회전된 곳을 찾는다. 그 후 배열의 첫번째 값과 target number를 비교하여 어떤 앞 부분, 뒷 부분 중에서 어떤 곳에서 이진 탐색.. [swift/LeetCode] Binary Search 오늘 leetcode가 추천하는 오늘의 문제이다. 근데 쉬워서 특별히 swift로 짜봤다. 문제는 단순히 이진 탐색 구현하는 것 이진 탐색은 값을 범위를 반씩 좁혀가며 찾는 것이기 때문에 O(logN) 의 시간복잡도를 가진다 단 오름차순이든 내림차순이든 정렬이 되어있어야 한다. 따라서 트리 탐색에 유용하게 사용된다. Submission: 372 ms / 14.3 MB class Solution { func search(_ nums: [Int], _ target: Int) -> Int { var start = nums.startIndex var end = nums.endIndex - 1 var mid: Int while (start target) { end = mid - 1 } else { start = .. [C/LeetCode] Arithmetic Slices 뭘 풀지 모를때는 역시 daily 추천 문제를 푸는 것이 좋다 Difficulty: Medium Submission: 177ms/ 6.1MB 여전히 효율이 좋은 코드를 생각하는 버릇이 안들었다. 일단 돌아가면 되지 라는 무지성 코딩 제발 그만해 이러다간 다 죽어 int numberOfArithmeticSlices(int* nums, int numsSize){ int result = 0; int diff = 0; int signal = 1; // 3개부터 시작해서 몇개까지로 이루어진 sequence를 만들 수 있는지 for(int i = 3;i [c/LeetCode] Single Number 1. 첫 번째 아이디어 그냥 배열 돌면서 같은 값이 있는 경우는 flag를 0으로 해서 탈출하고, 같은 값이 없으면 1이 되므로 return 하도록 작성함 아쉽지만 o(n^2)이다. 856ms/ 7.3MB int singleNumber(int* nums, int numsSize){ int a; int flag; for(int i = 0; i < numsSize; i++) { a = nums[i]; flag = 1; for(int j = 0; j < numsSize; j++) { if (a == nums[j] && i != j) { flag = 0; break; } } if (flag) { return a; } } return 1; } 2. 두 번째 아이디어 (빌려옴) XOR 연산자인 ^를 사용하는 것이다.. [c/LeetCode] Median of Two Sorted Arrays 1. 첫 번째 아이디어 일단 아무 생각 없이 배열 동적할당 해서 무지성으로 값을 넣은 다음에 정렬해서 중앙값을 구하자고 생각했음. 근데 돌아가긴 하는데, 애초에 정렬을 버블 정렬을 썼더니 (m+n)^2이 나와서 시간이 85ms / 6.9MB 라는 엄청나게 쓰레기 같은 성능의 코드를 작성해버렸음... 무지성 코딩 멈춰 double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){ int resultSize = nums1Size + nums2Size; int *resultList = malloc(sizeof(int) * resultSize); int index = 0; for(int i = 0;i < nums1Size;.. 이전 1 2 3 4 5 6 다음
