컴공과고씨

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 ..

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을 이용하는 방법으로 ..

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 변수 선언 후 각 분면에 있는 원소들을 탐색해..