오뚝이개발자

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 DP를 사용해 쉽게 풀 수 있는 문제이다. input으로 주어진 각 수는 아래의 연산 중 한 가지를 할 수 있다. 2로 나누어 떨어지면 2로 나눈다. 3으로 나누어 떨어지면 3으로 나눈다. 1을 뺀다. 이를 반복해서 결과적으로 1이란 수를 만들어야 하는데, 이를 DP의 점화식과 연관지어 생각해보면 쉽다. 만약 내가 10이란 수를 input으로 받는다고 가정해보자. 10->5->4->2->1 10->9->3->1 10->9->8->7->...->1 위의 경우 말고도 10을 1로 만들기 위해선 굉장..

문제 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 나의 풀이 양끝에서부터 하나씩 이동시켜가면서 서로 문자를 비교해보면 된다. 왼쪽에서 오른쪽으로 가는 포인터를 l, 오른쪽에서 왼쪽으로 가는 포인터를 r이라고 하자.(two pointer 방식) l = 0, r = len(a)-1로 초기화 해주고 a[l]과 a[r]을 서로 비교해준다. a[l] == a[r] -> l += 1, r -= 1 a[l] != a[r] -> print("no")하고 break 여기서..

문제 https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 나의 풀이 사실 처음엔 itertools 모듈의 중복조합을 사용해 구했다. 물론 답은 맞았지만 조금 더 nice해 보이는 코드가 있어 첨부한다. 이 문제는 브루트 포스 문제로 그냥 가능한 경우를 모두 카운트 해주면 된다. 문제에서 주어진 조건 중 1000이하의 자연수만 입력으로 주어진다고 했기 때문에 1000 이하의 모든 유레카 수를 구해두면 된다. eureka라는 flag 배열을 ..

문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 나의 풀이 위상 정렬을 사용해 푸는 대표적인 문제이다. 위상 정렬의 개념을 모르겠으면 이 글을 참조하기 바란다. 코드 # https://www.acmicpc.net/problem/2252 n, m = list(map(int, input().split())) # adjacent list adj_list = [[] for _ in range(n+1)] ..

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 생각의 흐름 알파벳마다 중요도를 계산한다. 이 때, 중요도는 해당 알파벳이 등장하는 자릿값을 더해주는 것이다. 예를 들어, ABCDE가 주어졌다면 A의 중요도는 10000이 되는 것이다. 모든 알파벳의 중요도를 계산한 후 중요도가 큰 순서대로 9부터 순차적으로 할당해주면 된다. 깨달은 점 파이썬에서 아..

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 dp[i]에 i를 1, 2, 3 더하기로 i를 만들 수 있는 경우의 수를 저장한다. 동적 프로그래밍을 위한 점화식은 dp[i]=dp[i-1] + dp[i-2] + dp[i-3]이 된다. 이처럼 이전의 3항까지만을 더해주는 이유는 1, 2, 3으로 만드는 수이기 때문에 3만큼 작은 수를 만들 수 있는 가짓수를 더해주면 3이라는 수로 그 부족분을 보충해줄 수 있기 때문이다. 코드 # 백준 15988 t = int(input()) dp..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 생각의 흐름 dp[i]에는 i라는 수를 만들기 위해 필요한 제곱수들의 최소 항의 갯수를 계산해 저장한다. 그 후 j를 1부터 sq..

문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. www.acmicpc.net 생각의 흐름 각 자리에 있는 수를 선택하였을 때 올 수 있는 가장 큰 합을 dp 리스트에 저장한다. 예를 들어, 문제에서 예시로 주어진 arr = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]의 경우 dp = [1, 10..