일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- 소프티어
- path planning
- 선형대수
- CUDA
- MDP
- DynamicProgramming
- C++
- 수치최적화
- 백준
- Dubins Path
- GIT
- autonomous vehicle
- Graph Neural Network
- solver
- 경로생성
- 강화학습
- 정적라이브러리
- Hybrid A star
- Frenet Coordinate
- CPP
- Recursion
- Leetcode
- C
- OSQP
- PathPlanning
- GNN
- self driving car
- 동적라이브러리
- 공유라이브러리
- Motion Planning
- Today
- Total
목록개념공부/알고리즘 (13)
Swimmer
문제 설명 Interval을 Scheduling 하는 문제는 코딩 문제의 대표적인 유형 중 하나이다. 예를 들어, 시계열을 기준으로 시작 시간과 종료 시간이 주어진 여러개의 수업이 있을 때, 이를 최대한 많이 수강할 수 있는 수업들을 Scheduling 하는 것이다. 이 문제는 Sorting과 Greedy Algorithm 개념을 활용해 풀 수 있다. 먼저 Scheduling 문제는 Greedy Algorithm을 적용할 수 있다. 이를 적용하기 위해서는 2가지를 고려해야 하는데, 첫번째는 각 Interval이 Sorting 되어야 한다는 것이다. 그리고 Interval의 종료 시간을 기준으로 Sorting 되어야 한다. 문제 예시 4개 수업의 시작 시간 및 종료 시간이 다음과 같이 주어졌을 때, 겹치지..
Tribonacci 수열 피보나치 수열이란, 특정 항이 앞의 두 항의 합과 같은 수열을 의미한다. 첫번째와 두번째 항의 값은 0, 1로 고정된다. 피보나치 수열의 n 번째 값이 무엇인지 계산하는 것이 코딩 기본 문제에 종종 등장한다. Tribonacci 수열은, 피보나치 수열에서 1개의 항을 더 추가하는 것이다. 즉, 특정 항의 값이 앞의 세개 항의 합과 같은 수열이다. 이때 첫번째, 두번째, 세번째 항의 값은 각각 0, 1, 1로 고정된다. 예를 들어, Tribonacci의 4번째 항은 0 + 1 + 1 = 2이다. 5번째 항은 1 + 1 + 2 = 4가 되는 것이다. Tribonacci 수열의 n번째 값을 계산하는 문제도 종종 코딩 문제로 나온다. 문제 풀이 방식은 피보나치와 다를게 없다. 연습해보고..
Monotonic Stack (단조 스택) Monotonic Stack은 원소가 Increasing / Decreasing으로 정렬되어 있는 배열을 의미한다. Monotonic Stack 그 자체로 유용함은 없지만, 정렬되어 있지 않은 배열을 Monotonic Stack으로 만드는 과정 혹은 Monotonic Stack에 새로운 원소가 입력되었을 때, 정렬하는 과정에서 발생하는 정보들이 유용하다. 이를 사용해 풀 수 있는 문제들이 있는데, 대표적인 문제는 Find Next Greatest Number 이다. Brute Force로도 풀 수 있지만 Time Complexity : O(n^2)이므로 입력 배열의 원소 개수가 많을 수록 불리하다. 이때 Monotonic Stack을 만드는 과정에서의 정보를 이..
Method 백트래킹 알고리즘은 모든 솔루션을 탐색해볼 수 있는 방법이다. 탐색 과정은 Tree 자료 구조를 DFS(depth first order)로 탐색하는 것과 동일하다. Tree 자료 구조를 기준으로 Partial Candidates는 tree의 Node로 표현되고, 1 depth 마다 부모 노드의 partial candidates에서 자식 Node의 값이 추가된다. 수많은 솔루션에서 정답만 찾아야 한다면, 백트래킹은 다음과 같이 동작한다. DFS와 같이 root node에서 부터 tree를 재귀적으로 순회한다. 각 노드에서 알고리즘은 노드가 valid solution인지 체크한다. 만약 solution이 아니라면 스킵한다. 정답이라면 저장한다. 특정 Depth에서의 노드 값들의 배열을 저장해야 ..