1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 조합 풀이 from itertools import combinations N = int(input()) result = set() for i in range(1, 11): for com in combinations(range(0, 10), i): com = sorted(com, reverse=True) result.add(int(''.join(map(str, com)))) result = sorted(result) try: print(result[..

1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net R, C = map(int, input().split()) board = [list(map(int, input().split())) for r in range(R)] T = int(input()) def get_median(arr: list): arr.sort() return arr[4] moveC = C - 2 moveR = R - 2 result = [] for mr in range(moveR): for mc i..

1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 접근 이진법으로 접근해야 한다. 코드 입력받은 숫자 N을 bin() 메서드로 이진수로 변환하고 1의 개수를 구한다. 이 1의 개수가 해당 숫자 N 에서 만들 수 있는 물병의 갯수가 된다. 예를 들어 N 이 3이라면, 세 개의 물병에서 문제의 조건대로 만들 수 있는 물병의 개수는 2개가 된다. 그래서 while bin(N).count('1') > K: 이라는 조건식을 만들 수 있다. 우리가 만들고자 하는 물병의 개수는 K 를 넘지 않아야 하니까. # 1. 일일이 다 더..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이 deque 을 이용해 풀었다. 다른 분들은 투포인터 등의 방법을 사용했던데 나는 deque 이 가장 직관적이라 느껴졌다. 우선 가장 단순하게 접근하면 리스트 슬라이싱을 먼저 떠올릴 수 있다. 하지만 입력의 최대 크기가 십만이기 때문에 당연히 시간초과 문제가 터진다. 이정도면 b급 영화의 뻔한 시놉시스보다 더 뻔한 전개가 아닐 수 없다. 클리셰를 극복하기 위해 나는 deque 를 ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 접근 처음엔 queue 를 사용해 bfs 로 접근했지만, 이 문제는 dfs 로만 풀 수 있다. 파란색은 BFS 접근을 나타내고, 분홍색은 DFS 식의 접근을 나타낸다. 문제에서 구하고자 하는 것은 최대한 얼마만큼 뻗어나갈 수 있는지를 구하는 것이기에, 분홍색의 DFS 식으로 접근해야 답을 구할 수 있다. 코드 r, c = map(int, input().split()) maps = [] fo..

https://www.acmicpc.net/problem/1213

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 핵심 이 문제를 쉽게 풀 수 있는 핵심은 deque() 자료형의 rotate() 메서드다. rotate(n)는 deque 의 내장함수로, n 이 양수면 우측으로, 음수면 좌측으로 회전한다고 볼 수 있다. 코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque(e..

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 처음 푼 코드 ( 메모리 초과 ) 시간 초과도 아니고 메모리 초과가 났다. 메모리 초과를 의심해 볼 부분은 배열이나 큐에 너무 많은 데이터가 들어가는 곳이다. 아래 코드에서는 덱(deque)에 데이터를 넣는 부분을 의심해 볼 만하다고 생각했다. import sys from collections import deque input = sys.stdin.readline t = int(inpu..

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 정답 코드 N = int(input()) array = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] board = [] if N == 1: print(9) exit() else: board.append(array) for n in range(1, N): temp = [] for j in range(10): if j == 0: temp.append((board[n - 1][1])) elif j == 9: temp.append((board[n - 1][8])) else: temp.append((board[n - 1][j - 1] + board[n - 1][j + 1]))..