분류 전체보기
-
[백준] 14889번 스타트와 링크 (by Python)Programming/Algorithm 2021. 3. 2. 17:42
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 첫 번째 풀이 처음 생각하게 된 풀이는 브루트 포스 방식입니다. itertools의 combination을 이용해 가능한 조합들을 모두 구하고 그에 따른 각 팀의 능력차를 구하는 방법인데, 여기서 (1, 2, 3, 4) / (5, 6, 7, 8)로 팀이 나뉘었을 때와 (5, 6, 7, 8) / (1, 2, 3, 4)로 팀이 나뉘었을 때를 별도의 경우로 보면 시간복잡도가 더 커지므로 이를 해소하기 위해 우리 팀에는..
-
[백준] 1107번 리모컨 (by Python)Programming/Algorithm 2021. 2. 28. 19:51
문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 nums = set(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']) n = int(input()) m = int(input()) if m: broken = set(input().split()) nums -= broken ans = abs(n - 100) if nums: i = 0 while True: left = 0 if n ..
-
[백준] 9663번 N-Queen (by Python)Programming/Algorithm 2021. 2. 28. 17:54
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 def n_queens(col, i): if (promising(col, i)): if i == n: global ans ans += 1 else: for j in range(1, n + 1): col[i + 1] = j n_queens(col, i + 1) def promising(col, i): k = 1 flag = True while k < i and flag: if col[i] == col[k..
-
[백준] 2225번 합분해 (by Python)Programming/Algorithm 2021. 2. 28. 17:34
문제 0 이상 N 이하의 정수 K개를 더해 N을 만든다고 할 때, K가 1이면 N이 어떤 수든 방법은 1가지이다. 이러한 리스트를 dp_k로 나타낸다고 하면 dp_1은 길이가 n인 [1, 1, 1, 1 ...] 의 모습을 하고 있을 것이다. 그리고 2 이상의 k에 대해서는 dp_k[i] = sum(dp[:i + 1])이다. 풀이 n, k = map(int, input().split()) dp = [1] * (n + 1) k -= 1 while k: next_dp = [1] * (n + 1) for i in range(1, n + 1): next_dp[i] = sum(dp[:i + 1]) dp = next_dp[:] k -= 1 print(dp[-1] % 1000000000)
-
[백준] 1699번 제곱수의 합 (by Python)Programming/Algorithm 2021. 2. 28. 17:19
문제 비슷한 문제인 1, 2, 3 더하기가 있지만 이 문제는 1, 2, 3이 아니라 n과 같거나 작은 모든 제곱수를 다 고려해야한다는 점에서 시간복잡도가 더 높은 문제이다. 그래서 Pypy3 환경에서만 성공할 수 있었다는 아쉬움이 있지만 이 문제에서 요구한 사고력은 내 풀이로도 충분하다고 생각해 더 이상의 최적화를 시도하진 않았다. 풀이 from math import sqrt n = int(input()) sq_num = [i ** 2 for i in range(1, int(sqrt(n) + 1))] dp = [1 if i in sq_num else i for i in range(n + 1)] for i in range(2, n + 1): for j in range(1, int(sqrt(i)) + 1):..
-
[백준] 14002번 가장 긴 증가하는 부분 수열 4 (by Python)Programming/Algorithm 2021. 2. 21. 21:52
문제 이 문제의 원형인 11053번에서 꽤나 애를 먹어서 어떻게 꼬아놨을까 조금 긴장했지만 생각외로 쉽게 풀렸던 문제. 경로를 기억해두는 장치만 해두면 되는 문제였다. 풀이 n = int(input()) arr = list(map(int, input().split())) dp = [[1, i] for i in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j] and dp[i][0] < (dp[j][0] + 1): dp[i] = [dp[j][0] + 1, j] temp = dp.index(max(dp)) route = [temp] while dp[temp][1] != temp: route.insert(0, dp[temp][1]) temp..
-
[백준] 11053번 가장 긴 증가하는 부분 수열 (by Python)Programming/Algorithm 2021. 2. 21. 21:22
문제 내가 생각했던 것은 bottom-up 방식으로 for loop으로 0번째부터 i번째까지의 LIS(Longest Increasing Subsequence) 값을 저장해둔다는 것. 그렇지만 점화식을 세우는 것이 쉽지 않았는데, 이전 원소들의 정보를 충분히 활용할 수 없었기 때문이었다. 그래서 이코테 책을 보다가 알게 된 점화식은 내 기존 생각에 한 가지를 덧붙인 것이었는데, i번째 원소를 사용한다는 제약조건을 추가하는 것이다. 그렇게 마지막 원소까지 반복문을 수행한 후 max값을 찾으면 LIS의 길이를 구할 수 있다. 점화식을 생각할 때 정보가 충분하지 않은 것 같다면 정답으로 이어질 수 있으면서 고려할 범위를 좁혀줄 수 있는 제약조건을 주라는 것이 내가 이 문제에서 얻은 팁이다. 풀이 n = int(..
-
[백준] 1932번 정수 삼각형 (by Python)Programming/Algorithm 2021. 2. 21. 18:32
문제 점화식을 찾는 것은 사실 무척 쉬웠지만 인덱스를 헷갈려 시간을 낭비했다. 언제나 느끼지만 문제를 잘 푸는 것은 논리력뿐만 아니라 실수를 하지 않는 것도 포함되는 것 같다. 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [] dp = [[0] * (i + 1) for i in range(n)] for _ in range(n): arr.append(list(map(int, input().strip().split()))) dp[0][0] = arr[0][0] for i in range(1, n): for j in range(i + 1): if j == 0: dp[i][j] = dp[i - 1][0] + arr[i][j] elif j ==..