DP (Dynamic Programming) 하나의 문제를 여러개의 작은 문제로 나누어 해결하고 그 결과를 종합하여 정답을 구하는 알고리즘. 접근 방법 상향식 접근법(Bottom-Up) 작은 하위문제부터 시작해 큰 문제까지 차근차근 해결하는 방식 작은 문제들을 해결하고 결과를 저장한 후 그 결과를 이용해 보다 큰 문제를 해결함 보통 반복문을 이용해 구현함 하향식 접근법(Top-Down) 큰 문제를 작은 하위 문제들로 재귀적으로 나누어 해결하는 방식 재귀적인 호출을 이용해 작은 문제를 해결하고 그 결과를 이용해 큰 문제를 해결함 일반적으로 메모이제이션(Memoization, 결과를 구하고 나중에 다시 활용함) 기법을 사용해 중복 계산을 피함 예시) 피보나치 1 재귀로 구현 def fibonacci(n): ..
study/TIL
그리디(Greedy) 각 단계에서 최선의 선택을 하는 방식으로 문제를 해결하는 알고리즘. 각 단계에서 최선의 선택(부분 문제의 최적해)를 모두 합쳤을때 전체에서의 최선의 선택과 다르다면 풀이가 성립하지 않는다. 따라서 그리디하게 문제를 풀때는 풀이의 정당성을 증명해야한다. 보통 최적화 문제에서 사용된다. 특징 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 쪼개어 해결할 수 있는 문제 구조를 가진다. 그리디 알고리즘은 각 단계에서 부분 문제의 최적해를 찾는 방법으로 전체 문제의 최적해를 찾는다. 탐욕적 선택 속성 (Greedy Choice Property) 각 단계에서 최적해를 찾기 위해 가장 최선의 선택을 한다. 이 선택이 나중에 문제의 해결에 대한 최적해에 영향을 미치..
1. 브루트 포스(Brute-force) 문제를 해결하기 위해 가능한 모든 경우를 다 따지며 해를 찾는 간단하고 직관적인 알고리즘. 모든 가능한 해를 찾아내는데 유용하지만, 문제의 크기가 커질수록 실행시간이 급격하게 증가하고 효율성이 낮아서 대부분은 다른 최적화 기법이나 다른 알고리즘을 사용한다. 보통 다음과 같은 과정으로 이루어진다. 후보 생성 : 모든 가능한 후보 해를 생성한다. 후보 평가 : 후보들을 평가하여 주어진 조건에 부합하는지 확인한다. 적합한 해 선택 : 문제의 요구조건에 따라 최적의 후보 해를 선택한다. 예시) 백준 1182번 부분 수열의 합 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램..
그래프 탐색 - DFS / BFS 1. 깊이 우선 탐색 (DFS) 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색하는 방법. 최대 깊이까지 도달했다면 방문한 정점들을 역순으로 재방문하며 탐색 가능한 정점이 있는지 확인한다. 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행한다. 스택 또는 재귀로 구현할 수 있다. 아래 그림의 그래프를 DFS로 탐색하는 과정은 다음과 같다. 1번 노드에서 탐색을 시작한다. 스택에 1번 노드를 삽입한다. ([1]) 1번에서 탐색 가능한 노드는 2번과 4번이 있다. 2번을 스택에 삽입한다. ([1, 2]) 2번에서 탐색 가능한 노드는 3번과 4번이 있다. 3번을 스택에 삽입한다.([1, 2, 3]) 3번에서 탐색 가능한 노드는 2번과 4번이 ..
1. 그래프(Graph) 1) 그래프의 구성 요소 정점(Node / Vertex) 특별한 하나의 객체 간선(Edge) 정점을 연결하는 선. 두 노드 간의 관계를 나타냄. 방향이나 비중을 나타낼수있음. 그래프(Graph) 정점과 간선의 집합으로 이루어진 구조. 2) 그래프 관련 용어 인접(adjacent) : 두 정점이 간선으로 연결되어 있는 경우 차수(degree) : 정점에 연결된 간선의 수 진입 차수(in-degree) : 해당 정점으로 향하는 간선의 수 진출 차수(out-degree) : 해당 정점에서 나가는 간선의 수 경로(path) : 한 정점에서 다른 정점으로 이어지는 정점들의 리스트 경로 길이(path length) : 경로를 구성하는 간선의 수 단순 경로(simple path) : 모두 다..
1. 이분 탐색(Binary Search) 정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 방법. 탐색 범위를 절반씩 줄여나가면서 탐색 범위가 1이 될때까지 진행한다. 시간 복잡도는 O(log n). 이진 탐색이라고도 한다. 이분 탐색 예시 코드 # 백준 2110번 : 공유기 설치 n, m = map(int, input().split()) trees = sorted(list(map(int, input().split()))) # 오름차순으로 정렬(필수) start, end = 1, max(trees) # 시작 위치와 끝 위치 지정 while start = mid: temp += i - mid if temp >= m: start = mid + 1 else: end = mid - 1 print(end) 예를 들..
1. 힙 (Heap) 정해진 우선 순위에 따라 원소를 O(log n)에 추가 / 삭제가 가능한 자료구조. 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조이다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있어서, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 파이썬에서는 heapq 라이브러리를 사용해 구현할 수 있다. 파이썬의 heapq 라이브러리는 최소값을 우선 순위로 하는 힙을 제공한다. 기본 연산 push : 힙에 새로운 원소 추가 pop : 힙에서 가장 우선 순위가 빠른 원소를 추출하고 그 값을 반환 heapq 라이브러리 heapify : 리스트를 최소 힙으로 변환 heappush : 힙에 원소 추가 ..
1. 스택 (Stack) 후입선출(LIFO : Last In First Out). 파이썬의 list를 사용해서 구현할 수 있다. 기본 연산 push : 스택에 원소 추가 pop : 스택에 가장 마지막으로 들어온 원소를 제거하고 그 값을 반환 peek : 스택에 가장 마지막으로 들어온 원소를 조회 list로 스택 구현하기 stack = [] stack.append(3) # 3 push stack.append(2) # 2 push stack.append(5) # 5 push stack.pop() # pop -> 5 가 제거됩니다 print(stack[-1]) # peek / python의 음수 인덱스를 활용. 맨 마지막 요소가 출력됨 2. 큐 (Queue) 선입선출(FIFO : First In First O..
오늘 강의는 없었고, 코딩 테스트를 했다. 문제가 어려운 것들이 너무 많았다 😢 그래도 멘토링 시간에 다 어려워하는 부분이니 걱정하지 말라는 얘기도 들었고 좋은 문제들에 대해 정리해볼 수 있었다. 사실 오늘 코딩 테스트 문제들을 풀면서 좀 힘들었다... 계속 실패하는 문제들 때문에 힘들었고 멘탈적으로도 좀 힘들었다. 그래도 조금 쉬고 나서 다시 생각해보면 내가 파이썬으로 알고리즘을 공부한지는 겨우 일주일쯤인데 잘하기를 바라는건 욕심인 것 같다는 생각이 들었다. 또 힘들긴 했지만 처음 문제들을 풀때 파이썬 함수들을 몰라서 계속 구글링 했던걸 생각하면 지금은 그래도 어느정도는 외우고 익숙해진 함수들이 있으니까 아주 늘지 않았다고는 말할수 없기도 하고. 내가 원하는 만큼은 아니지만 분명히 실력이 늘긴 늘었다는..
파이썬의 이차원 배열에 대해서 배울 수 있었다. 이차원 배열은 리스트 안에 리스트가 있는 형태이다. arr1 = [list(map(int, input().split())) for _ in range(n)] 이런 식으로 리스트 컴프리헨션을 사용해 입력값들을 이차원 배열로 만들어줄수도 있다. 백준으로 문제를 풀때마다 느끼는 거지만 입력값을 가져와서 어떻게 넣어주는지도 중요한 것 같다. 이차원 배열과 관련된 알고리즘 문제들을 풀면서 어렵다는 생각을 많이 한다. 그래도 해야지 뭐 어쩌겠음! new! 이차원 배열에서 최대값을 구해줄때 max함수 안에 max함수를 넣어줄수 있다는 걸 새로 알게 되었다. arr = [ [1, 2, 3] [4, 5, 6] [7, 8, 9] ] max_num = max(map(max, ..
