컴공과고씨

convolution을 이해하기 위해서는 앞 포스트 내용을 이해하고 오는 것이 좋다. LTI 시스템이 중요한 이유는 LTI 시스템을 만족하면 Convolution Sum으로 나타낼 수 있다. impulse response를 나타내면 이것이 LTI 시스템을 만족하게 되면 이런식으로 변한다 이 식의 의미는 하나의 입력 가지고 모든 출력을 알 수 있다는 뜻이다. 그래서 LTI시스템이 중요한 것이다. 우리가 모든 입력을 넣어보지 않아도 하나의 입력으로 모든 출력을 알 수 있기 때문이다. 그래서 LTI 시스템은 convolution sum(*)으로 표현 될 수 있다. Computing Convolution 예시 h[n]에서 h[-n] 즉, 원점 기준으로 대칭이동해주는 것이 포인트이다. y[0] = h[-n]을 x..

signals : A sequence of information or data system : 시그널을 입력으로 받아서 또 다른 시그널을 출력. system function (system operator) H Linear system 선형시스템이란 scaling 과 superposition(additivity)를 만족하는 것이다. scaling(homogeneity)은 스칼라 값을 곱한후 시스템 함수에 넣은 거나 시스템 함수에 넣은 후 스칼라 값을 곱한 값이 같다는 것이다. superposition(additivity)는 먼저 두개의 입력을 더한 후 시스템 함수에 넣은 것이랑 각각의 입력을 시스템 함수에 넣은 후 더한 값이랑 같다는 것이다. 그래서 이 두개를 만족하면 선형 시스템이라고 한다. Time-i..

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 시간초과로 못풀어서 어떤식으로 풀어야하는지 처음으로 답을 참고를 했던 문제이다. 그래서 나중에 한번 더 복습이 필요할 것 같다. 아무튼 어떤식으로 풀었고 시간초과가 났으면 어떤식의 해결방법이 옳았는지 보겠다. 처음 푼 방법은 1, 11, 111, 1111이렇게 직접 n으로 나누어가면서 1의 개수를 늘려주어 나머지가 0인것을 찾으면 될거라고 생각했다. 하지만 이렇게 풀면 시간 초과가 걸리기 때문에 나머지 연산 공식을 써주어야한다. 이 문제는 나머지..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제를 보고 탐색으로 풀어야겠다고 생각했다면 바로 풀 수 있다. 한가지 조금 다른 문제와 다른거는 대각선으로 땅을 밟을 수 있기 때문에 대각선을 고려해야한다는 것만 주의해주면된다. 기존에 상하좌우를 dx[] = {0,0,-1,1} = dy[] = {1,-1,0,0} 이런식으로 4번을 반복해서 움직여주었다면 이번거는 dx[] = {0,0,-1,1, 1,1,-1,-1} = dy[] = {1,-1..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 이 문제는 어떤 식으로 접근했냐면 한 로프를 사용한다고 가정했을 때, 자기보다 많은 무게를 드는 로프는 결국 자신의 로프의 최대 들 수 있는 용량을 모두 들 수 있다는 것을 이용했다. 10 30 50 50 85 90 이라는 무게를 들 수 있는 로프가 있을 때 10로프를 이용해서 들 수 있는 최대 중량은? 10과 10보다 큰 로프의 개수를 10에 곱해주면 총 60을 들 수 있다. 30로프를..

https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 이 문제를 보고 조금 생각을 해본 결과 팁을 많이 주고 싶어하는 사람들을 앞쪽에 세워야지 가장 많은 팁을 얻을 수 있다. 왜냐하면 뒤로 등수가 밀릴수록 그 만큼 빼주어야한다. 그렇다면 팁을 10을 주고 싶은사람이 10등인것과 팁을 1을 주고싶은 사람이 10등이라면 전자는 0원 후자는 음수가 되어진다. 여기서 음수는 0으로 처리가 되어지기 때문에 둘다 똑같이 못받는 꼴이 된다. 그..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 이 문제를 보고 나는 수학적으로 풀어야겠다고 생각했다. 물론 dynamic programing (동적계획법)으로도 풀 수 있지만 딱 처음 떠오른것이 수학적으로 푸는것이였다. 어떤 생각을 했냐면 일단 최대한 5원짜리를 쓰고 남은 돈에서 만약 2로 나눴을 때 나머지가 0이 안되면 5원짜리를 한 개 덜 쓴 후 2로 나누어 주도록 반복하여 2로 나눈 나머지가 0이 되도록 하면 쉽게 풀릴거라고 생각했다. 그리고 예외처리로 처음 최대한 5원짜리를 쓰고 점점 5원짜리를 줄여갈건데 이것이 음수가 되면 거슬러 줄 수 없는 것이므로 ..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수를 구하는 문제. 문제를 보면 처음 들어야할 생각은 동적 계획법(dynamic programing)를 떠올려주면 쉽게 풀린다. 재귀로 구현하면 아마 시간초과가 걸릴것이다. 그렇기 때문에 dp 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주..

저번 글에서 기본적이 intensity transformations에서 공부했습니다. 이번에는 histogram equalization에 대해서 알아보겠습니다. unnormalized histogram 위 그림 처럼 m*n의 픽셀들이 나열되어있을 때 각 픽셀이 나타내는 밝기가 0~n까지 있다면 밝기가 0인 칸의 개수 1인 칸의 개수 쭉쭉 세어서 옆의 그래프 처럼 나타낸 것이다. 히스토그램의 bin을 이용해서 범위를 지정해 그 범위 밝기에 속한 칸의 개수를 세어 그래프를 만들어준 것이다. 이 때 이 범위를 bins라고 합니다. unnormalized histogram가 있으니 normalized histogram도 있다. normalized histogram는 unnormalized histogram에서 ..

오늘은 영상처리에서 intensity transformations에 대해 알아보겠습니다. 밝기 값 변환에는 spatial domain processing(공간 도메인)이 있습니다. 이것의 정의는 픽셀 하나하나의 밝기 값을 변경해 주는것을 말합니다. 왼쪽 그림은 contrast strectching의 예시이고 오른쪽 그림은 Thresholding의 예시입니다. Contrast strectiching로 k의 왼쪽에 있는 빨간 점선의 점들은 더 어둡게 바꾸어주고 k 오른쪽에 있는 빨간 점선의 점들은 더 밝게 바꾸어 주어 대비를 늘리는 모양입니다. 반면, Thresholding은 k점을 기준으로 왼쪽은 검은색으로 오른쪽은 제일 밝게 바꾸어 주고 있습니다. Remarks 1. point processsing이다 ..