본문 바로가기

CS Study/algorithm

 (23)
다이나믹 프로그래밍 다이나믹 프로그래밍이란? (동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 일반적으로 두가지 방식으로 구성된다.(top down, bottom up) * 자료 구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미하지만, 다이나믹 프로그래밍에서 다이나믹은 별 다른 의미 없이 사용된 단어이다. - 다이나믹 프로그램인 문제가 다음의 조건을 만족할 때 사용할 수 있다. 1) 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2) 중..
다이나믹 프로그래밍 2 (이론 정리) Dynamic Programming(DP)는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임이다. DP는 왜 사용할까? 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 발생한다. 그럼 한 번 구한 작은 문제의 결과 값은 저장해두고 재사용하자! 가 DP의 사용 이유이다. 분할 정복과 무엇이 다를까? 작은 문제가 중복이 일어나는지, 안일어나는지에 따라 차이가 있다. 분할 정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나지 않는다. 동적 프로그래밍은 작은 부분 문제들이 반복이된다. Memoizat..
이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다. 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. -> 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. ex. 시작점, 중간점, 끝점을 기준으로 내가 찾고자하는 원소가 중간점보다 작을 경우 중간점~ 끝점 까지는 탐색을 하지 않아도 된다. ➡️ 끝 점을 중간점 왼쪽으로 옮기고 중간점을 다시 설정한다. ➡️ 위 과정을 반복한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례한다. 즉 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장한다. 파이썬 코드 def binary_sear..
정렬 정렬이란?? - 데이터를 특정한 기준에 따라 순서대로 나열하는 것. - 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨. 1. 선택 정렬 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. #직접 작성한 초기 코드 array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)-1): min_num=array[i] num=array[i+1] index=i+1 for j in range(len(array)): if(jarray[j]: index=j num=array[j] if min_num>num: array[index]=min_num array[i]=num print(array) #답안 for i ..
DFS & BFS 그래프 탐색 알고리즘: DFS/BFS - 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. * DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이다! - 스택 자료구조 stack = [] stack.append(5) stack.pop() # 최상단 원소부터 출력 print(stack[::-1]) # 최하단 원소부터 출력 print(stack) - 큐 자료구조 from collections import deque queue=deque() queue.append(5) queue.append(2) queue.popleft() print(queue) queue.reverse() print(queue) - 재귀 함수 자기 자신을 다시 호출하는 함수, 종료 조건을 무조건 포함해야한다. ..
구현: 시뮬레이션과 완전 탐색 구현이란? - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 그럼 알고리즘 대회에서 구현 유형의 문제란? - 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. ex. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 1. 일반적으로 알고리즘 문제에서 2차원 공간은 행렬의 의미로 사용된다. 그리고 2차원 공간에서의 방향 벡터가 자주 활용된다. # 동, 북, 서, 남 dx = [0,-1,0,1] dy = [1,0,-1,0] # 현재 위치 x, y = 2, 2 for i in range(4): # 다음 위치 nx =..
그리디 그리디 알고리즘이란? - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 정당성 분석이 중요 ➡️ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요한 기법이다. (일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.) EX. 거스름 돈 문제 문제: 1260원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러주는 경우에 대해서 찾아본다. 답: 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러주면 된다. N원을 거슬러줘야할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러 준다. 이후로 100원, 10원으로 거슬러주기 ➡️ 정당성 분석 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은..

티스토리툴바