컴공과고씨

푸리에 변환을 이해하기 위해 알아할 기본적인 지식부터 하나씩 정리할 것 입니다. *각속도라는 개념에 대해서 좀 더 설명 해보자면 sin 그래프를 원에 붙인다고 생각하면 쉽습니다. 무슨 말이냐면 cos(2πt) 그래프에서 주기는 1sec 일 겁니다. 그 말은 똑같은 모양이 반복되어지는 시간이 1초라는 겁니다. 즉, 1초마다 똑같은 모양이 반복되는 것이죠. 360도는 2π이기 때문에 원으로 볼때 한 바퀴라는 것은 2π 만큼 각을 움직 인 것 입니다. 그래서 cos그래프에서 1초 동안 움직인 거리를 원으로 그렸을 때 몇 바퀴를 돌 수 있을까 라는 생각을 해보면 만약 주기가 2초라면 2초마다 반복이 일어나는 거고 1초 동안은 한 주기 그래프에서 1/2만 이동하는 것이죠. 그럼 원으로 그려서 봤을 때 전체 주기의..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제의 핵심은 두 가지로 볼 수 있다. 첫 번째는 팀을 어떤 식으로 구성하는 가. 두 번째는 구성한 팀에서 능력치를 구해 전 팀과 비교. 팀을 구성하는 방법은 중복을 고려해주어야 한다. 팀을 구성하는 방법 - 먼저 한 팀의 인원은 n/2이다. n이 4라고 할 때 한 팀의 인원은 2명 - 01 02 03 12 13 23 이런식으로 구성할 것이다. for (int i = start; i < n;i++){ // 중복 고..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제 같은 경우는 탐색 BFS 알고리즘을 이용하면 쉽게 구현이 가능하다. 보드판 100칸 중에 사다리 혹은 뱀이 있을 경우 도착 지점을 적어두고 나머지는 0으로 해서 특수한 경우와 일반 경우를 구별해준다. bfs를 구현할 때는 큐에 좌표와 주사위를 굴릴 때마다 카운트 하는 변수를 넣어준다. 주사위가 1일때 부터 6일때까지 반복해주고 현재 좌표에 더..

ROM (Read only Memory) - 기본적으로 rom은 읽기만 가능. - 초기에 만들 때 부터 프로그래밍이 되어서 나옴 PROM - 처음 한번 프로그래밍이 가능하고 다음 부터는 불가능 EPROM - 자외선을 이용해서 지울 수 있어 다시 프로그래밍이 가능함 EEPROM - 전기적 신호를 이용하여 지우고 다시 프로그래밍이 가능하다.

Template Matching -입력 영상에서 작은 크기의 부분 영상 위치를 찾아내고 싶은 경우 사용 - 템플릿은 찾고자 하는 대상이 되는 작은 크기의 영상을 의미 - 템플릿 영상을 입력 영상 전체 영역에 대해 이동하면서 가장 비슷한 위치를 수치적으로 찾음. (유사도가 가장 높은거 or 비유사도가 가장 낮은거) Motion Estimation - 현재 영상과 참조 영상 사이의 motion vector를 추정하는 것. 즉, 두 영상 사이의 움직임 벡터를 알아내는 것 - 모션 벡터를 이용하면 영상을 압축 하여 전송하는게 가능함. (뒤에서 설명) BMA(Block Matching Algorithm) - 설명 그대로 주어진 이미지 블록에 대해서 motion vector(MV)(모션 벡터)를 찾아주는 것이다. ..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해결 방법은 2차원 배열을 이용해서 map을 만들어주고 사과가 있는 칸에는 1을 넣어준다. 입력으로 시간과 방향 정보를 받아 준다. 방향을 바꾸기 전까지 반복문을 돌아줄건데 다음 x좌표와 다음 y 좌표를 구해주고 맵을 벗어나는지 확인해주고 visit을 체크해줄건데 visit은 몸이 있는 좌표에 true를 넣어주는 것이다. 뱀이 사과를 먹는 경우에 몸의 길이가 늘어나는데 이때 큐에 좌표를 넣어주고 v..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 먼저 이해하면 탑이 서있을 때 오른쪽 탑부터 왼쪽으로 레이저를 쏴서 자신보다 높이가 같거나 높은쪽에 부딪치면 수신하는 탑이 되고 없다면 0을 출력하는 것이다. 내가 생각한 문제 접근 방식을 소개하면 일단 처음 입력 받은 탑들을 스택에 넣어준다. 스택에 넣어주는 이유는 오른쪽 탑부터 레이저를 쏘기 때문이다. 이 때 스택에 저장하는 값은 pair를 이용해서 첫번째는 탑의 높이 두번째는 순서를..

https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 이 문제 같은 경우는 2개의 케이스로 나누어서 풀어주었다. 첫 번째는 트럭이 올라갈 때 다리의 무게가 버틸 수 있어 트럭이 올라갈 수 있는 경우와 트럭이 다리를 다 건넌 경우로 나누어 주었다. 트럭이 출발하면 큐에 넣을 건데 이 때 그 트럭의 무게와 언제 다리를 다 건너는지 도착 시간을 pair를 이용해서 넣어주는 것이 핵심이다. 큐를 쓰는 이유는 ..

https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 이 문제 같은 경우 각 줄마다 누루고 있는 음을 저장하는 스택배열을 선언해서 풀면 쉽게 풀 수 있다. 음을 누를경우 스택에 넣어준다. 이유는 먼저 누른 음은 항상 나중에 뗄 것이기 때문이다. 만약 5를 누루고 10을 누루고 11을 눌렀다고 치고 6을 누르려고 하면 손가락을 뗄 때는 마지막에 누른 음부터 손가락을 떼게 된다. 11->10까지 떼주고 6을 눌러준..

영상에서 Thresholding이란 어떤 이미지에서 기준을 정해서 그 값 이상이면 어떤 값, 낮으면 또 어떤 값 이런식으로 정해주는 것이다. 여기서 중요한 것은 기준 T를 어떻게 정할 것이냐가 가장 중요한 요소이다. 기본적인 Global thresholding은 임의의 T를 기준으로 클래스를 나눈 후 각 클래스의 평균의 평균을 구해서 그것을 다시 T로 잡고 다시 반복한다. 이런 식으로 해서 T를 최대한 클래스가 잘 구별되는 쪽으로 가도록 한다. 그러나 이 방법에는 문제가 있다. 한 쪽 클래스가 너무 몰려있고 구별하려는 곳이 너무 적을 경우 제대로 된 thresholding 안될 수 있다. 예를 들면 이럴 때 유용한 것이 바로 otsu's method 이다. Otsu's Method 이 방법은 평균과 분산..