컴공과고씨

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가 나온다..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 직접 도형을 그려보면서 어떤 규칙이 있는지 보았지만 도형 모양안에서 규칙을 찾기는 힘들었다. 그래서 고민하다가 도형 개수에 대한 규칙을 찾아서 풀었다. 도형의 개수 1 -> 1개 2 -> 2개 3 -> 3개 4 -> 5개 5 -> 8개 6 -> 13개 직접 그려보면 이렇게 개수가 나온다. 그럼 점화식이 보인다. n = (n-1) + (n-2) 근데 중요한 것은 문제에 보면 10007로 나눈 나머지를 구하는 것이다. 해..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제를 보고 규칙이 있을 것 같아서 쭉 써보았다. 1 -> 1개 2 -> 2개 3 -> 4개 4 -> 7개 5 -> 13개 여기서 점화식을 알아낼 수 있는데 n = (n-1) + (n-2) + (n-3)번째 라는 점화식을 볼 수 있었다. 점화식은 다이나믹 프로그래밍으로 풀면 쉽게 풀 수 있어 다이나믹 프로그래밍을 이용하여서 문제를 풀었다. 단계별 문제 풀이 1. dp 배열 선언 2. 초기값 dp[1], dp[2], dp[3] 값 입력 3. 점화식을 이용해서 풀어줌 전체코드 1 2 3 4 5 6 ..