컴공과고씨

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

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