https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '2xn개의 크기의 직사각형을 1x1,1x2로 채우는데.. n=1,n=2....의 과정 및 결과를 비교하며 규칙이 있는지 파악할 것 같은디...??'였다. ② 아이디어 열기 (1) 과..
Algorithm
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) 첫번째 줄에 나온 피연산자의 개수는 괜히 주어진 값이 아니다...
https://www.acmicpc.net/problem/2743 2743번: 단어 길이 재기 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. 풀이 과정 나의 풀이 ① 이 문제에서 직관적으로 파악한 것은 '특정 문자열이 주어지고 문자열의 길이를 재야하는구나'이다. ② 아이디어 열기 주어진 단어를 리스트화시키고 리스트 메서드 len을 사용하면 쉽게 풀릴 것 같다. 이를 실제 코드에 구현하면 다음과 같다. # 2743 word = input() word_lst = list(word) print(len(word_lst)) 후기 리스트개념을 알면 너무나도 쉬..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 설명 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에..
https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제 설명 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금..
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 설명 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판(맨 위의 원판)만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 ..
