ALGORITHM/c&c++ leetcode (22) 썸네일형 리스트형 [C++/LeetCode] Game of Life Daily LeetCoding Challenge for April, Day 12 문제 2차원 vector의 값을 규칙에 맞게 변경하기 아이디어 2차원 vector를 돌면서 이웃한 cell 중에서 몇개의 1이 있는지 확인한 후, 값을 정한다. 완성 submission: 6ms / 6.9MB class Solution { public: void gameOfLife(vector& board) { int row = board.size(); int col = board[0].size(); vector result(row, vector (col, 0)); for(int i = 0;i < row;i++) { for(int j = 0;j < col;j++) { int sum = 0; for(int n = i - 1;n.. [C++/LeetCode] Kth Largest Element in a Stream Daily LeetCoding Challenge for April, Day 8. 문제 배열에서 k번째로 큰 수를 찾음. 이때 add() 함수를 구현하여, 이 함수의 인자로 int 값을 주었을 때 배열에 추가하고 추가한 배열에서 k번째로 큰 수를 반환하도록 구현 아이디어: Heap(priority queue) k번째로 큰 수를 찾는 것이므로, k+1번부터 큰 수는 필요하지 않다. 즉 배열에서 없어도 된다.또한 k번째로 큰 수를 찾는 것이므로 오름차순으로 정렬한 배열이 필요하다.이 조건을 쉽게 만족하는 자료구조는 바로 Heap이다. Heap 1. complete binary tree2. 모든 노드의 값은 자식보다 크거나 같다. (max heap), 작거나 같다.(min heap) Heap은 위의 특성을 만족.. [C/LeetCode] Container With Most Water Daily LeetCoding Challenge April, Day 5 문제 높이가 배열로 주어졌을 때, 만들 수 있는 가장 넓은 사각형 영역의 크기 구하기 (width = 1로 고정) 아이디어: brute force 이중 배열을 돌면서 두개의 index를 선택하고 이를 통해 만들 수 있는 사각형의 크기와 max 값을 비교함 완성: time limit exceeded 눈물이 나게도 시간초과가 발생했다. int min(int a, int b) { return a height[.. [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 = .. 이전 1 2 3 다음
