🍒 Chae-ri Dev 🍒

[Algorithm/Python] 다이나믹 프로그래밍 알고리즘 정리

DP(Dynamic Programming)는 연산 속도와 메모리 공간을 최대한 효율적으로 활용할 수 있게 해주는 알고리즘이다. 대표적인 예시 : 피보나치 수열 피보나치 수열을 점화식으로 표현하면 다음과 같다.프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현(+ dict 자료형)# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현def fibo(x): if x == 1 or ×= = 2: return 1 return fibo(x - 1) + fibo(x - 2)print(fibo(4)) 하지만 위 코드는 n이 커지면 수행 시간이 기하급수적으로 늘어나는 문제가 발생한다.메모이제이션 기법을 사용해서 한 번 구현한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메..

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.리스트에 담긴 데이터에 순차적으로 접근해야 할 때, 시작점(start)과 끝점(end) 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 가지는 부분 연속 수열 찾기- N개의 자연수로 구성된 수열이 있다.- 합이 M인 부분 연속 수열의 개수를 구해보자.- 수행 시간 제한은 O(N)이다.  위 문제는 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다. 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.2. 현재 부분 합이 M과 같다면, 카운트한다.3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.4. 모..

https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr def solution(t, p): answer = 0 subStr = [t[i: i+len(p)] for i in range(0, len(t)-len(p)+1)] for j in subStr : if(int(j)  파이썬 슬라이스와 List Comprehensions를 활용하였다.List Comprehensions을 사용하니 코드가 간결하다.

파이썬에서는 리스트를 더 간결하고 간편하게 만들기 위해 List Comprehension라는 것을 사용할 수 있다. 기본 구조[식 for 변수 in iterable]식(expression): 리스트에 추가될 새로운 요소변수(item): 반복적으로 가져오는 변수iterable: 반복 가능한 객체(리스트, 튜플, 집합 등)a = [i*2 for i in range(10)]print(a) if 조건문 사용[식 for 변수 in iterable if 조건문]a = [i*2 for i in range(10) if i%2 == 0]print(a) 다중 반복문[식 for 변수 in iterable for 변수2 in iterable2]a = [(x, y) for x in [1,2,3] for y in [3,1,4] ..

https://school.programmers.co.kr/learn/courses/30/lessons/159994 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr def solution(cards1, cards2, goal): answer = '' inCards1Count = 0 inCards2Count = 0 subGoal = [] for i in range(0, len(goal)): if(goal[i] in cards1) : subGoal.append(cards1[inCards1Count]) ..

프로그래머스 문제를 푸는 중 reversed를 사용하면서 발견한 reverse와 reversed의 차이가 뭔지 궁금해져서 정리를 해보았다. 공식 문서에는 어떻게 분리되어 있는지 봤더니reverse() -> 리스트 객체의 메서드reversed() -> 파이썬의 내장 함수 이처럼 정의를 했다. 결론적으로, reverse는 리스트에서만 사용할 수 있고 다른데서 사용하면 AttributeError가 날 것이다. reversed는 두 가지 형태로 반환한다.tuple과 str에서 사용할 때 -> reversed 객체 반환list에서 사용할 때 -> listreverseiterator 객체 반환

특정 요소가 몇번째에 위치하는지 파이썬으로 확인하고 싶을 때 find() vs index() 둘의 차이점은 무엇이고 어떤 상황에서 쓰이는 걸까 궁금했다. 파이썬 공식 문서  Built-in TypesThe following sections describe the standard types that are built into the interpreter. The principal built-in types are numerics, sequences, mappings, classes, instances and exceptions. Some colle...docs.python.org를 참고해봤을 때  find()str 또는 문자열에서 사용찾는 문자가 없는 경우 -1 반환 index()str 또는 문자열, 리스..