프로그래밍
-
코테 일기(12) : 백준 [11047번] 동전 0프로그래밍/C++ 2020. 4. 23. 17:57
전형적인 그리디 알고리즘이다. 그리디 알고리즘(Greedy Algorithm) 이란? 매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘이다.Dijkstra와 다르게 현재 노드에서 다음 노드까지만 생각하는 "오늘만 사는 알고리즘" 이라고 할 수 있다. 그래서 그리디 알고리즘 자체의 난이도가 낮을 수 밖에 없다. 무한한 while문 속에서 현재에 해당하면 continue, 해당하지 않으면 break와 같은 극과 극의 알고리즘이다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int get_coin(vector coin, int value) { int count = 0; int i = coin...
-
코테 일기(11) : 백준 [1780번] 종이의 개수프로그래밍/C++ 2020. 4. 22. 20:28
전형적인 divide and conquer 문제이다. 코드를 짜는데 30분 밖에 걸리지 않았지만, 그 놈의 시간초과 때문에 한참을 애썼다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int pr[3]; //pr[0] -> -1, pr[1] -> 0, pr[2] -> 1 vector input; //입력 받을 배열 typedef struct { int row; int col; } place; void div_paper(int param, place pl) {//배열과 배열 크기, 위치를 인자로 넣음 if (param == 1) { //크기가 1개면 바로 return 할 수 있게 함. if (input[..
-
코테 일기(10) : 백준 [1051번] 숫자 정사각형프로그래밍/C++ 2020. 4. 21. 23:11
DP(Dynamic Programming)를 풀다가 머리가 아파서 잠깐 brute force로 돌렸다... 역시 어려운 것을 하다가 쉬운 것을 풀면 너무 빨리 풀린다. 총 코딩 시간 10분, 삽질 20분... 정답률 37%는 아무래도 오답을 했던 기록까지 포함해서 인지 상당히 낮다. 하지만 난이도는 초보자도 풀 수 있을 정도라는 것. (전형적인 brute force 문제이다.) 코드 #include #include #include using namespace std; int find_square(vector arr) { int result = 1; for (int i = 0; i < arr.size(); i++) { // 행 위치 for (int j = 0; j < arr[0].size(); j++) {..
-
코테 일기(9) : 백준 [2178번] 미로찾기(BFS)프로그래밍/C++ 2020. 4. 21. 18:06
이번에 풀 문제는 백준 2178번 미로찾기이다. DFS, BFS는 꼭 알고 가야 하는 탐색기법이기에 풀어보기로 했다. 정답률은 35%로 충분히 풀만한 오기가 생겼다. 처음엔 실력도 모자란 내가 풀어도 될까? 라는 마음이 들었지만 언젠간 넘어가야 할 산이다. 처음 든 생각 DFS로 stack을 사용해서 푸는것이 더 편해 보였다. 하지만 문제에서는 BFS를 요구했으니 넓이 탐색으로 풀기로 했다. 연속된 1을 통해 array의 마지막에 도달하는 것이 우리 최종 목표이다. 먼저 queue의 size가 0 이 아닌 한 반복을 해야 할 것이고 while (queue.size() > 0) queue의 front를 받아와서 한 단계 씩 나아가야한다. (queue.front()) 이후 상하좌우를 모두 검색하여 1이 존재..
-
코테 일기(8) : 하노이탑(The tower of Hanoi)프로그래밍/C++ 2020. 4. 20. 14:02
하노이탑은 Divide and Conquer(정복 분할 기법)에서 가장 많이 다뤄지는 문제 중 하나다. A에서 B를 거쳐 C로 옮기기 위해 하노이 탑의 순서는 다음과 같다. 1. (1,2)를 B로 옮긴다. 2. (3)을 C로 옮긴다. 3. (1,2)를 C로 옮긴다. 이를 코드로 그대로 옮기면 다음과 같다. Code //하노이탑 만들기 #include using namespace std; int hanoi(int a, int b, int c, int d); int main() { int N; cout
-
Computer Vision(Gaussian Filtering)[4]-Hybrid Image프로그래밍/Python 2020. 4. 20. 13:25
저번 시간에 Color로 blur된 아인슈타인을 출력해보았다. 이번 시간에는 high frequency image를 출력해 이 두 사진을 합성하는 hybrid Image를 출력해보겠다. 먼저 high frequency image를 만드는 함수이다. High Frequency Image 코드 간단하다. Image에 low frequency를 제거하면 high freqeuncy가 남는데 이를 이용한 것이다. 128을 더해주는 이유는 negative value에 대한 방지이다. 가능한 value의 범위의 mean 값을 더해주면 된다. 다음은 이 high frequency image를 출력하는 코드이다. 실행 코드 실행 결과 이렇게 high frequency만 남은 Image가 출력이 된다. 이제 Low fre..
-
Computer Vision(Gaussian Filtering)[3]프로그래밍/Python 2020. 4. 20. 13:07
이번 시간에는 Color(RGB)로 Blurring한 이미지를 출력해보겠다. 처음 이 문제를 풀 때는 머리가 하얬다. '2차원 배열에 RGB를 넣으려면 어떻게 해야하지?' 라는 생각이 맴돌았다. 해결 방법은 3차원 배열이었다. [행][열][RGB] 라는 배열을 사용하면 간단했다. gaussian filter와 convolve 할 함수를 만들어보았다. Convolve Color 코드 zero-padding을 할 때, 3차원의 RGB에는 padding을 해 줄 필요가 없기 때문에 (0,0)으로 패딩을 시키지 않는다. 이를 rot90() 함수를 통해 180도 회전시키고, RGB가 추가된 배열을 선언한다. 이 배열의 각 R, G, B에 맞게 각각 연산을 해주었다. 세 번 수행하는 for loop를 사용해도 되지..
-
Computer Vision(Gaussian Filtering)[2]프로그래밍/Python 2020. 4. 20. 12:27
30분 넘게 글 쓰다가 인터넷이 팅겨서 다시 씁니다... 정말 성심성의껏 글쓰고 있었는데 이렇게 날라가니까 슬프네요... -------------------------------------------------------------------- 저번 시간에 앞서서 우리는 gaussian filter를 만들었다. 이번 시간에는 convolve 함수와 이미지를 사용하여 실제로 블러된 이미지를 출력하는 시간을 가지도록 하겠다. convolve 코드 필터의 크기로 부터 padding 시켜야 하는 정도가 구해진다. pad함수에 constant라는 zero-padding 파라미터를 넣어 이미지를 zero-padding 시킨다. 위의 그림은 convolution 방법이다. 즉, w * f는 blur처리된 이미지의 한..