본문 바로가기

Algorithm things13

[Leetcode/Easy] 9. Palindrome Number 앞 뒤가 똑같은 경우 ture를 다른 경우 false를 output으로 출력 해 주는 문제다. 문제를 보고 엉뚱하게 stack이 먼저 생각났다. 깊이 생각안하고 바로 풀었던 솔루션은 다음 과 같다. char 배열에 값을 넣어두고 중간까지만 stack에 넣은 뒤 pop되는 값과 array 값을 비교해 준다. class Solution { public: bool isPalindrome(int x) { char v = 0; char arr[10] = {0, }; int arr_len = 0; if (x < 0) return false; while ( true ) { v = x % 10; x /= 10; arr[arr_len++] = v; // 1 / 10 == 0; if ( x == 0 ) break; } /.. 2021. 11. 10.
[LeetCode/Easy] 13. Roman to Integer - 문제풀이 쉬운 문제임에도 불구하고 이상한데서 디버깅을 하다가 엄청난 시간을 소비했다. 요새 정말 코드를 생각없이 짜 왔구나 라는 것을 느끼게 해 준 문제.. class Solution { public: int romanToInt(string s) { auto len = s.length(); auto sum = 0; for ( int i = 0; i < len; i++ ) { auto v = 0; if ( s[i] == 'I' ) { if ( i + 1 < len ) { if ( s[i+1] == 'V' ) v = 4; else if ( s[i+1] == 'X' ) v = 9; } if ( v == 0 ) v = 1; else i++; } else if ( s[i] == 'V' ) v = 5; else if ( s.. 2021. 11. 6.
[Leetcode] 696. Count Binary Substrings 문제: leetcode.com/problems/count-binary-substrings/ DFS 끄적거리다가 못풀었다. Easy인데.. 착찹한 심정으로 Solution 해설이나 해본다. Solution은 Leetcode 사이트에 있다. Intuition We can convert the string s into an array groups that represents the length of same-character contiguous blocks within the string. For example, if s = "110001111000000", then groups = [2, 3, 4, 6]. For every binary string of the form '0' * k + '1' * k or .. 2021. 4. 27.
59. Spiral Matrix II 이번에는 재귀호출을 쓰지 않고 Loop로 풀어봤다.. 메모리를 좀 많이 쓰는 코드인데, 자료형을 조금 손 보거나 map을 만들지 않는 방법도 개선점으로 둘 수 있을 것 같다. class Solution { int map[20][20]; int direction[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; public: vector generateMatrix(int n) { vector r; int cur_x = -1; int cur_y = 0; int marker = 1; int last_marker = n * n; while( marker = n || cur_x = n || map[cur_y][cur_x] != 0) { cur_y = cur.. 2021. 4. 1.
[Algorithm] Karatsuba algorithm 큰 수를 곱해야 하는 상황에서 카라추바 알고리즘이 최적화에 많이 이용 된다고 하여... 문제풀이에 필요할 것 같아 정리해 둔다. 아래는 위키에 적혀있는 내용이다. 인터넷에 보면 예시가 많은데... 나도 이해를 해야하니 하나의 예시를 적어보려 한다. 예를들어, 1234 * 4321 을 곱해야 하는 상황이라 하면 아래와 같이 풀어서 적을 수 있을 것이다. 1234 * 4321 을 구해야 한다. 1234 = 12 * 100 + 34 4321 = 43 * 100 + 21 이 수식을 다시 정리하면 (12 * 100 + 34 ) * ( 43 * 100 + 21 ) = 1234 * 4321 = ( 12 * 43 ) * 10000 + ( 12 * 21 * 34 * 43 ) * 100 + 34 * 21 * 1 여기서 1.. 2021. 3. 31.
[LeetCode] 54. Spiral Matrix 여전히 쓸데없는 실수가 잦다. 재귀를 이용했고, 방문 지점을 음수로 덮어서 처리하려그랬는데, matrix에 값이 -100~100 까지인지를 안보고 했다가 Submit 한번을 날렸다. 그 외에도 놓친 부분이 많았다. 재귀를 써도 되고, 메모리를 줄이고 싶다면 for loop도 충분히 가능한 문제로 보인다. class Solution { vector result; int direction[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; int cur_direction = 0; public: void dfs ( int y, int x, vector& matrix ) { result.push_back(matrix[y][x]); matrix[y][x] = -999; int nex.. 2021. 3. 30.
[LeetCode] LeetCode 풀이를 할때 IDE를 써야할까 다른 Online Judge 를 사용할때 (정올, 백준, dovelet 등) 보통 IDE에 코드를 복사해서 빌드하고 Debugging을 했었다. 처음 LeetCode라는 Online Judge 를 접했을때, 습관적으로 코드를 IDE에 복사하고 시작했는데, Class밖에 없어서 조금 당황했던 기억이 있다. 그때는 내가 이 Class constructor를 만들어서 임시객체를 생성하고 호출해 줘야하나? 라는 생각을 했던 것 같다. LeetCode내에 따로 매뉴얼이 있을 것 같다는 생각이 드는데, 일단은 왠만한 디버깅 가능한 환경은 제공해 주고 있다. C++을 주로 사용하는데 std::cout / std::endl 모두 동작한다. 따로 헤더를 붙일 필요도 없다. 원하는 출력을 run code해보면 나타내기 때.. 2021. 3. 27.
[LeetCode] Weekly Contest 234 LeetCode 환경을 이해해 보기 위해서 첫 Weekly Contest를 기다리고 있다. 내일 시작한다고 하는데, Important Note를 읽어보면 몇가지 제약은 있는 것 같다. - New Contest Rule : leetcode.com/discuss/general-discussion/951105/new-contest-rule-effective-from-december-2020 제출을 여러번 하면 서버 부하가 있을 수도 있어서 그런건지 5분 제약이 있고, 일부 test case는 공개하지 않는 것으로 보인다. 사실 테스트 케이스는 문제에 주어진 제약조건을 보고 유추해 내는 것도 어느정도 실력이라고 판단하는 지표가 아닐까 싶다. 퇴근할때마다 하나씩 풀어보겠지만.. 얼마나 풀 수 있을지는 잘 모르겠다.. 2021. 3. 27.
[LeetCode] 62. Unique Paths 전형적인 DP 문제의 입문. Memoization을 위한 dp_map을 만들어 놓고 이미 방문한 경로에서 계산 된 Path 갯수를 저장해서 사용한다. class Solution { int dest_x, dest_y; int dp_map[100][100]; public: Solution () : dest_x (0), dest_y (0) { for( int i = 0; i < 100; i++) for( int j = 0; j < 100; j++) dp_map[i][j] = -1; } int dfs ( int y, int x ) { if ( y == dest_y - 1 && x == dest_x - 1 ) return 1; int rr = 0; int rd = 0; // move right if ( x + 1.. 2021. 3. 27.
[LeetCode] 6. ZigZag Conversion 실수가 좀 잦은 것 같다. numRows 내에서 첫줄과 마지막줄은 고정 크기만큼 jump 가 가능하며 그 중간에서의 Jump size만 계산하면 되는 문제다. 근데 Jump Size가 0으로 나오는 경우를 처리하지 않아서 제출횟수를 좀 날렸다. class Solution { public: string convert(string s, int numRows) { // ( numRows - 2 ) * 2 // 3 : 4, 2, 4 // 4 : 6, (4,2,4,2.. ), (2,4,2,4...), 6 // 5 : 8, (6,2,6,2...), (4,4,4,4..), (2,6,2,6...), 8 int std_gap = ( numRows - 2 ) * 2 + 2; // standard gap int input_.. 2021. 3. 26.
[LeetCode] 5. Longest Palindromic Substring 대충 30분 가량 소요.. substr에 length에 문자열 연산을 마구잡이로 쓰다보니 TLE 무지막지하게 났다. 게다가 stack을 써서 push pop 하면서 LPS 를 판단했었는데 굳이 왜그랬나 싶다. 좌 우 index를 가지고 비교하도록 개선하다 보니 성능이 점점 나아졌다. class Solution { public: string longestPalindrome(string s) { auto size = s.length(); string lps; int max_length = 0; for ( int i = 0; i 0; j--) { if ( s[i] .. 2021. 3. 25.
[LeetCode] Add Two Numbers 코드가 좀 길지않나 싶다. 줄이기는 또 귀찮고.. 문제를 제대로 안읽고 그냥 다 더해서 리스트를 만들라는건가 싶었는데 node 개수가 1~100 개라고 하니 그것은 아닌 것 같고, Node를 방문하면서 계속 만들어 내야할 것 같았다. 한 노드에 저장되는 수는 0~9 이기에 Carry 는 1이상 나오지 않는다고 생각했다. Constraints: The number of nodes in each linked list is in the range [1, 100]. 0 val + carry; if ( v >= 10 ) { v %= 10; carry = 1; } else if ( carry != 0 ) { carry = 0; } if ( l3 == nullptr ) { l3 = new ListNode(v); l3.. 2021. 3. 21.
[LeetCode] Two sum 손풀기용. 매일 한 문제 씩 풀어나갈 수 있었으면 좋겠다. 보통 LeetCode쓰는사람이 IDE에서 로컬로 따로 푸는지 아니면 그냥 페이지에서 바로 푸는지 조금 궁금하다. 클래스 써서 필요한 Test case를 넣을 수야 있지만.. 조금 귀찮기도 하고.. 그냥 브라우저에서 푸는게 최선이일련지.. class Solution { public: vector twoSum(vector& nums, int target) { auto v_size = nums.size(); int idx1, idx2 = 0; for ( int i = 0; i < v_size-1; ++i ) { for ( int j = i + 1 ; j < v_size; ++j ) { int sum = nums[i] + nums[j]; if ( sum.. 2021. 3. 21.

티스토리툴바