rainyCode rainyCode

백준 11053번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 이 문제는 특히 실버2의 난이도를 갖고 있는 만큼 생각을 많이 해야지만 규칙을 파악할 수 있다. 문제 링크 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 알고리즘 규칙을 파악하기 까다로운 문제이다. 먼저, 가장 긴 증가하는 수열이 되기 위해서는 처음부터 각 원소의 최대 증가길이를 생각해볼 필요가 있다. 예를 들어, 위의 예시에 주어진대로 10 20 10 30 20 50 수열에서는, 10 20 의 각각의 수열의 길이는 1,2 가 된다. 하지만 3번째 ..

백준 1149번 RGB거리 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 문제 링크 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 cnt [1001][3]라는 이중 배열을 선언해 cnt [n][o]은 n 번째 집을 빨간색으로 칠할 때 최솟값, cnt [n][1]은 n 번째 집을 초록색으로..

백준 2193번 이친수 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 문제 링크 2193번: 이친수 (acmicpc.net) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 알고리즘 // 1 // 10 // 100 101 // 1000 1010 1001 // 10000 10100 10010 10001 10101 이친수는 0으로 시작하지 않고 1이 두 번 이..

백준 11726번 2xn 타일링 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 문제 링크 11726번: 2 ×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 알고리즘 실버 3 문제인데 생각보다 안 떠올라서 어렵게 느껴졌다. 결국 노가다하다가 규칙은 찾아내었는데 마지막에 값이 너무 커지는 걸 생각을 못해, 마지막 출력에만 10007로 나누어주었다가 틀렸다...

문제 링크 5052번: 전화번호 목록 (acmicpc.net) 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 알고리즘 문자열 배열을 선언해 입력받은 값들을 오름차순으로 정리한다. 오름차순으로 정리했을 때, 앞에 있는 값이 뒤에 있는 값보다 문자열 길이가 길다면 절대 뒤에 값에 포함될 수 없기 때문에 continue로 즉시 연산을 종료해준다. ex) 12345 1345 2345 235... substr()을 이용해 시작 부분과 원하는 만큼의 길이를 인자로 넣어서 부분 문자열을 반환하도록..

문제 링크 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 알고리즘 find()와 substr()를 사용해서 while문 무한루프를 돌며 문자열을 찾고 그 앞뒤를 이어 붙이는 방식으로 했는데 2%에서 시간 초과가 나버렸다. find함수를 썼을 때 시간 복잡도가 최대 O(n^2)까지 늘어나니 문자열 한 번만 돌면서 폭탄을 지워줘야 했고, 그렇기 때문에 stack 방식을 활용했다. 문자열을 앞에서부터 돌면서 하나씩 빈 문자열(temp)에 추가한다. ..

https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net substr() - C++ string헤더에 들어있는 부분 문자열 추출 함수. - 시작 지점과 길이를 전달하면 인덱스 시작 지점부터 길이만큼 문자열 반환. string.substr(시작 지점, 길이) - 기본값으로 시작 지점은 0, 길이는 문자열 보다 더 긴 길이가 들어오면 마지막 문자까지만 리턴. - 파라미터를 입력하지 않으면 기본적으로 전체 문자열 리턴 #include #include #include using namespace std; int main(){ ios_bas..

문제 링크 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 알고리즘 문자열 형태로 받은 수를 먼저 내림차순으로 정리를 해버리고 30의 배수가 되는지 안되는지 판별 후에 전자의 경우 그대로 출력하고 후자의 경우 -1을 출력한다. 30의 배수 판별법 1. 0으로 끝나야 한다. 2. 각 자리 숫자의 합이 3의 배수여야 한다. 예전에 수학 문제 풀 때 써먹던 기억이 어렴풋이 나면서 어렵지 않게 떠올릴 수 있었다. 30 배수 판별법만 잘 정리해주면 코드 ..