나는 오늘 무엇을 했는가

음~ 오랜만~ 심심할때마다 알고리즘 문제를 하나씩 풀려고 한다. 보니까 자주 업데이트 되는거 같고, 단계별로 풀어보기도 이것저것 많이 나왔길래 풀어봐야지 싶다 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 생각의 흐름 1. 입력값 확인 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 5..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 생각의 흐름 1. 입력값 확인 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) 2. 생각의 흐름 입력값이 1000개밖에 들어오지 않기 때문에 자리 하나하나를 다 검사하는 방향으로 생각했다. 가장 긴 증가하는 부분수열에서 아이디어를 가지고 오고, 거꾸로 뒤집어서 다시 가장 긴 증가하는 부분수열을 구한 뒤 둘을 더하..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 생각의 흐름 1. 입력값 확인 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 2. 생각의 흐름 들어오는 숫자의 갯수가 10만개이기 때문에 모든 경우를 for문 돌려가며 찾는데는 한계가 있다. dp로 해결하기 위해 과정을 생각해 보았다. MAX 값을 찾기 위해 총 3가지..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 생각의 흐름 1. 입력값 확인 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다. 2. 생각의 흐름 2579 계단오르기 와 유사한 문제라고 생각했다. 규칙을 찾으려고 했고, 2개전, 1개전 단계를 보고 판단을 했다. 따라서 리스트 배열의 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 1. 입력값 확인 N은 1보다 크거나 같고, 100보다 작거나 같은 자연수 정답을 1,000,000,000으로 나눈 나머지를 출력 2. 생각의 흐름 계단수는 특징을 가진다. 0, 9일때는 다음에 1, 8밖에 나오지 않는다. 그 외의 수는 다음에 두가지 숫자가 나올 수 있다. 진행과정은 다음과 같다. (처음에는 4번째까지 다 손으로 직접 그려 보았다) 3. 결론 손으로 그려봐도 규칙을 찾기 어려웠다. 많은 문제를 경험 해 보는 수 밖에 없을 것 같다. Code #-*- coding: utf-8 -*-..