컴공과고씨

오늘은 공간 도메인 필터링에 대해서 알아볼것이다. 1. 선형 공간 필터링(Linear Spatial Fitering) 위 방법은 마스크를 이용하여 필터링을 하는 방법이다. 마스크는 필터라고 보면 된다. 예를 들면 3*3 마스크가 있다고 하자. 이렇게 이미지 픽셀 마다 마스크를 씌워가며 값을 구해주는 것이다. 연산 방법은 우리가 앞에서 배운 컨볼루션(convolution)과 비슷한 correlation을 사용할 것이다. convolution에서 우리는 h[n]을 영점 대칭을 시켜준후 연산 진행했는데 correlation은 그냥 원점대칭하지 않고 그냥 곂치는 것대로 연산을 해주면된다. 예를 들면 이런식의 연산이 나오는 것이다. 이렇게 보면 correlation 과 convolution의 차이를 명확히 이해할..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제를 정리하면 땅 높이를 맞추어 주는 것인데 이제 땅을 쌓는건 1초, 깎는건 2초 걸리고 쌓을 때는 블록이 있어야 쌓을 수 있다. 최대높이가 256이기 때문에 땅을 0으로 고르는, 1로 고르는 ...... 256으로 고르는 시간을 각각 계산해서 비교해주는 식으로 풀었다. 위 방법을 brute force (브루트포스) 무차별 대입이라고 한다. 먼저 높이의 개수를 저장하는 hight 배열을 만들었..

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 배열을 이용하여 각 값을 저장해주고 다음 값을 구할때 계산하는 대신 앞에 계산한 값을 가져와주면 된다. 현재 값은 그 전의 값 + 그 전전 값 이 식을 구현해 주..