Itscool

다이나믹 프로그래밍 문제에 접근하는 방법 - 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요 - 가장 먼저 그리디, 구현, 완전탐색 등의 아이디어로 해결할 수 있는지 검토 다른 알고리즘으로 풀이방법이 떠오르지 않으면 다이나믹 프로그래밍 고려 - 우선 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 후 Top-Down(작은 문제에서 구한 답이 큰 문제에 사용될 수 있음) 방식이 적용될 것 같으면 코드를 개선하는 식 - 점화식 떠올려보기 - 일반적인 코딩테스트 유형에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음 다이나믹 프로그래밍 문제1: 개미 전사 A(i): i번째까지의 식량창고가 존재할 때 털 수 있는 식량의 최댓값 K: 식량창고 리스트 개미전사 파이썬 코드 impor..

다이나믹 프로그래밍이란? - 메모리를 적절히 사용하여 수행시간을 비약적으로 향상시키는 방법 - 이미 계산된 결과는 별도 메모리 영역에 저장하여 다시 계산하지 않도록 함 - 다이나믹 프로그래밍의 구현은 일반적으로 하향식(Top-Down)과 상향식(Bottom-Up)으로 구성 일반적인 프로그래밍 분야에서의 동적(Dynamic)의 의미 - 자료구조에서 동적할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 - 동적계획법(Dynamic Programming)에서의 동적(Dynamic)은 별다른 의미없이 붙여진 단어 다이나믹 프로그래밍의 조건 1. 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 ..

순차탐색이란? 리스트에서 특정 데이터를 찾기 위해 앞에서부터 순차적으로 데이터를 확인하는 탐색 방법 이진탐색이란? 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 하나씩 확인하는 방법 - 시작점, 중간점, 끝점을 이용하여 탐색 범위를 설정 - 시간복잡도 log(2)N 파이썬 라이브러리 bisect from bisect import bisect_left, bisect_right a = [1, 2, 3, 4, 4, 6, 7, 8] x = 4 bl = bisect_left(a, x) # 정렬을 유지하며 x를 삽입할 가장 왼쪽의 인덱스를 반환 br = bisect_right(a, x) # 정렬을 유지하며 x를 삽입할 가장 오른쪽의 인덱스를 반환 print(bl) print(br) # 값이 특정 범위에 속..

탐색(Search)이란? - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 대표적인 그래프 탐색 알고리즘으로는 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있음 - DFS/BFS는 코딩테스트 빈출유형이므로 반드시 숙지해야 함 DFS(Depth-First Search)란? - 깊이우선탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 - 스택 자료구조(혹은 재귀함수)를 사용 - 동작 과정 탐색 시작 노드를 스택에 push, 방문 처리 스택 최상단에 방문하지 않은 인접한 노드가 있으면 push, 방문 처리(단, 방문하지 않은 노드가 없으면 pop) 더 이상 2. 의 과정을 수행할 수 없을 때까지 반복 def dfs(graph, v,..

스택 자료구조 - 먼저 들어온 데이터가 마지막에 나가는 형식, 후입선출(Last In First Out) - 입구와 출구가 동일한 형태로 시각화 큐 자료구조 - 먼저 들어온 자료가 먼저 나감, 선입선출(First In First Out) - 입구와 출구가 각각 뚫려있는 터널의 형태로 시각화 재귀함수(Recursion Function) - 자기 자신을 다시 호출하는 함수 - 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임, 따라서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많음 - DFS/BFS 의 구현에 있어 매우 중요 유클리드 호제법 - A>B일 때, A를 B로 나눈 나머지를 R이라 한다. - A와 B의 최대공약수는 R과 B의 최대공약수와..

구현(Implementation)이란? 구현이란 문제풀이를 소스코드로 바꾸는 과정을 의미합니다. 일반적으로 구현 유형의 문제는 상대적으로 문제풀이 방법을 떠올리는 것보다 문제풀이 방법을 소스코드로 바꾸는 것이 더 어려운 경우를 지칭합니다. 따라서 구현 유형의 문제를 잘 해결하려면 해당 프로그래밍 언어에 대한 깊은 이해도와 다양한 라이브러리 활용 능력이 필요합니다. 구현문제 데이터 유형 예시는 다음과 같습니다. 알고리즘은 간단하지만 코드가 길어지는 문제 실수 연산을 다루고 특정 소수점까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 활용하는 문제 행렬(Matrix) 일반적으로 알고리즘 문제에서 2차원 공간은 행렬(matrix)로 표현할 수 있습니다...

그리디 알고리즘이란? 그리디 알고리즘, 탐욕 기법은 현재 상황에서 가장 좋은 것만을 고르는 문제해결 방법입니다. 그리디 알고리즘은 구현이 쉽다는 장점이 있지만 최적해를 구할 수 있는 경우는 많지 않습니다. 따라서 보통은 근사치 추정을 위해 그리디 알고리즘을 사용하곤 합니다. 일반적으로 코딩테스트에서는 문제를 풀기 위한 적절한 아이디어를 떠올리고, 또 그리디 알고리즘의 해법으로 해결이 가능한지(즉, 매 상황에서 가장 좋은 것을 고르는 방식으로 최적해 도출이 가능한지)에 대한 정당성을 분석하는 능력을 요구합니다. 예를 들어, 다음과 같은 트리구조에서 연결된 부모 노드와 자식 노드의 조합만으로 가장 큰 정수값을 도출해야 한다고 할 때, 그리디 알고리즘은 최적해를 구할 수 있을까요? 그리디 알고리즘은 눈 앞에 ..