흙금이네 블로그

아이디어 DFS로 주어진 연산자로 가능한 식을 만들어 그 최댓값과 최솟값을 찾는다. 풀이 #1 (Python) 덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 람다식들을 리스트 cal에 저장한다. 리스트 operator에 각 연산자의 개수를 저장하고, 최댓값과 최솟값을 저장하는 리스트 res를 생성한다. 함수 dfs에서는 재귀 호출로 주어진 연산자를 사용하여 식을 만들고, 식을 모두 만들면 결과값과 비교하여 갱신해 나간다. cal = [lambda a, b: a+b, lambda a, b: a-b, lambda a, b: a*b, lambda a, b: a//b if a > 0 else -(-a//b)] def dfs(idx, total, a, s, m, d): global res if idx >= N: if t..

아이디어 동적 계획법으로 암호를 구성하는 숫자들이 직전의 숫자와 붙을 수 있는지 여부를 확인하여 가짓수를 구한다. 풀이 10과 20을 제외하고 0으로 시작하거나 30처럼 0이 포함된 암호는 해석할 수 없으므로 0을 출력한다. elif문에서 0이 아니면서 N의 길이가 1인 암호는 1을 출력한다. 그 외의 경우는 1로 채워진 N+1 길이의 리스트 dp를 생성하고, for문에서 암호를 구성하는 숫자들을 차례로 확인한다. 만약 현재 숫자가 0인 경우 직전 숫자와 붙여야 하므로 앞의 숫자 이전의 경우로 되돌린다. 직전 숫자가 0이 아니면서 현재 숫자를 직전 숫자와 붙일 수 있으면 직전 숫자까지의 가짓수와 그 이전 가짓수를 더한다. 그 외에 직전 숫자와 붙일 수 없는 경우는 직전 숫자까지의 가짓수로 저장한다. co..

아이디어 DFS로 가능한 순열 순서를 탐색하되, 백트래킹으로 중간에 500 미만이 되는 순서는 더 탐색하지 않는다. 풀이 #1 (Python) 운동 키트 중량 증가량을 리스트 A에 저장하고, 방문 표시를 위해 리스트 visited를 생성한 후 함수 dfs를 호출한다. 함수 dfs에서는 사용하지 않은 운동 키트들에 대해 visited에 표시한 후, 재귀 호출로 중량 total을 갱신하며 탐색해 나간다. 중간에 중량이 500 미만이 되면 현재 탐색을 종료하고 되돌아가고, 운동 일수 day가 N이 되면 결과값 res를 1 증가시킨다. def dfs(day, total): global res if total = N: res += 1 return for i in range(..

얼마 전 원티드에서 주관하는 코딩테스트 대회 2022 쇼미더코드 3회차에 참가했습니다. 지난 2022년 1회차에 참가했을 땐 3문제 중 2문제를 풀었습니다. 결과와 상관없이 보내주는 테스트 결과 메일을 기다리다가 아무런 메일도 못 받아서 한동안 원티드를 안 썼는데, 이번에 다시 메일을 확인해보니 G메일 프로모션 탭에 2022년 4월 12일자로 1회차 결과 메일이 와 있었습니다. 지난 1회차에서는 은손 뱃지를 받았었네요. 근데 9개월이나 지난 시점에 메일을 확인해서 뱃지는 활용도 못해보고 사라졌습니다. 그래도 이번 3회차에서는 간당간당하긴 했지만 3문제 중 3문제를 모두 풀었습니다. 대회는 BOJ에서 진행되었고, 누적합, BFS, DP의 세 문제가 출제되었습니다. 지난 2022년 1회차에서도 마지막 DP ..

아이디어 1149번 RGB거리와 유사한 문제로, 동적 계획법으로 각 칸에서 가능한 최댓값과 최솟값을 갱신해 나간다. 풀이 min_dp와 max_dp에는 각각 현재 줄에서 각 칸의 가능한 누적 점수 최솟값과 최댓값을 저장하고, min_prev와 max_prev는 각각 이전 줄까지 각 칸의 누적 점수 최솟값과 최댓값을 저장한다. 차례로 숫자 세 개를 a, b, c에 입력 받고, 이전 줄에서 내려올 수 있는 누적 점수와 더해 min_dp와 max_dp를 갱신한다. min_dp와 max_dp 갱신 이후 min_prev와 max_prev에 각각 현재 min_dp와 max_dp을 저장하고 다음 for문을 진행한다. import sys input = sys.stdin.readline def solution(): N ..

아이디어 버블 소트는 1회전마다 바로 뒤의 수보다 큰 앞의 수가 한 칸씩 뒤로 이동하며 정렬된다. 따라서 정렬 후 수들이 뒤로 이동한 거리의 최댓값을 구한다. 풀이 딕셔너리 A에 순서를 키로, 수를 값으로 저장하고, 수가 작은 순으로 그 순서를 정렬한다. for문에서 정렬 전의 순서에서 정렬 후의 순서를 뺀 값의 최댓값을 res에 저장한 후, 1 증가시킨 res를 출력한다. import sys input = sys.stdin.readline def solution(): N = int(input()) A = dict() for i in range(N): A[i] = int(input()) A = sorted(A, key=lambda i: A[i]) res = 0 for i in range(N): res =..

아이디어 플로이드-워셜 알고리즘으로 모든 건물 간 거리를 구한 후, 왕복 시간을 최소로 하는 두 건물의 조합을 찾는다. 풀이 #1 (Python) 건물 개수 N은 100 이하이므로 모든 건물 간 거리를 저장하는 2차원 리스트 D를 생성하여 100으로 채운다. 같은 건물 간 거리는 0으로 저장하고, 입력 받은 도로 정보를 D에 반영한다. 플로이드-워셜로 건물 i에서 j로 가는 시간을 건물 k를 경유하여 가는 시간과 비교해 최솟값으로 갱신해 나간다. 양방향 도로이므로 건물 j에서 건물 i에서 가는 시간도 같은 값으로 저장하며, j는 i보다 큰 번호부터 시작하도록 한다. 모든 건물 간 거리를 구한 후, 이중 for문에서 건물 i와 j를 선택했을 때의 왕복 시간 합을 구해 결과값을 갱신한다. import sys..

아이디어 #1 동적 계획법으로 사용하는 동전의 최소 개수를 구한다. 풀이 #1 k+1로 초기화된 k+1 길이의 리스트를 dp를 생성한다. 차례로 입력 받은 동전의 가치 c가 k보다 크거나 중복되는 동전인 경우 continue로 건너뛰고, 아니면 dp[c]에 1을 저장한다. c보다 큰 가치 합들에서 각각 c를 뺀 가치 합의 사용 동전 최소 개수보다 1 큰 값과 비교해 dp의 최솟값을 갱신한다. 가치 합을 k로 만들 수 있으면 사용하는 동전의 최소 개수를 출력하고, 그렇지 않으면 -1을 출력한다. import sys input = sys.stdin.readline def solution(): n, k = map(int, input().split()) dp = [k+1]*(k+1) for _ in range(..

아이디어 동적 계획법으로 경우의 수를 더해 나간다. 풀이 가치 합을 인덱스로 하여 경우의 수를 저장하는 리스트 dp를 생성한다. k보다 큰 값은 고려할 필요가 없으므로 dp의 길이는 k+1로 하고, 인덱스 0의 값은 1, 나머지는 0으로 채운다. 인덱스 0의 값을 1로 채우는 이유는 이후 for문에서 동전 가치의 경우의 수를 증가시키기 위함이다. 차례로 입력 받은 동전의 가치 c로 c보다 더 작은 가치는 만들 수 없으므로 for문에서 가치 합을 c부터 시작한다. c 이상의 가치 합 j의 경우의 수 dp[j]에 j에서 c를 뺀 가치의 경우의 수 dp[j-c]를 더해 나간다. import sys input = sys.stdin.readline def solution(): n, k = map(int, inpu..

아이디어 표에서 조건에 맞게 칸을 이동하며 만들 수 있는 숫자들 중 가장 큰 완전 제곱수를 구한다. 풀이 #1 (Python) 표를 입력 받아 2차원 리스트 table에 저장하고, 만들 수 있는 숫자들을 저장하는 세트 numbers를 생성한다. 차례로 표의 i행 j열에 있는 숫자를 numbers에 추가하고, 행과 열의 공차 di, dj로 함수 make_number를 호출한다. 이때 행과 열의 공차가 모두 0이면 무한 루프에 빠지므로 둘 중 하나라도 0이 아닐 때 함수를 호출하도록 한다. 함수 make_numbers는 인덱스를 벗어나지 않는 범위에서 재귀 호출로 공차에 따라 칸을 이동하며 숫자를 이어 붙인다. 이어 붙인 숫자들을 numbers에 추가하며, 공차가 음수인 숫자들을 저장하기 위해 역순으로 이어..