본문 바로가기

알고리즘117

[알고리즘] 퀵 소트 공부해보기 분할정복 알고리즘인 퀵 소트에 대해 공부해보았다. https://www.daleseo.com/sort-quick/ [알고리즘] 퀵 정렬 - Quick Sort (Python, Java) Engineering Blog by Dale Seo www.daleseo.com 여기에서 상상 이상으로 정리가 잘 되어있다. 기본이 있고, 최적화하는 방법이 있는데 나는 일단 기본부터 외워보기로 했다. 의외로 구현이 간단해서 놀라웠다. 금방 외울 수 있었다. def qsort(arr): if len(arr) arr[i]: l.append(arr[i]) elif mid < arr[i]: r.append(arr[i]) else: e.append(arr[i]) return qsort(l) + e + qsort(r) print(.. 2021. 11. 13.
[알고리즘] DP 공부해보기 동적 계획법이라는 것에 대해 공부해보는 시간을 가졌습니다. '완전탐색 < DP' 라고 합니다. 문제를 쪼개고, 작은 단위의 답을 구하고, 그걸 바탕으로 더 큰 문제의 답을 구하는 과정을 반복하는 방법입니다. 오늘은 맛보기로 DP의 대표작인 피보나치 수열에 대해 간단하게 알아보았습니다. # recursive def f(n): if n < 2: return n return f(n-1) + f(n-2) # top - down cache = [-1] * 37 def f2(n): if cache[n] != -1: return cache[n] cache[n] = n if n < 2 else f2(n-1) + f2(n-2) return cache[n] # bottom - up fibo = [-1] * 37 def f.. 2021. 11. 10.
[프로그래머스] N-Queen 문제 문제 설명 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요. 제한사항 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다. n은 12이하의 자연수 입니다. 입출력 예 nresult 4 2 입출력 예 설명 입출력 예 #1 문제의 예시와 같습니다. 오답노트 안되는 문제는 그냥 외워라! 그러면 이해하게 될 것이다! 는 말은 진리인 것 같다. 처음에.. 2021. 11. 9.
[프로그래머스] 가장 긴 펠린드롬 문제 설명 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다. 제한사항 문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성 입출력 예 sanswer "abcdcba" 7 "abacde" 3 입출력 예 설명 입출력 예 #1 4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다. 입출력 예 #2 2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 retu.. 2021. 11. 8.

티스토리툴바