백준

[python] 백준 - 2133. 타일 채우기

🤔문제 해결 S2 | DP 이런문제는 역시 단골 DP문제 일단 손으로 구해봤다. i == 0, 2, 4, 6 ( 홀수 일 경우는 제외함 ) 경우의수 == 1, 3, 11, 41 점화식 dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2 i경우의수 = 이전의 경우의 수 * 3 + 이전의 경우의 수 들 * 2 + i만 만드는 경우 💻소스 코드 N = int(input()) if N % 2: print(0) else: dp = [0] * (N + 1) dp[0], dp[2] = 1, 3 for i in range(4, N + 1, 2): dp[i] = dp[i - 2] * 3 + 2 for j in range(2, i - 2, 2): dp[i] += dp[j] * 2 prin..

[python] 백준 - 1182. 부분수열의 합

🤔문제 해결 S2 | 완전탐색(백트래킹) 문제를 잘 이해하지 못해서 많이 헷갈렸다. 그냥 쉽게 설명해서 주어진 숫자들 중 n개를 뽑아서 더한 값이 S와 같은 조합이 몇개인지 구하라는 말 파이썬에서는 쉽게 콤비네이션을 쓰면 된다. 문제 유형에 백트래킹이 있으므로 백트래킹을 연습하고 싶으면 백트래킹을 써도 좋다. 💻소스 코드 from itertools import combinations N, S = map(int, input().split()) numbers = list(map(int, input().split())) answer = 0 for i in range(1, N + 1): for combi in combinations(numbers, i): # print(combi) if sum(combi) ==..

[python] 백준 - 11055. 가장 큰 증가 부분 수열

🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신보다 작은 값의 인덱스를 찾는다. 해당 인덱스의 dp값중 가장 큰 값과 자신의 값을 더해 dp를 다시 채운다. dp에서 max값을 출력 💻소스 코드 N = int(input()) numbers = list(map(int, input().split())) dp = numbers[:] dp[0] = numbers[0] # print(f'최초DP: {dp}') for i in range(1, N): for j in range(i): if numbers[j] < numbers[i]: dp[i] = max(dp[i],..

[python] 백준 - 11722. 가장 긴 감소하는 부분 수열

🤔문제 해결 S2 | DP 참고(비슷한 유형) : deok2kim.tistory.com/173 [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com numbers에는 수열이 들어있다. dp라는 1차원 리스트를 만든다. (1초 초기화, 감소하는 부분 수열의 길이가 들어갈 것이다.) 1로 초기화한 이유는 혼자만 가능할 때는 길이가 1이므로 numbers를 하나씩 돌면서 자신보다 앞쪽의 숫자와 비교한다. 자신보다 앞쪽의 숫자가 클 경우 - 나와 그 숫자는 감소하는 부..

[python] 백준 - 1931. 회의실 배정

🤔문제 해결 S2 | 정렬, 그리디 회의 시간이 긴 것과 상관 없이 회의가 끝나는 시각이 빠른것을 선택 회의가 끝나는 시각이 빠른 순으로 정렬 이전 회의가 끝난 시각과 비교하여 회의를 시작할 수 있으면 카운트 +1 없으면 통과 💨 끝나는 시각 뿐만 아니라 시작 시간도 두번 째로 정렬 해줘야 한다. 반례 [2,2], [1,2] 💨 sys.stdin.readline 과 input의 차이 (아래가 input()으로 받은 것) 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(key=lambda x: (x[1], x..

[python] 백준 - 1011. Fly me to the Alpha Centauri

🤔문제 해결 S1 | 수학 DFS로 구현해보려고 했으나 역시 시간초과로 실패했다. 알고리즘이 수학이다보니 역시 손으로 직접 패턴을 구해야 한다. 패턴을 보면 다음과 같다. 노란색으로 칠한 곳을 보면 뭔가 알 수 있다. . . . . 거리의 제곱근은 홀수 횟수가 끝나는 지점. 4: 2*2-1 = 3 9: 3*2-1 = 5 16: 4*2-1 = 7 25: 5*2-1 = 9 그렇다면 제곱근이 아닌 숫자는 어떻게 찾을까? 파란색을 보자. . . . . 거리의 제곱근만큼 다음 숫자가 있다. EX 예를 들어 거리가 7이다. 제곱근은: 2.xxxx 이므로 2이다. 2를 제곱하면 4 우리는 4부터 보면된다. 그렇다며 나머지는 거리 7에서 4를 빼면된다. 카운트는 2*2-1 이므로 3 제곱근은2, 시작은4, 나머지는3,..