문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우를 구하는 문제이다. 문제를 풀기 위해 경우를 찾아보면 다음과 같은 규칙을 찾을 수 있다. N이 홀수인 경우 경우의 수는 0이다. 2x1, 1x2로는 N이 홀수인 경우 채울 수 없다. N = 2 3가지 경우의 수 N = 4 2의 경우의 수 * 3 + 2 N = 6 4의 경우의 수 * 3 + 2의 경우의 수 * 2 + 2 N = 8 6의 경우의 수 * 3 + 4의 경우의 수 * 2 + 2의 경우의 수 * 2 + 2 `dp[N] = dp[N - 2] * 3 + dp[N - 4] * 2 + ... dp..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 주어진 입력 값 N, M에 따라 간선 정보를 토대로 그래프를 초기화 해준 후 각 노드마다 연결된 노드들로 경로를 탐색하면 된다. 이때 백트랙킹이 필요하므로 `DFS`로 탐색을 진행하여 연결된 노드의 개수가 크면 갱신시켜주면 문제를 해결할 수 있다. 코드 from collections import defaultdict T = int(input()) def dfs(cur_node, cnt): global answer if answer < cnt: answer = cnt for next_node in graph[cur_node]: if not visit..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 `DFS`를 통한 백트래킹으로 NxN 크기의 체스판에서 Queen을 배치할 수 있는 경우의 수를 계산할 수 있다. 이는 앞서 다룬 백준: 9663 N-Queen과 동일한 로직으로 풀면 된다. N의 크기가 최대 10이기 때문에 백준의 문제와는 달리 Python으로도 충분히 통과할 수 있다. 다시 한번 로직을 상기해보자면 다음과 같다. 행의 경우 DFS를 호출하며 증가시키므로, 별도의 중복확인이 필요하지 않다. 열의 경우 해당 열을 선택하면 `set`에 추가하여 중복을 확인한다. 우측 상단에서 좌측 하단의 대각선의 경우 현재 `X + Y`를 `set`..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 농작물을 수확하여 얻을 수 있는 이익이 행열에 주어 질 때, 마름모로 탐색하여 이익의 합을 구하는 문제이다. 마름모로 접근하는 로직만 설계하면 끝나는 문제이다. 마름모를 접근하기 위해서는 다음과 같이 생각하면 된다. 예를 들어 3x3 행렬이라고 하면 다음과 같이 접근하게 된다. (0, 1) (1, 0), (1, 1), (1, 2) (2, 1) 이와 같이 접근하고자 할 때 `j`의 범위에 대한 규칙은 `abs(N // 2 - i)`부터 `abs(N - half)`이다. `half`는 i가 절반이 되기 전까지는 감소하고, 절반이 된 이후로는 증가하여 ..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 메모리가 초기화되어 모든 bit가 0이 된 상태에서 원래 상태로 돌아가기 위한 최소 변환 횟수를 구하는 문제이다. 메모리를 변경하는 데 있어 다음과 같은 규칙이 있다. 예를 들어 `000`을 변환하면 하나만 변환하여도 `111`로 변환되게 된다. 따라서 처음에 비교할 bit를 0으로 두고 0과 다르다면 비교 비트를 1로 바꾸는 식으로 스위치 하여 비교하면서 현재 비트와 비교할 bit가 다른 경우를 카운트하면 bit를 변경하는 횟수가 된다. 코드 T = int(input()) for test_case in range(1, T + 1): answer ..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 중복이 되는 경우 소거하여, 중복이 없을 때까지 반복하여 남는 문자를 비밀번호로 하는 문제이다. 문제를 풀기 위해서는 `stack`을 사용하면 쉽게 풀 수 있다. `stack`에 추가 되는 규칙은 `stack[-1] == 현재 숫자`와 같은 경우 `stack.pop()`을 하고 아닌 경우 `stack.append(현재 숫자)`를 하여 비밀번호 값을 stack에 유지한다. 프로그래머스: 올바른 괄호를 중복된 숫자가 대신한다고 생각하면 된다. 코드 for test_case in range(1, 11): stack = [] n, nums = input(..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 8개의 숫자가 주어질 때 1 - 5의 숫자를 반복하면서 숫자를 감소한 후에 마지막 숫자가 0이 될 때까지 반복하는 문제이다. 문제는 `deque`를 활용하면 쉽게 풀 수 있다. 반복문을 돌면서 감소시킬 수 있는 수(코드에서는 delta라고 하였다.)를 통해 맨 앞의 숫자를 감소시키고 맨 뒤로 보낸다. 이때 `list`의 `pop(0)`와 `append`를 사용하여도 되지만 `deque`를 사용하는 이유는 `pop(0)`의 경우 시간 복잡도가 O(N)이기 때문이다. 이 문제에서는 `list`와 `deque` 어느 것을 사용하여도 상관 없지만, `po..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 0 ~ 9의 숫자가 문자열 "ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"와 같이 주어질 때 문자열 순이 아닌 숫자 순으로 정렬 후에 출력하는 문제이다. 문제를 해결하기 위해서는 딕셔너리를 활용하면 쉽게 풀 수 있다. 코드 digit_to_string = { 0: "ZRO", 1: "ONE", 2: "TWO", 3: "THR", 4: "FOR", 5: "FIV", 6: "SIX", 7: "SVN", 8: "EGT", 9: "NIN" } string_to_digit = {va..
