본문 바로가기
반응형

백준

[백준] 1463번 - 1로 만들기 (파이썬 코드) (feat. DP) 1. 문제 https://www.acmicpc.net/problem/1463 2. 코드 n = int(input()) dp = [0 for i in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i%3 == 0: dp[i] = min(dp[i], dp[i//3]+1) if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) print(dp[n]) 3. 알고리즘 점화식 : dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1 1) 1을 빼준 경우를 우선 저장해놓는다. 2) 3으로 나뉠 경우, 1을 빼준 경우와 비교해서 최솟값을 저장한다. 3) 2로 나뉠 경우, 1을 빼준 경우(만약 2)에서 3으로 .. 더보기
[백준] 2108번 - 통계학 (파이썬 풀이) (feat. collections, sys) 1. 문제 https://www.acmicpc.net/problem/2108 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. (시간 초과 때문에 왕왕 고생한 이번문제,,,,,) 2. 코드 from collections import Counter import sys n = int(input()) .. 더보기
[백준] 10989번 - 수 정렬하기 3 (파이썬) (feat. 정렬하지 않고 정렬하기,,?) 1. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. (문제는 쉬우나 메모리 제한이 아주 빡센 문제이다.) 2. 코드 import sys n = int(input()) l = [0 for i in range(10001)] for i in range(n): l[int(sys.stdin.readline())] += 1 for i in range(10001): for j in range(l[i]): sys.stdout.write(str(i) + '\n') 3. 주요 포인트 이 문제는 메모리 공간 제한이 아주 심한 문제이다. 그냥 sort를 사용하면 바로 메모리초과 발생이다. 따라서 절대 sort를 해서는 안된다. 그렇다면 어떻게 sort를 하는가? 1~10000이 input .. 더보기
[백준] 2751번 - 수 정렬하기 2 (파이썬 코드) (feat. sys.stdin / sys.stdout) 1. 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. (문제는 매우 간단하지만,,,, 시간 초과가 발생이 아주 잦은 문제) 2. 코드 #https://www.acmicpc.net/problem/2751 import sys n = int(input()) num_list = [] for i in range(n): num_list.append(int(sys.stdin.readline())) num_list.sort() for i in range(len(num_list)): sys.stdout.write(str(num_list[i])+'\n') 3. 주요 포인트 평소와 같이 input()이나 print()를 쓰면 돌아가지 않는다. 시간 초과 발생한다. sys를 import해서 .. 더보기
[백준] 2581번 - 소수 / 파이썬 코드 1. 문제 https://www.acmicpc.net/problem/2581 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 2. 코드 #https://www.acmicpc.net/problem/2581 min_n = int(input()) max_n = int(input()) sosu = [] for i in range(min_n, max_n+1): flag = 0 if i != 1: for j in range(.. 더보기
[백준] 2869번 - 달팽이는 올라가고 싶다 1. 문제 2. 코드 #https://www.acmicpc.net/problem/2869 a, b, v = map(int, input().split()) n = (v-b)//(a-b) if (v-b)%(a-b) != 0: print(n+1) else: print(n) 더보기
[백준] 2292번 - 벌집 1. 문제 https://www.acmicpc.net/problem/2292 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 2. 코드 #1: 1(0) / 2: 6(6)(2~7) / 3 : 12(18)(8~19) / 4: 18(36)(20~37) n = int(input()) cnt = 1 temp = 6 while n-1 > 0: n -= temp cnt += 1 temp.. 더보기
[백준] 10809번 - 알파벳 찾기 (feat. 문자 ascii로 변환) https://www.acmicpc.net/problem/10809 1. 문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 2. 코드 #https://www.acmicpc.ne.. 더보기
반응형

티스토리툴바