https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 설명 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, ..
파이썬
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 풀이 과정 나의 풀이 ① 처음 이 문제..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 설명 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 풀이 과정 나의 풀..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '위에서 아래로 순차적으로 진행되는 과정 속에서 최대인 경우를 찾는 것이니깐... DP문제인가...?'였다. ② DP문제인듯한 느낌을 받은 상태에서 예제문제의 과정을 직접 수행해보며 확인해보았다. 위에서 아래로 내려오며 빨간 O표 부분은 과정 속에서 최선의 방법이고, 빨간 X표 부분은 과정 속에서 버려지는 부분이다. ③ 아이디어 열기 (1) 입력값 처음 입력되는 값인 5값은 5줄의 삼각형 크기의 숫..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 설명 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입..
[백준] 9095 1,2,3 더하기 (파이썬 Python) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 설명 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '정수 n을 숫자 1,2,3을 이용해 1,2,3의로만 이루어진 숫자합을 구성..
https://www.acmicpc.net/problem/11727 문제 설명 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '11726문제와 같이 DP문제이고, 결과 혹은 과정에 의한 규칙이 분명 존재하겠구나'이다. ② 아이디어 열기 우선 n의 값에 따른 문제의 과정과 결과에 대해 알아보자. n = 1 ; 1 n = 2 ; 3 n = 3 ; 5 n = 4 ; 11 n = 5 ; 21 n = 6 ; 43 ... 결과에 의해서는 한눈에 규칙이 안보인다. 그러므로 과정에 집중해보자..! n = 4인경우 경우의 수는 n = 3인 경우에서 2x1..
1. dp란 dp, dynamic programming의 줄임말이다. dp는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 또한 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이라고 흔히 말한다. dp의 핵심은 앞서 말한 수행 시간 효율성의 비약적 향상인데 이는 '메모이제이션'이라는 기법을 이용해 이미 계산된 결과(작은 문제)를 별도의 메모리에 저장해 다시 계산하지 않고 필요한 경우 사용하는 방식이다. 이 기법을 사용하면 시간복잡도가 훨씬 줄어들기에 수행 시간 효율성이 비약적으로 향상한다. 2. dp 문제 유형 dp문제의 조건은 두가지이다. 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제..
https://www.acmicpc.net/problem/11718 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net 문제 설명 입력 받은 대로 출력하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '입력값이 몇 번 주어지는지는 모르지만 입력된 값 그대로 출력해야한다는거구나'이다. ② 아이디어 열기 입력값이 몇 번 주어지는지는 모르겠는데... 입력값이 그대로 출력해야한다라.. try,except 구문을 통해 입력값이 계속 들어오면 그대로 프린트해주고, 입력..
https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 문제 설명 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '두번째 줄에 후위 표기식이 주어지고 3번째줄부터 피연산자에 대응하는 값이 주어져 후위표기식을 계산하여 출력하는 거구나'이다. ② 아이디어 열기 (1) 첫번째 줄에 나온 피연산자의 개수는 괜히 주어진 값이 아니다...
