컴공과고씨

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 n이 되도록 찾는 식으로 풀어 주었다. 배열에 저장하지 않고 연산을 계속하면서 찾을 경우 당연히 연산 시간이 오래걸려 시간초과가 난다. 합이 n이 되도록 할 때 최소 개수의 수로 만들어야 ..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 첫 번째로 ) 나왔을 때 구별 해주어야할 것은 막대기의 끝인지 아니면 레이저인지 구별하는 것이다. ) 나오기 바로 직전이 ( 였다면 레이저이고 )이면 막대기의 끝이다. 이것을 이용하여 ( 나올때 카운트를 해준다. 그리고 ) 나왔을 때 (하나는 사라지는 것이므로 카운트 개수를 -1해준다. ) 나왔을 때 레이저라면 앞에 ( 개수를 세준수 만큼 잘린 막대기 개수가 나오므로 총 막대기 개수에 저장해준다. 만약 막대..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제를 보고 처음에는 당연히 queue를 떠올리기 어려울 수 있지만 한 번 직접 괄호 지우다 보면 queue가 떠올라야한다. 이런식으로 앞에 나온 ( 가 있다면 ) 나왔을 때 (을 지워주는 형식으로 할 것이다. 그런데 만약 남아있는 ( 있거나 ( 가 나오지 않았는데 ) 나온다면 그것도 잘못된 괄호이다. 그래서 큐를 이용하는 것이다. 먼저 ( 일 경우 큐에 push..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 일단 규칙을 파악해보면 n = 7, k=3 일 때 12[3]45[6]7 12[4]57 [1]25[7] 이런식으로 []안에 있는 것을 출력할 것이다. 쉽게 생각해보면 자기 차례가 아닌 것을 뒤로 보내주면 연결이 된다. 12[3]45[6]712[4] 이런식으로 말이다. 바로 queue를 쓰면 쉽게 이 방식을 구현할 수 있다. 자기 차례가 아니면 뒤로 옮겨주고 자기 차례인 경우 pop을 해주면 된다. ps. 출력 형식이 안에 있으니 주의 하도록 하자. 단계별 풀이 1. 정답을 저장할 vecto..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net pair로 받아서 정렬 기준을 바꾸어 주면 된다. vector를 잘 모르면 https://hagisilecoding.tistory.com/53?category=1050177 공부하고 오면 이해하기 편하다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

https://www.acmicpc.net/problem/23284 23284번: 모든 스택 수열 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 www.acmicpc.net 문제를 보고 일단 구해보려고 직접 써보았다. 그러다 보니 떠오른생각이 N-Queen하고 비슷한 문제인 것을 느껴서 백트래킹 쪽으로 생각하게 되었다. 왜 비슷하면 각 자리마다 숫자를 넣을 때 이 숫자를 넣으면 수열이 가능한지 아닌지를 판단 한 후 아니면 다른 수를 넣는식으로 가기 때문에 n-queen도 각 자리에 퀸이 들어갈지 아닐지를 판단하는 문제였어서 비슷하다고 느꼈다. 이..

Marr-Hildreth Edge detector 이 방법은 LoG(Laplactian of Gaussian)라 볼 수 있다. 앞서 배운 것 처럼 gaussian은 거리에 따라 가중치를 다르게 두는 것이고 라플라시안은 2차 미분을 통해서 기울기의 변화량을 측정하는 것이다. 즉 LoG는 가오시안을 2차 미분을 한 것이다. 이 방법은 가오시안 안에 있는 σ를 통해 스케일을 컨트롤 할 수 있다. 가오시안을 통해 잡음을 제거 한 후 라플라시안을 씌우는 2 단계를 한번에 합쳐놓은 것이라고 생각하면 된다. LoG 필터를 적용한 후 zero-crossing 부분을 찾은 후 thresholding을 해주면 경계선을 찾을 수 있다. Canny Edge Detector 이 방법은 경계선을 찾을 때 대부분 사용하는 방법으로..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제같은 경우 다이나믹 프로그래밍에 대표적인 문제라고 할 수 있다. 각 경우에 대해서 최선의 선택을 하면서 가면 되는데 이 말을 이해하기 위해서는 직접해보는 것이 좋다. 표를 직접 그려봤다면 이게 무슨 원리인지 알 것이다. 자신이 채우고 있는 행의 최선의 선택은 1. dp[i][j] = dp[i][j-현재 물건 무게] + 현재 ..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 문제를 읽고 bfs를 떠올렸다. 아이디어 백신 놓기 전과 결과를 비교한다. 여기서 만약 다른게 나오면 bfs를 돌려서 숫자를 결과의 값으로 바꾸어 주고 백신은 한번만 놓을 수 있기 때문에 비교를 멈춘다. 그 후 바뀐 값과 주어진 결과를 비교해서 하나라도 다른 값이 있다면 no를 다 똑같다면 yes를 출력해주면 된다. 단계별 풀이 1. 입력값 받을 두 개의..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이런 문제의 경우 각 경우 마다 최적의 경우의 수를 선택하면서 가면 된다. 저런식으로 각 자리를 늘려가면서 A에서 C가 들어갔을 때 LCS의 경우 0 AC와 C의 LCS = 1 이런식으로 표를 채워가준다. 중요한 것은 LCS가 하나 더 늘어나는 경우는 문자가 들어갈 수 있을 때 예를 들면 ACAYK 와 CAP 다음 순서에 ACAYKP 와 CAP가 나온다..