15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번 N과M(1) 문제와 거의 똑같지만 다른 점은, 고른 수열이 오름차순이어야 한다는 점! # 15650번: N과M(2) n, m = map(int, input().split()) visited = [False] * (n+1) result = [0] temp = 0 def backTracking(num): if num == m: print(*result[1:]) return for i in range(1, n+1): if not visited[i] and..
알고리즘/백준
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 파이썬 itertools모듈의 permutations 함수를 사용하면 쉽게 풀 수 있지만 문제의 출제의도와 벗어난다. 백트래킹 문제라고 해서 일단 백트래킹 개념을 공부했다. 백트래킹은 DFS의 향상된 버전이라고 한다. 기본적으로 DFS의 개념을 사용하는데 약간 변형한다. 시간 복잡도는 현재 중복이 불가능하므로 O(N!)이다. (N = 10까지 가능) 중복이 가능한 경우에는 O(N^N) (N = 8까지 가능) n, m = map(int, inpu..
1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 처음에 점과 점 사이의 거리를 구하는 공식을 단순하게 가로 길이 + 세로 길이로 생각해서, 아니 이중 for문을 10000 X 10000으로 어떻게 돌리지? 라고 생각해서 결국 구글링을 통해 풀었다. 알고보니 math라이브러리를 사용해서 직접 점과 점사이의 거리를 구하는 것이었다. 그리고 직접 점과 점사이의 거리를 구하다보니, 접점의 좌표를 직접 구하기는 힘들 수 있다. -> 딱 안떨이지니까 우리가 알고 싶은 건 접점의 개수이기 때문에 두 원 사이의 접점의 개수 공식을 이용해서 풀면 되는 문제다. 고등학교, 아니 ..
2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 아이디어 생각까지 다 했는데 구현을 못했다.. 원래 재귀를 돌면서 별을 출력할 때, 리스트에 넣는게 아니라 그냥 문자열로 출력하게 만들었다. 이렇게 될 경우 print문 * 3 이런식으로 코드가 만들어져서 그냥 컴파일 오류가 발생한다. (print(a) * 3 이런 느낌) 별을 문자열이 아닌 리스트에 넣어서 마지막에 정답 출력할 때, join함수를 통해 별들을 출력해줄 수 있다. def print_star(n): if n == 3: r..
9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 에라토스테네스의 체를 활용해서 풀면 되는 문제다. 특정 짝수를 만드는 두 소수 중에서 두 소수 사이의 차가 적은 친구들이 답이다. temp 변수를 선언해서 최솟값이 for문을 돌때마다 초기화되도록 로직을 작성했다. import math check = [True] * 10001 check[1] = False def erathos(n): for i in range(2, int(math.sqrt(n))+ 1): if check[i]: j = 2 w..
2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 그리디 또는 DP로 풀 수 있는 문제다. 1. 그리디 n = int(input()) total = 0 while True: if n % 5 == 0: total += n // 5 print(total) break elif n % 5 != 0: total += 1 n -= 3 if n < 0: print(-1) break 2. DP n = int(input()) dp = [5001] * 5001 dp[3] = 1 dp[5] = 1 for i in range(6, n+1): ..
07_럭키 스트레이트 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 시간 제한이 1초였고, N도 99,999,999이하인데 어 happenundo.tistory.com
03_문자열 뒤집기 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 happenundo.tistory.com
1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 파이썬 itertools 라이브러리의 combinations를 써서 풀었다. 통과는 했으나 4중 for문까지 들어가므로 성능이 별로라고 생각한다. 자음이 2개 이상 들어가야 한다는 조건을 빼먹어서 틀렸다. 고치니 바로 정답! 내 풀이 # 기타 알고리즘_B_2_암호 만들기 import itertools l,c = map(int, input().split()) temp_list = list(input().split()) # 알파벳 종류 ㅣㅇㅂ력받기 consonants =..
