algorithm122 [Python] 백준 1182번 : 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 💡 문제 풀이 브루트 포스 문제이다. 부분 수열을 만들어서 합이 목표값과 같은지만 확인해주면 된다. itertools의 combination을 사용하면 부분 수열을 쉽게 만들 수 있다. ✔️ 느낀 점 그렇게 어려운 문제는 아니었다. 💻 코드 import sys from itertools import combinations input = sys.stdin.read.. 2022. 7. 31. [Python] 백준 2623번 : 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 풀이 그래프 이론 중 위상정렬 문제이다. 위상정렬 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다. 느낀 점 위상정렬에 대해서 한번 짚고 넘어갈 수 있는 문제가 되었다. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] indegr.. 2022. 7. 31. [Python] 백준 1107번 : 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 💡 문제 풀이 브루트 포스 문제이다. 모든 경우를 따져주면 된다. 백만까지 범위의 모든 숫자를 따져서 가장 낮은 값을 찾아주면 된다. 주어진 범위는 50만까지인데 더 따지는 이유는 500,000 채널을 가려고 하는데 1, 2, 3, 4, 5가 고장 났을 경우 100에서 499,900번을 누르는 게 정답이 아니라 600,000에서 100,000번을 - 누르는게 정답인 경우가 있기 때.. 2022. 7. 30. [Python] 백준 1759번 : 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡 문제 풀이 백트래킹 문제이다. 주어진 길이까지 백트래킹을 실시하고 주어진 조건만 맞추면 된다. 백트래킹의 기본이라고 볼 수 있다. ✔️ 느낀 점 브루트포스인 줄 알고 풀었는데 백트래킹 문제였다. 💻 코드 import sys l, c = map(int, sys.stdin.readline().split()) words = sorted(list(map(str, sys.stdin.readline().spl.. 2022. 7. 29. [Python] 백준 1577번 : 도로의 개수 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 💡 문제 풀이 DP 문제이다. 이 문제는 메모리의 크기는 작긴 하지만 n, m의 100까지므로 배열을 사용해도 괜찮다. 최단거리로만 이동하기 때문에 항상 아래 혹은 오른쪽으로만 이동한다는 점이 포인트이다. 주어진 (a,b), (c,d)에 대해서 어떤 점이 못 가는 점인지 판단하기 까다롭다는 생각에 방향에 따라 이동 가능 여부를 따지려고 4차원 배열까지 가고 마지막 배열에 boole.. 2022. 7. 26. [Python] 백준 2110번 : 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💡 문제 풀이 이분 탐색 문제이다. 입력받은 집의 위치를 정렬해서 이분 탐색을 진행한다. 이분 탐색 시 mid는 공유기 사이의 거리를 의미한다. 따라서 최소거리는 1, 최대 거리는 마지막 집과 처음 집의 간격이다. 지금 설치하려는 위치가 확인하는 간격(mid)을 벗어나는지 확인하면서 설치한 공유기 개수를 세어준다. 설치한 개수가 c보다 크다면 간.. 2022. 7. 26. 이전 1 ··· 9 10 11 12 13 14 15 ··· 21 다음