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) 첫번째 줄에 나온 피연산자의 개수는 괜히 주어진 값이 아니다...
1. 리스트 합집합 lst1 = ['A','B','C','D'] lst2 = ['C','D','E','F'] # 합집합 union = list(set(lst1) | set(lst2)) print( union ) # ['C', 'F', 'A', 'E', 'B', 'D'] union = list(set().union(lst1,lst2)) print( union ) # ['C', 'F', 'A', 'E', 'B', 'D'] set(lst1) | set(lst2) set().union(lst1,lst2) 를 통해 합집합 표현이 가능하다. 2. 리스트 교집합 lst1 = ['A','B','C','D'] lst2 = ['C','D','E','F'] # 교집합 intersection = list(set(lst1) &..
1. round 함수로 소수점 관리하기 round(반올림하고자 하는 값, 반올림하는 자릿수)로 소수점을 관리할 수 있다. a = round(1.23456,0) # 1.0 출력 b = round(1.23456,1) # 1.2 출력 c = round(1.23456,2) # 1.23 출력 d = round(1.23456,3) # 1.234 출력 +) k = round(1.23456) # 1 출력 2. 파이썬 format 서식 지정으로 소수점 관리하기 print("{:.nf}".format(number)) 로 number의 소수점 n+1번째 자릿수에서 반올림해서 소수점 n번째 자릿수까지 출력함으로써 소수점을 관리할 수 있다. print("{:.2f}".format(1.23456)) # 소수점 3번째에서 반올림해..
-목차- 1. 아스키코드란? 2. 아스키코드 변환 함수 아스키코드란? 아스키란(줄여서 ASCIII) 미국 정보교환 부호이다. 즉, 정보교환을 위한 부호로서 기호와 알파벳에 적합한 문자 인코딩이다. (문자 인코딩은 문자열이나 기호를 컴퓨터에서 이용하기 위해 코드화 부호화하는 과정이다.) 아스키코드는 7bit 인코딩으로서 0부터 127까지 알파벳과 기호를 할당한다. 또한 아스키코드는 컴퓨터와 여러 통신 장비에 활용되며 문자 인코딩의 기초다. 0~32까지는 제어용 언어이고 33번부터 64번, 91번부터 96번,123~127은 기호 및 숫자, 65번부터 90은 영어 대문자, 97번부터 122번은 영어 소문자이다. 아스키코드 변환 함수 ① ord() 문자열을 아스키코드로 변환해주는 함수이다. 괄호 안에 문자열을 ..
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 라면 이것을 하나의 괄호에..
