→

문제link: https://www.acmicpc.net/problem/2805M미터의 나무를 얻기 위해 절단기에 설정할 높이의 최댓값을 구하는 문제이다. 접근요즘은 코드가 지저분해지더라도 일단 작성하고, 그 이후 최적화하는 식으로 백준 문제를 풀고 있다.처음에는 이 문제를 DP와 비슷한 방식으로 접근하려고 했는데, 그렇게 코드를 작성해 보니 너무나도 비효율적인 코드가 만들어졌다. (높이마다 잘리는 나무 개수를 리스트에 저장하도록 구현했다.) 코드를 돌려보지 않더라도 이 답안을 제출했다간 시간 초과가 뜰 것이라는 사실을 알 수 있었다. 그래서 이분 탐색으로 다시 접근했다. 코드N, M = map(int, input().split())trees = list(map(int, input().split()))s..

문제link: https://www.acmicpc.net/problem/15654N개 자연수 중 M개를 골라 나열하는 법을 모두 출력하는 문제이다. 접근백트래킹을 활용했다.수열을 구성하는 숫자가 같아도 순서가 다르면 다른 것으로 보기 때문에, 같은 숫자가 들어가지 않도록 유의해야 한다. 코드def bt(): if len(tmp) == m: print(' '.join(map(str, tmp))) return for i in nums: if i in tmp: continue tmp.append(i) bt() tmp.pop() tmp = []n, m = map(int, input().split..

문제link: https://www.acmicpc.net/problem/1541주어진 식에 임의로 괄호를 추가할 수 있다고 할 때 가능한 수식 계산값의 최소를를 출력하는 문제이다. 접근수식에 사용되는 것은 덧셈(+)과 뺄셈(-) 두 가지이다.빼는 값이 많아지도록 괄호를 치면 되므로 덧셈을 먼저 계산한 후 뺄셈을 계산하게끔 코드를 작성하면 문제를 해결할 수 있다.'-' 기호를 기준으로 숫자를 구분하여 문제를 푸는 방법이 더 효율적이겠지만, eval()을 사용하는 방법이 떠올라 이 방법을 사용해보았다. '-' 기호 앞뒤로 괄호를 추가하여 (수식...) - (수식...) 형태가 되도록 문자열을 조정한 후, eval() 함수로 결과값을 출력해주었다. 주의해야 할 점은 수식 내 숫자가 0으로 시작하는 경우가 있다..

문제link: https://www.acmicpc.net/problem/1260DFS와 BFS로 그래프를 탐색하는 문제이다. 접근DFS는 재귀 함수, BFS는 큐를 활용해 구현했다. 코드import sysfrom collections import dequeinput = sys.stdin.readlinedef dfs(graphs, visited, v, ans_d): ans_d.append(v) visited[v] = 1 for n in graphs[v]: if visited[n] == 0: dfs(graphs, visited, n, ans_d) def bfs(graphs, v, ans_b): q = deque([v]) visited = [0 ..

문제link: https://www.acmicpc.net/problem/1012배추밭에 필요한 배추흰지렁이 수 최솟값을 출력하는 문제이다. 접근배추흰지렁이가 인접한 배추로는 이동할 수 있으므로, 배추들이 몇 군데에 퍼져있는지를 확인하면 된다.DFS를 이용했다. set에 좌표값을 저장하여, 특정 땅의 좌표를 제거할 때 인접한 좌표도 함께 제거하는 식으로 몇 군데에 퍼져있는지를 세어 주었다.재귀 함수를 이용했기 때문에, 재귀 깊이 제한을 조정하는 코드를 추가했다. 코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10000)def search(x, y): if (x, y) not in s: return s.discard((x, ..

문제link: https://www.acmicpc.net/problem/17626입력받은 자연수를 최소 개수의 자연수 합으로 표현하는 문제이다. 접근처음에는 다소 비효율적으로 코드를 작성했는데, 시간 초과가 발생했다.더보기N = [4] * 50001S1 = []for i in range(1, 224): S1.append(i**2) N[i**2] = 1 for j in S1: for jj in S1: if j+jj >= 50001: break if N[j+jj] == 4: N[j+jj] = 2 for k in S1: for kk in S1: if k+kk >= 50001: ..

문제link: https://www.acmicpc.net/problem/117271x2, 2x1, 2x2 크기 타일을 활용해 2xn 사이즈 직사각형을 채우는 경우의 수를 구해 10007로 나누었을 때의 나머지 값을 출력하는 문제이다. 접근백준 11726번 2xn 타일링 문제와 같은 방식으로 접근하면 된다. (https://going-on.tistory.com/46) [백준] 11726 | 2xn 타일링 [파이썬/python]문제link: https://www.acmicpc.net/problem/117262xn 크기 직사각형을 1x2, 2x1 크기 타일로 채우는 경우의 수를 구해 10007로 나누었을 때의 나머지를 출력하는 문제이다. 접근%10007을 출력해야 한다는 사실을going-on.tistory.c..

문제link: https://www.acmicpc.net/problem/117262xn 크기 직사각형을 1x2, 2x1 크기 타일로 채우는 경우의 수를 구해 10007로 나누었을 때의 나머지를 출력하는 문제이다. 접근%10007을 출력해야 한다는 사실을 꼭 유념해야 한다!(중요해서 위에 씀) 전에 푼 백준 9095번 문제와 비슷하다고 느꼈다. (https://going-on.tistory.com/43) 동일하게 이전 항의 값을 이용해 n일 때의 값을 구할 수 있다. [백준] 9095 | 1, 2, 3 더하기 [파이썬/python]문제link: https://www.acmicpc.net/problem/9095주어진 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 접근방법을 구할 때, ..

문제link: https://www.acmicpc.net/problem/9461문제에서 제시한 그림과 같이 정삼각형이 추가될 때, n번째 정삼각형 변의 길이 P(n)을 찾는 문제이다. 접근문제에서 삼각형은 나선에서 가장 긴 변에 추가된다.P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9인데, 여기에서 P(n) = P(n-2)+P(n-3)인 것을 알 수 있다.리스트에 미리 값을 저장한 후 알맞게 출력해주었다. 코드import sysinput = sys.stdin.readlineP = [0, 1, 1, 1] + [0] * 97for i in range(4, 101): P[i] = P[i-3] + P[i-2] for _ in range(int(input..

문제link: https://www.acmicpc.net/problem/9375해빈이가 가진 의상 목록을 입력받아 가능한 옷 조합의 가짓수를 출력하는 문제이다.같은 종류의 의상은 동시에 착용할 수 없고, 의상은 한 종류 이상만 착용하면(알몸이 아니기만 하면) 상관없다. 접근의상 종류별로 개수를 카운트한 후 곱해서 가능한 경우의 수를 계산했다. 이때, 해당 종류의 옷을 입지 않는 경우도 고려 가능하도록 종류별로 개수를 셀 때 +1 해주었다. 아무 옷도 입지 않은 경우는 제외해야 하므로 모두 곱한 값에서 1을 빼 출력하도록 했다. 코드import sysinput = sys.stdin.readlinefor _ in range(int(input())): clothes = dict() for __ in..