LiDARism

Sum of Two Integers - LeetCodeBinary operation을 사용하는 기본 문제라고 한다. Given two integers a and b, return the sum of the two integers without using the operators + and -.Example 1:Input: a = 1, b = 2 Output: 3Example 2:Input: a = 2, b = 3 Output: 5첫 시도하지만 역시 또 time limit에 걸려버렸다. 역시 나야!class Solution: def getSum(self, a: int, b: int) -> int: while b != 0: _and = a & b _x..

Climbing Stairs - LeetCode Dynamic Programming 문제 중 가장 쉬운 버전이다. 70. Climbing StairsYou are climbing a staircase. It takes n steps to reach the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Example 1:Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 stepsExample 2: Input: n = 3 Output: 3 Explan..

Best Time to Buy and Sell Stock - LeetCodeYou are given an array prices where prices[i] is the price of a given stock on the ith day.You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.이번에는 최대 이득을 볼 수 있는 주..

문제 링크: https://leetcode.com/problems/two-sum/description/ 문제는 다음과 같다.Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.complement 만드는 것 제외하면 별 방법이 떠오르지 않아서 그냥 brute force처럼 했는데, e..

Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not). Example 1: Input: s = "abc", t = "ahbgdc" Outpu..

뭔가 이름이 멋있는 알고리즘이다. O(N + M)의 시간 복잡도 특정한 상황에서 KMP 알고리즘보다 매우 느리게 동작한다고 한다. 사실 그럴만도 한 것이 일단 hash함수를 써야하고, hash값이 같은 부분이 많으면 check하는 함수를 써야하니... 그래도 내 머리보단 빠르지 않을까? 설명은 이 분의 블로그가 좋겠다. blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240679247&redirect=Dlog&widgetTypeCall=true&directAccess=false #include #include char * parent = "acabacdabac"; char * pattern = "abacdab"; // 같은 문장인지 확인하는 함수 void che..

O(N + M)의 시간복잡도의 알고리즘이다. matching 전에 접두사와 접미사가 일치하는 최대길이를 기록하는 table을 만들어 이용한다. 알고리즘이 다소 복잡하게 느껴질 수 있으니 설명을 찾아보는 게 좋을 듯하다. 그런데 알고리즘에 대한 설명은 나보다 이 사람이 더 잘하지 않을까? bowbowbow.tistory.com/6 #include #include #include char * parent = "acabacdabac"; char * pattern = "abacdab"; int * makeTable(char * pattern){ int patternSize = strlen(pattern); int * table = (int *)malloc(sizeof(int) * patternSize); for..

컴퓨터가 2의 보수를 이용하는 것을 이용할 것이다...? 2의 보수, 1의 보수에 관한 좋은 설명이 있는 블로그 링크 ndb796.tistory.com/tag/2%EC%9D%98%EB%B3%B4%EC%88%98 오타쳐서 런타임 에러가 났었고 찾아서 해결했다.. 아래는 예시 코드다. #include #define NUMBER 7 int tree[NUMBER]; int sum(int i){ int res = 0; while (i > 0){ res += tree[i]; i -= (i & -i); // i = (i & -i); // 오타쳤음. 이 경우 계속 i = 1이라서 영원히 안끝난다... 오버플로우까지 } return res; } void update(int i, int dif){ //i index에 di..

구간 합을 구하는데 좋은 알고리즘 중 하나이다. O(N)의 시간복잡도. 이마저도 비효율적이라 생각하는 알고리즘에 미친자들... 결국 트리를 이용해서 시간복잡도를 O(logN)으로 축소시킨다. #include #define NUMBER 7 // data의 개수 int a[] = {7,1,9,5,6,4,1}; int tree[4*NUMBER]; // 4를 곱해서 모든 범위를 커버한다...라고 하는데 그냥 높이를 곱한 것. // start : 시작하는 인덱스, end : 끝나는 인덱스 // node : 사실 그냥 1이 들어간다...만은 원래는 특정 노드에 특정 값이 들어가게 하기 위해 따로 파라미터로 내놓는다. 즉, 재귀함수로 사용하기 위해 존재하는 파라미터. main에서의 용도는 root node를 지정해주..

동작 원리가 프림 알고리즘과 흡사. 아래 설명 코드에선 main 함수에서 차이가 난다. 프림 알고리즘과의 차이점은 간선의 '가중치'가 아닌 간선의 '이동거리'를 중심으로 판단한다는 점이다. 즉 기존 이동했던 노드를 거쳐간다는 가정하에 '이동거리'를 계산하고 이를 통해 Table을 갱신한다. 기존의 테이블을 매번 새로 갱신하는 특징이 있다. 우선순위 큐를 이용해서 구현한다. 프림 알고리즘과 같이 시간복잡도 O(ElogV) #include #include #include #define NODE_MAX 1001 #define EDGE_MAX 600001 // 양방향 간선이므로 300000개를 고려 // Node가 Edge를 참조, priorityQueue가 Edge의 cost를 중심으로 최소값이 pop되게 구..