컴공과고씨

앞에서 우리는 1D에 대한 미분을 공부했다. 이번에는 2D에 대한 미분을 공부할 것이다. 2D는 변수가 두 개 이기 때문에 편미분을 이용해주면 된다. X와Y 방향을 따로 미분하면 벡터 값이 나온다. 벡터의 크기를 구하면 얼마나 밝은지에 대한 값이고 아크 탄젠트를 구해주면 X축과 이루는 각 즉, gradiant의 방향을 알 수 있게 되는데 90도에서 이 방향을 빼주면 edge의 방향을 구할 수 있다. 예를 들면 프리윗 마스크를 씌워주는 예이다. Simple Edge Detection 그림과 같이 2차 미분을 이용한 경계값 추출은 엣지를 얇게 추출이 가능하다. 문제는 실제 세계에서는 잡음들이 많이 섞여져 있기 때문에 위와 같은 깔끔한 그래프는 없다. 이렇기 때문에 edge detection을 할 때는 꼭 s..

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 떠올린 방법은 정렬하지 않고 일단 unique 함수를 사용해서 연속되는 수를 제거한다. (unique, erase를 잘 모른다면 https://hagisilecoding.tistory.com/53 여기서 공부하고 오면 편함) aabbbccb가있다면 unique함수를 정렬을 하고 써주면 연속되는 값이 쓰레기 값으로 가고 이것을 erase를 통해 지워주면 abcb가된다..

https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 이 문제를 보고 두가지 방법을 떠올렸는데 공백을 주지 않기 때문에 int 받으면 각자리 수 반복문을 통해 구해서 출력하거나 string을 이용해서 각 자리를 stoi를 이용해서 int로 변환해서 더해주는 것이다. 나는 후자를 사용했다. 쉽게 string으로 입력을 받아서 각 하나하나 마다 문자를 - '0'을 통해서 char형을 int형으로 변환해주었다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include #include using namesp..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 내가 처음 푼 방법은 우선순위 큐 한개와 스택을 이용해서 풀었다. 최대값은 top에서 그냥 빼주면 끝이지만 최소값을 빼는 방법은 스택을 이용해서 큐에 있는 모든 수를 빼면서 스택에 넣어준다. 그럼 스택 맨 위에 있는 것은 최소값이 된다. 그래서 스택에서 맨 위 값을 제거하고 다시 우선순위 큐에 넣는 방식으로 구현했다. 결과는 시간초과이다. 그래서 다른 방법 multiset을 이용하는 방법으로 ..

선언 set은 중복을 없애고 입력할 때 정렬이 되어서 입력되는게 특징이다. multiset은 중복을 허용하는것만 다르고 나머지는 set과 같다. set도 마찬가지로 정렬 기준을 바꿀 때는 priority queue와 마찬가지로 구조체를 선언하거나 stl에서 지원하는 것을 사용하면됩니다. 이것에 대한 설명은 https://hagisilecoding.tistory.com/60 여기에서 구조체 구현 부분을 보시 면 자세히 나와있습니다. #include set s1 // 중복없애고 정렬(default : 오름차순) multiset s2 // 중복허용 정렬(default : 오름차순) set s3 // 내림차순 정렬 set s4(s2); // 선언 후 복사한 값으로 초기화 set s4 = s2 // 선언 후 복사..

우선순위 큐는 힙을 이용하여 루트에 우선순위에 따라 최대값 혹은 최소값이 있는 것을 말한다. 선언 struct cmp{ bool operator()(int a, int b){ return a>b; } } #include priority_queue q1; // 루트가 최대인 우선순위 큐 선언 priority_queue; // 루트가 최소값인 우선순위 큐 선언 priority_queue;// 루트가 최소값인 우선순위 큐 선언 자신이 직접 우선순위를 정할 때는 구조체를 생성해주어야한다. 주의 할 것은 벡터는 위와 같이 비교연산을 하면 내림차순으로 정렬된다. 하지만 우선순위 큐는 a가 루트에 있는 값이기 때문에 a가 더 크면 true를 반환한다. 반환값이 true이면 swap를 하겠다는 의미이기 때문에 a와 b..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net priority queue 우선순위 큐를 사용하면 쉽게 풀리는 문제이다. priority queue를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다. priority_queue는 default로는 최소값이 root에 있기 때문에 이것을 그대로 사용해주면 된다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제를 보고 priority queue를 떠올리면 쉽게 풀리는 문제였다. priority queue를 간단히 설명하자면 heap으로 구성된 queue로 항상 최대값 혹은 최소값이 root에 있다. priority_queue는 default로는 최대값이 root에 있기 때문에 이것을 최소로 바꾸어주기만 하면된다. 바꾸는 법은 벡터 sort와 마찬가지로 해주면되는데 주의할 점은 최..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 유형을 보고 분할정복을 떠올려 풀어준 문제이다. 각 변을 3씩 나누면서 보면 탐색하는 문제이다. 보면 처음에 9로 시작한다. 모든 원소가 같지 않다면 n/3으로 나누고 각 분면의 시작 좌표로 이동해주어야한다. ​이런식의 좌표가 나온다. y가 행 x는 열. 단계별 풀이 1. 입력을 받아주고 papper 재귀함수로 들어간다. 2. bool 변수 선언 후 각 분면에 있는 원소들을 탐색해..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 처음에 고민을 하다가 팩토리얼 숫자를 그리면서 규칙을 좀 살펴보니 5배수가 곱해질때마다 뒤에 0 이 붙는 것을 보고 이것을 이용해 풀었다. 왜냐하면 10이 곱해지려면 2와 5가 필요한데 2는 항상 5보다 많기 때문에 5가 몇개 있는지 세주면 된다. 주의 해야할 것은 5의 배수중 25 와 같이 5가 2번 곱해진것은 0이 2개가 추가 됨에 주의 해주면된다. 위 방법과 다이나믹 프로그래밍을 이용하여 하나씩 0의 개수를 저장하는데 5배수가 들어있는 수가 곱해지는 차례에는 i-5번..