[Kalman filter - 1] Average Filter, Moving Average Filter, Low-pass Filter
·
Study/Radar
앞으로 몇 개의 글에 걸쳐서 Kalman filter에 대해서 정리해보고자 합니다.해당 글들은 "칼만 필터는 어렵지 않아" (김성필) 책을 기반으로 정리하는 내용들입니다. 책의 지향점과 마찬가지로 수학적인 유도와 증명보다는 칼만 필터의 핵심 알고리즘의 작동 개념을 이해하고 여러 예제를 통해 학습하는 것을 목표로 합니다. 먼저 Kalman filter를 이해하기 위해 필요한 기본적인 filter인 average filter, moving average filter, low-pass filter에 대해서 정리하겠습니다.   평균 필터 (Average Filter) 정말 간단한 연산으로써 만약 $k$개의 데이터 $(x_1, x_2, \cdots, x_k)$가 있다면 모든 데이터를 더한 뒤 $k$로 나눠주는 필..
FMCW (Frequency-Modulated Continuous Wave) Radar
·
Study/Radar
이번 글에서는 3D sensor 중 하나인 FMCW radar와 동작 원리에 대해서 알아보겠습니다. FMCW Radar란?선형적으로 주파수가 변조된(modulated) 신호를 연속적으로 송신(transmit)하고 목표(target)의 거리와 속도에 따라 주파수가 변한 수신(received) 신호를 통하여 거리, 속도, 각도를 측정하는 센서입니다.FMCW radar의 구조는 위 그림과 같습니다. 먼저 신호 생성기에서 정현파 신호를 발생시키고 증폭기를 거친 뒤 송신 안테나($T_x$)를 통해 신호가 주변으로 방사됩니다. 방사된 신호는 물체에 반사되고 이 반사된 신호는 수신 안테나($R_x$)로 들어오게 됩니다. 이후 송신 신호와 수신 신호를 mixer를 통해 두 신호를 대수적으로 곱해줍니다. 이는 두 정현파..
[백준] 7576번: 토마토 (python)
·
Study/algorithm
https://www.acmicpc.net/problem/7576상하좌우의 토마트를 익힌다는 말을 보고 BFS를 떠올렸다.하지만 1. 날짜를 어떻게 카운트할 것인가, 2. 모든 토마토를 익히지 못하는 경우를 어떻게 알것인가이 두가지를 해결하지 못해서 찾아봤다.아이디어는 간단했다. 주변 토마토를 익히면 해당 위치의 값을 이전 위치의 값에 +1을 해주면 된다.이후 마지막에 순회하며 가장 큰 값을 찾은 뒤 -1을 하면 최종 걸리는 날짜를 구할 수 있다.또한 순회 중 익지 않은 토마토를 찾게 되면 -1을 출력하면 되는 간단한 생각이었다.from collections import dequem, n = map(int, input().split())tomato = []q = deque()for i in range(n..
[백준] 10971번: 외판원 순회 2 (python)
·
Study/algorithm
https://www.acmicpc.net/problem/10971처음에는 최소 비용이라는 단어만 보고 무작정 BFS로 풀었다가 시간 초과로 못푼 문제.DFS로 순회를 하며 지금까지의 최소 비용보다 비용이 높다면 다시 그 전으로 돌아가 백트래킹을 하여 문제를 해결하였다.순회가 종료되었음을 확인하는 조건을 생각해내지 못해서 검색을 통해 풀었다.끝까지 순회를 한 뒤 마지막 지점에서 다시 출발 점으로 갈 수 있는지 확인하면 되는 간단한 방법이었다...DFS에 좀 더 익숙해져야 할 필요가 있다.from collections import dequen = int(input())costs = [list(map(int, input().split())) for _ in range(n)]# 최소 비용min_cost = 1..
[백준] 2468번: 안전 영역 (python)
·
Study/algorithm
https://www.acmicpc.net/problem/2468BFS를 사용하여 문제를 풀이하였다.문제 풀이의 포인트는 지도를 저장하며 최대 높이를 구하여 최대 높이 전까지만 물이 차는 경우를 모두 탐색한다.또한, 잠기지 않은 땅인 경우에 해당 영역 기준으로 BFS를 통하여 주변 영역들을 순회하며 잠기지 않은 영역을 구분하고 카운트한다.마지막으로 카운트 된 갯수 중 가장 큰 값을 출력하면 된다.from collections import dequedef bfs(x, y, num): q = deque([(x, y)]) visited[x][y] = True while q: n_x, n_y = q.popleft() # 상하좌우 방향 탐색 fo..
[백준] 11057번: 오르막 수 (python)
·
Study/algorithm
https://www.acmicpc.net/problem/11057dp 테이블을 2차원으로 구성해서 풀어가는 문제규칙만 잘 생각하면 쉬운 문제였다.n = int(input())# 2차원 dp 테이블 생성dp = [[0] * 10 for _ in range(1001)]# 길이가 1인 경우 오르막 수for i in range(10): dp[1][i] = 1 for i in range(2, n + 1): for j in range(10): cnt = 0 # 마지막 자리가 현재 숫자보다 크거나 같은 경우를 모두 카운트 for k in range(j, 10): cnt += dp[i - 1][k] dp[i][j] = cnt ..
[백준] 11726번: 2×n 타일링 (python)
·
Study/algorithm
https://www.acmicpc.net/problem/11726전형적인 DP 문제로 규칙을 찾아가면 되는 문제n이 1000이하 값으로 크지 않기 때문에 1부터 모두 구해나가면 된다 규칙을 간단히 설명하면,n = 1일때는 아래 그림과 같이 채울 수 있습니다. n = 2일때는 아래 그림과 같이 채울 수 있습니다. n = 3인 경우부터 규칙이 발생합니다. n = 1인 경우 뒤에 1 x 2 블록 두개를 쌓은 경우와 n = 2인 경우 뒤에 2 x 1 블록 한개를 쌓은 경우가 됩니다. 동일한 규칙으로 n = 4인 경우에는 n = 2인 경우 뒤에 1 x 2 블록 두개를 쌓은 경우와 n = 3인 경우 뒤에 2 x 1 블록 한개를 쌓은 경우가 됩니다.  따라서 n = (n - 2) + (n - 1) 의 규칙을 가지게..
[백준] 1463번: 1로 만들기 (python)
·
Study/algorithm
https://www.acmicpc.net/problem/1463처음에는 아무 생각 없이 BFS로 풀었다가 시간 초과로 틀린 문제입력이 10의 6승으로 매우 크기 때문에 DP를 이용해 시간 생각을 하면서 풀었어야 했다무작정 풀지말고 생각 먼저 하고 풀기# BFS로 풀어서 시간 초과된 코드from collections import dequen = int(input())q = deque()q.append((n, 0))ans = -1while q: now, times = q.popleft() if now == 1: ans = times break if now % 3 == 0: q.append((now // 3, times + 1)) if now % 2..