알고리즘
-
Backtracking알고리즘 2021. 2. 13. 07:30
정의 백트래킹은 문제를 Brute force 방법의 일종으로, 문제를 재귀적으로 풀어내서 점진적으로 해결책을 마련하는 방법이다. Example Knight's tour 문제를 보자. N*N의 보드에서 체스말인 나이트가 이 보드를 전부 방문한다고 할 때, 나이트가 방문한 순서를 print하는 문제이다. 푸는 방법에는 두가지가 있는데 하나는 모든 경우의 수를 생성하고 조건을 만족하는지를 check하는 Naive Algorithm 두번째는 Backtracking이다. 1. Naive Approach 모든 경우를 생성하고, 조건에 만족하는지를 체크하는 방법이다. while there are untried tour { generate the next tour if this tour covers all square..
-
Leetcode - 15. 3Sum알고리즘/알고리즘 문제 복기 2021. 2. 13. 06:33
leetcode.com/problems/3sum/ '풀어낼 떄 2Sum을 이용해야겠다'라는 생각을 하고 접근해서 풀어보려고 했지만 중복을 해결하지 못해서 풀어내지 못했었다. Set을 사용해서 Output을 세팅하려 했지만 [-1, 0, 1], [0, -1, 1]은 다른것으로 처리되어 중복은 해결되지 않았다. 결국 Discussion 탭을 보게되었고 다음과 같이 풀이가 있었다. 2Sum의 기법을 사용하는 방법까지는 맞는 방향성이였던 것 같다. 중복을 해결하는 방법으로, 우선 배열을 정렬해 준 다음에, 16번 라인, 17번 라인에서 위와 같이 값이 중복이라면 index값 다음 값으로 넘기는 방식으로 진행하여 중복을 해결해냈다.
-
Leet code - 2. Add Two Number알고리즘/알고리즘 문제 복기 2021. 2. 8. 19:06
leetcode.com/problems/add-two-numbers/ Add Two Numbers - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Answer1. 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 ..
-
Leet code - 1. Two Sum알고리즘/알고리즘 문제 복기 2021. 2. 6. 19:38
leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. Brute force 언어: C++ 2중 for문을 이용해 풀었다. 단순하게 전체를 훑어서 맞는 값을 찾아내는 방식 2. map 이용 a + b = target b = target - a 인 것을 이용해 배열을 훑는건 똑같지만 map에 값을 담고 map에 target - nums[i]를 뺀 값이 있는지 확인해서(조건을 충족하는 값이 있는지..
-
Leecode - 5. Logest Palindromic SubString알고리즘/알고리즘 문제 복기 2021. 2. 6. 17:55
leetcode.com/problems/longest-palindromic-substring/ Longest Palindromic Substring - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com string s가 주어지고, 가장 긴 palindrome을 만족하는 substring을 구하는 문제 첫번째 풀이: Brute Force 언어: C++ 기존에 Brute Force 방법으로 풀어보려 시도했고, 테스트코드에서는 어느정도 맞아 떨어지는 것을 볼 수 있었다...
-
K번째 수알고리즘/알고리즘 문제 복기 2021. 2. 3. 12:03
programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 문제 내 풀이 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 #include #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; vector sliced_array; // commands[i][0] == first ind..
-
복잡도 계산알고리즘 2021. 1. 29. 18:07
복잡도의 종류 Time Complexity Space Complexity 복잡도의 정의 Time Complexity 메소드가 호출된 빈도를 세서 복잡도를 계산한다 Space Complexity 알고리즘이 차지하는 총 공간. Example1) 다음과 같은 코드가 있을 때 복잡도 계산은 다음과 같다. 시간 복잡도 계산은 '메소드가 호출된 빈도'를 계산하는 것인데 위의 코드를 보면 s = 0, return s에서 메소드가 한번씩 호출되었고, for문의 조건이 'n+1'번이 호출되었고, for문 안의 S = S+A[i] 구문이 'n'번 호출되어서, 이를 다 합해 '2n+3' 이라는 값이 나왔고 가장 큰 지수의 값만 따지는 빅 오 노테이션을 통해 O(n)으로 표기했다. 공간 복잡도는 배열인 A가 n만큼의 크기를 ..
-
Divide and conquer알고리즘 2021. 1. 15. 17:11
Divide And conquer Algorithm DAC 소개 DAC를 사용한 알고리즘들 DAC의 주의점 Divde And Conquer 소개 Divide and conquer Algorithm은 알고리즘 전략 중 하나로써 일반적으로 다음 세단계를 거쳐 문제를 해결한다. 1. Divide 문제를 하위 문제(sub-problem)으로 나누는 과정 2. Conquer 하위 문제가 해결될 때 까지 재귀적인 호출을 해서 하위 문제를 풀어낸다. 3. Combine 풀어낸 하위 문제를 통해 문제의 해결책을 찾아낸다. // P is Problem DAC(P) { if(small(P) return(Solution(P)); else { divide P in P1, P2, P3 ... Pk; // f1(n) Apply ..