미식가의 개발 일기

문제 읽을 수 있는 단어 개수가 최대가 되는 K개의 글자 찾기 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정 - N - K - 단어: 영어 소문자, 8 해결 방법모든 단어에는 앞, 뒤로 무조건 와야하는 문자가 있으므로 'antic'은 무조건 K개의 글자에 포함되어야 한다. 따라서 K의 값이 5보다 작다면 정답은 0이고, 알파벳은 총 26글자 이므로 K의 값이 26이라면 정답은 N이다.itertools의 combinations를 사용하여 K-5개로 이뤄진 단어의 조합들을 탐색하며 읽을 수 있는 단어의 최댓값을 업데이트 해주면 된다.단, 여기서 중요한 최적화 포인트는 비트 마스크 연산이다.(처음에는 집합을 이용해 포함 여부를 판별했지만, 시간 초과가 ..

문제 올바른 괄호열이란 '()'나 '([[]])'처럼 괄호가 짝을 맞춰 올바르게 배치된 문자열을 의미한다.괄호의 값 계산 조건- ‘()’ 인 괄호열의 값은 2- ‘[]’ 인 괄호열의 값은 3이다.- ‘(X)’ 의 괄호값은 2×값(X) - ‘[X]’ 의 괄호값은 3×값(X) - 값(XY)= 값(X)+값(Y) - 올바르지 않은 괄호열이면 0 출력 해결 방법열린 괄호는 스택에 넣어주고 닫힌 괄호는 스택에서 빼준다. 단, 스택이 비어있거나 스택에 마지막으로 들어온 값에 대응되는 괄호가 없다면 0을 answer로 지정한다.괄호 안 괄호에 대해서는 값이 "("이라면 2, "["라면 3을 tmp에 계속해서 곱해주고, ")", "]"로 바로 직전에 짝이 있다면 answer에 현재까지의 tmp 값을 더해준다. 그 ..

문제 N개의 수로 이루어진 수열 A1, A2, ..., AN과 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로 이루어진 연산자 N-1개를 조합하여 만들 수 있는 식 중 결과가 최대인 것과 최소인 것 출력하기(단, 연산자 우선순위는 무시하고 앞에서부터 계산) 나눗셈은 정수 나눗셈으로 몫만 취하고, 음수를 양수를 나눌 때는 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꾼다.  해결 방법 1. 순열로 풀이: permutation을 사용해 연산자의 모든 순열을 구하고 계산한 뒤 최대값, 최소값 출력 → 많은 시간 소요2. 백트래킹으로 풀이: 재귀로 계속해서 타고 들어가며 모든 연산을 수행하고, 연산이 끝난 식은 현재까지의 최대값, 최소값과 비교해서 업데이트 → 시간, 공간 효율 더 좋음 나눗셈 연산은 i..

문제 예를 들어 N이 5라면 1부터 5까지 이어붙인 수는 `12345` 이므로 5자릿수가 된다.  입력 N(1 ≤ N ≤ 100,000,000)5 출력새로운 수의 자릿수 5 정답import sysinput = sys.stdin.readlineN = int(input())cnt = 0tmp = len(str(N)) for i in range(1, tmp): cnt += 9 * 10 ** (i-1) * icnt += (N - 10 ** (tmp - 1) + 1) * tmp print(cnt) 해결 아이디어간단하게 for문을 사용해서 모든 숫자를 풀어낸 후 길이를 반환하는 방식을 먼저 떠올렸지만 N의 범위가 `1 ≤ N ≤ 100,000,000` 이므로 당연히 시간 초ㅈ과가 날 것이라고 생각했고, ..

문제 x, y가 각각 M, N보다 작다면 전날 + 1, 작지 않으면 1은 달력의 마지막 해이고, 가 몇 번째 해인지 구하는 문제 M, N  1일2일3일4일5일6일7일8일9일10일11일x123456789101y1234567891011→ 10일을 보면 x는 M과 같은 값으로 M보다 작아야 한다는 조건을 만족하지 못하므로 11일에 1로 초기화 해준다. 입력1. 테스트 데이터의 개수 T2. T개의 M, N, x, y (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)  310 12 3 910 12 7 213 11 5 6 출력 가 몇 번째 해인지(유효하지 않으면 -1 출력) 33-183  정답import sysinput = sys.stdin.readlinedef cal_year(M, N, ..

문제 리모컨 0~9 숫자, +, -현재 채널 100, 채널 N까지 이동하기 위해 버튼(+, -)을 최소 몇 번 눌러야 할까?단, 0에서 - 버튼을 누르면 동작 X, 채널은 무한대 만큼 있음 입력1. 채널 N (0 ≤ N ≤ 500,000) 2. 고장난 버튼의 개수 M (0 ≤ M ≤ 10) 3. 고장난 버튼545736 7 8 출력 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지6  정답import sysinput = sys.stdin.readlinedef remote_controller(N, M, buttons): min_cnt = abs(100 - N) if N == 100: return 0 for i in range(1000001): fo..

문제 N x N 크기의 보드에 4가지 색의 사탕이 채워져 있음인접한 서로 다른 두 사탕을 교환 후 모두 같은 색으로 이루어진 가장 긴 부분(행 또는 열)을 먹음먹을 수 있는 사탕의 최대 개수는?  입력보드의 크기 N (3 ≤ N ≤ 50)보드에 채워진 사탕(빨강: C, 파랑: P, 초록: Z, 노랑: Y)3CCPCCPPPC 출력먹을 수 있는 사탕의 최대 개수3 정답import sysinput = sys.stdin.readlinefrom collections import Counter# 연속 행 또는 열의 최대 길이 반환 def check_cnt(n, target_list): global max_cnt for i in range(n): # 가로 방향 카운트 cnt..

가중치 그래프에서 단일 출발점의 최단 경로를 구하는 문제  조건출발점에서 각 노드까지의 최단 경로를 구할 때 사용음수 가중치를 포함하면 안됨 → 벨만-포드 알고리즘 사용  동작 과정# 그래프 예시 A --(5)-- B --(1)-- C | / | | (2) (2) (5) (1) | / \ | D --(3)-- E --(3)-- F  1. 초기화: 시작 노드의 거리는 0, 나머지 노드는 ∞로 초기화노드ABCDEF거리0∞∞∞∞∞  2. 노드 선택: 방문하지 않은 노드 중 최소 거리를 가지는 노드 선택  → `heapq.heappop`노드ABCDEF거리05∞2∞∞ → D, A → B 거리 갱신>   3. 거리 갱신: 선택된 노드의..