코딩테스트

[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] 백준 - 11729. 하노이 탑 이동 순서

🤔문제 해결 S2 | 재귀 하노이탑 - 1번에 위치한 원반을 고대로 3번으로 옮기는 것!! 재귀를 배울 때 단골 문제 💻소스 코드 def hanoi(n, start, end, sub): if n == 1: # print(f'{start}=>{end}') answer.append([start, end]) return hanoi(n - 1, start, sub, end) # print(f'{start}=>{end}') answer.append([start, end]) hanoi(n - 1, sub, end, start) N = int(input()) answer = [] hanoi(N, 1, 3, 2) # 출력 print(len(answer)) for i in answer: print(*i) 📕문제 확인 출..

[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] 백준 - 7562. 나이트의 이동

🤔문제 해결 S2 | BFS BFS로 다 돌아주다가 도착지를 만나면 끝! 💻소스 코드 from collections import deque def bfs(): q = deque() q.append((start_x, start_y)) while q: cx, cy = q.popleft() if cx == end_x and cy == end_y: print(chess[cx][cy]) return for k in range(len(dx)): nx = cx + dx[k] ny = cy + dy[k] if 0