알고리즘(172)
-
[LeetCode] [Medium] Longest Substring Without Repeating Characters
1. Problems Given a string. Find max length of substring without repeating characters. 2. sol I check all ascii for int array. Visited array has index of first finded index. and if find repeating char, Initialize all elements in front of first fineded index. This time complexity is O(N) because inner for statement operate total maximum n. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..
2021.03.18 -
[프로그래머스] [C++] 가장 큰 수 (sort)
1. 문제 정수가 담긴 배열이 주어진다. 이 정수를 전부 문자열로 덧붙인다고 할때 숫자가 최대가 되게 하여라. 2. 비교함수 작성 이 문제는 비교함수에서 정수를 to_string으로 문자열로 변환하고 문자열을 + 연산하여 사전순으로 큰지 작은지 비교할 수 있다. 이는 아스키 코드상에서 문자 '0' ~ '9' 의 상대적 크기가 숫자 0 ~ 9 와 같기때문에 가능한 일이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include using namespace std; bool comp(const int& a, const int& b) { string sa = to_string(a), sb = to_string(b); re..
2021.03.18 -
[LeetCode] [Medium] Add Two Numbers (linked list)
1. Problems Given two num list Add the two numbers and return the sum 2. Sol I use triple pointer for update double pointer. Becuse double pointer have address of answer list and I don't want to change value of answer list. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 /** * Definition for singly-linked list. * struct ListNode { * int val; * L..
2021.03.17 -
[프로그래머스] [C++] 정수 삼각형 (dp)
1. 문제 정수로 이루어진 삼각형에서 맨끝에서부터 맨아래쪽 까지의 경로들에서 거쳐간 숫자의 합중 최대값을 구하여라 2. Iterative Dynamic Programming 이 문제는 삼각형의 제일 맨 아래부터 두개의 수중 큰 수를 바로 위의 정수에 더하면 자연스럽게 triangle[0][0]에 가장 큰값이 들어가게 된다. 이것은 반복적 동적계획법으로 재귀적으로도 풀수있지만 메모리가 좀 더 소비된다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 #include #include using namespace std; int solution(vector triangle) { for(int i = triangle.size()-2; i >= 0 ; i--) for(int j = 0; j
2021.03.17 -
[LeetCode] [easy] Two Sum (brute-force, map)
1. Problem Given: numbers array and target. Select two element and sum, if output is target return these index. 2. brute-force time-complexity of brute-force is O(N^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: vector twoSum(vector& nums, int target) { for(int i = 0; i
2021.03.16 -
[프로그래머스] [C++] 조이스틱
1. 문제 조이스틱을 다음과 같이 조작하여 AA...A 에서 이름을 기록하는 최소의 조작 수를 구하여라 위 = 알파벳 다음글자 (Z->A) 아래 = 알파벳 이전 글자 (A->Z) 왼쪽 = 커서 왼쪽으로 (맨 왼쪽 => 맨 오른쪽) 오른쪽 = 커서 오른쪽으로 (맨 오른쪽 => 맨 왼쪽) 2. greedy 이문제는 그리디로 푸는 문제가 아닌것같지만 그리디 항목에 있어서 그리디로 풀었다. 그리디는 최소임을 보장하지 않는다. "CANAAAAANAN" 의 경우 최소는 48이지만 그리디한 방법 현재상태에서 최선을 선택하면 49가 나온다고한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..
2021.03.16