출처 : 백준, https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 더보기 쉬운 풀이 from itertools import permutations if __name__ == '__main__': n, m = map(int, input().split()) num_arr = [i for i in range(1, n + 1)] per_n = permutations(num_arr, m) for li in per_n: for num in li: prin..
출처 : 백준, https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 의외로 시간초과가 안 떠서 놀랐던 문제 당연히 시간초과 뜰 줄 알았는데 더보기 첫 번째 풀이 : 실패 def Goldbach(n, prime_set): a, b = n//2, n//2 for i in range(0, a): if a in prime_set and b in prime_set: print('%d = %d + %d' % (n, a, b)) retu..
출처 : 백준, https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 더보기 풀이 if __name__ == '__main__': n = list(input()) if '0' not in n: print(-1) elif sum(map(int, n)) % 3 != 0: print(-1) else: print(''.join(sorted(n, reverse = True))) 30의 배수이려면 1. 3의 배수이면서 2. 10의 배수이면 된다. 3의 배수이기 ..
본 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리하는 글입니다. 피보나치의 재귀 def Fibonacci(n): if n == 1 or n == 2: return 1 return Fibonacci(n-1) + Fibonacci(n-2) 피보나치의 수열을 재귀함수로 구현했다고 하자. 이전의 두 수의 합이 다음의 수가 되는데, 만약 F(5)를 구하기 위해서 위와 같은 재귀함수를 작성했다면 그림과 같이 함수가 호출되어 구해질 것이다. 문제는 색깔로 구분되어있듯 같은 값을 계속 호출하여 또다시 계산한다는 점이다. 한 번 계산한 값을 다시 계산한다니 듣기만 해도 비효율적인데 호출횟수가 늘어나면 매우 비효율적이 된다. 이 문제를 해결하려면 어떤 방법을 쓰면 될까? 첫째로는 값을 처음 계산할 때 ..
출처 : 백준, https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 더보기 첫 번째 풀이 : 실패 if __name__ == '__main__': n = int(input()) count = 0 while n != 1: if n % 2 == 1: #홀수 if n % 3 == 0: n //= 3 else: n -= 1 else:#짝수 if n % 3 == 0: n //= 3 else: if (n-1) % 3 == 0: n -= 1 else: n //= 2 count += 1 print(count) 125 10 #8 두 번째 풀이 : 실패 if __name__ ==..
출처 : 백준, https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 소수만 2연속 참고 : 에라토스테네스의 체 프로그래머스 - 소수 찾기 백준 1978 - 소수 찾기 더보기 풀이 if __name__ == '__main__': A, B = [int(input()) for _ in range(2)] num_set = set(i for i in range(A, B+1)) max_num = max(num_set) if 1 in num_set: num_set.rem..
출처 : 백준, https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 참고 : 에라토스테네스의 체 프로그래머스 - 소수 찾기 더보기 풀이 if __name__ == '__main__': n = int(input()) num_set = set(map(int, input().split())) max_num = max(num_set) if 1 in num_set: num_set.remove(1) for i in range(2, int(max_num ** 0.5) + 1): num_set -= set(j for j in ra..
출처 : 백준, https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 더보기 풀이 if __name__ == '__main__': a, b = map(int, input().split()) num_arr = [i for i in range(1, 46) for _ in range(i)] print(sum(num_arr[a-1:b])) 이 풀이가 맞는지를 잘 모르겠는데 난 이렇게 풀었다. 먼저, 시작과 끝을 나타내는 입력 A, B가 1 ≤ A ≤ B ≤ 1000이므로 배열의 ..
출처 : 백준, https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이거 한국정보올림피아드 지역부 본선 초등부 문제인걸 알면 얼마나 많은 사람들이 절망에 빠질까 일단 난 빠졌다.......... 더보기 첫 번째 풀이 : 실패 if __name__ == '__main__': n = int(input()) stairs = [int(input()) for _ in range(n)] visited = [-1] * n visited[n-1] = 1 stairs[n-1]..
출처 : 백준, https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 더보기 첫 번째 풀이 : 시간초과 if __name__ == '__main__': w, h = map(int, input().split()) position = list(map(int, input().split())) target = int(input()) dx = 1 dy = 1 time = 0 while True: if time == target: break ..
출처 : 백준, https://www.acmicpc.net/problem/2693 2693번: N번째 큰 수 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000 www.acmicpc.net 더보기 풀이 if __name__ == '__main__': num_arrs = [sorted(list(map(int, input().split()))) for _ in range(int(input()))] for num_arr in num_arrs: print(num_arr[-3]) 와 파이썬 너무 신기해 시간 복잡도 O(NlogN) 다른 사람의 풀이를 ..
출처 : 백준, https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 와 문제 더럽다 더보기 풀이 from collections import Counter import sys if __name__ == '__main__': arr = [int(sys.stdin.readline()) for _ in range(int(input()))] arr.sort() L = len(arr) avg = int(round(sum(arr) / len(arr), 0)) middle =..
