Algorithm

📚 다이나믹 프로그래밍(Dynamic Programming, DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍 구현은 일반적으로 두 가지 방식(탑다운(top-down)과 보텀업(bottom-up))으로 구성 🟦 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란? 자료구조에서 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어 ▼ 다음의 조건을 만족할 때 사용 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며..

📁이분탐색(Binary Search) 활용정렬된 데이터에서 특정 값을 찾기 위해 중간값과 타겟 값을 비교하여 탐색 범위를 좁혀가는 알고리즘기본 원리 : 배열의 중간값을 찾고, 타겟 값과 비교하여 탐색 범위를 절반으로 줄여나감구현 방법 : 반복문이나 재귀를 사용하여 구현, 중간값을 기준으로 탐색 범위를 조정def solution(n, times): start = 1 end = max(times) * n answer = end while start   프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr

📁그리디(Greedy) 활용 문제를 해결하는 과정에서 각 단계마다 가장 좋아 보이는 선택을 하는 방식으로, 매 순간 최적의 해결책을 선택함으로써 최종적인 해답을 찾아가는 전략 import sys input = sys.stdin.readline math_ = input().split('-') # 뺄셈 기호를 기준으로 식 분리 result = 0 for i in math_[0].split('+'): # 첫번째 뺄셈 기호 이전 모든 수 더함 result += int(i) for i in math_[1:]: # 첫번째 뺄셈 기호 이후의 모든 식에 대해 for j in i.split('+'): # 덧셈 기호를 기준으로 식 분리하고 각각의 수를 뺌 result -= int(j) print(result) 1541번:..

📁플로이드 워셜(Floyd-Warshall) 활용 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 최소 비용을, 갈 수 없다면 INF로 배열에 값을 저장 3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가 비용이 줄어드는 경우에는 값을 바꿔줌 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색 import sys input = sys.stdin.readline n = int(input()) # 물건의 개수 m = int(input()) # 미리 측정된 물건 쌍의 개수 INF = int(1e9) arr = [[INF] * (n+1) for _ in range(n+1)] # 2차원 리스트 만들고, 무한대로 초기화 # 자기 자신에서 자기 ..