생각하는 아져씨

2805번: 나무 자르기https://www.acmicpc.net/problem/2805 문제 정의상근이는 M미터의 나무가 필요해서 나무를 벌목하려고 한다. 절단기의 높이를 설정하면, 높이만큼 나무를 잘라주는데, 나무들의 높이가 주어졌을 때 적어도 M미터의 나무를 가져가려면 절단기의 높이를 최대 몇까지 설정할 수 있을까? 접근 방법나이브한 접근방법나무리스트 [20, 15, 10, 17] 가 주어졌을 때, 절단기의 높이를 1~최대 나무 높이(=20)까지 설정해보면서, (나무-절단기높이)의 합이 M미터 이상인지 확인하면 된다.즉, sum(각 나무높이 - 절단기 높이) ≥ M (적어도 M 미터이므로, M이상과 비교하면 된다.)하지만, N은 최대 2,000,000,000 이므로, 이중 for문을 사용하면 시간 ..

10816번: 숫자 카드 2https://www.acmicpc.net/problem/10816 문제 정의상근이는 숫자 카드 N개를 가지고 있다. 정수가 M개 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하면 된다. 만약 상근이가 6 3 2 10 10 10 -10 -10 7 3 카드를 가지고 있을 때,10 9 -5 2 3 4 5 -10 → 이 숫자들을 몇개 씩 가지고 있는지 출력하면 된다.이 예에서는 10은 3개 가지고 있으므로 3으로 출력하면 된다. 접근 방법N과 M이 최대 500,000이 될 수 있는데, 일일히 2개의 리스트를 비교하기에는 O(N2)O(N^2)O(N2) 으로 시간 초과가 뜰 수 있다.그래서 x가 리스트 안에 몇 개 있는지 찾기 위해서 기준 숫자인 mid..

1018번: 체스판 다시 칠하기https://www.acmicpc.net/problem/1018 문제 정의M*N 크기의 보드에서 8*8 크기의 체스판을 만들려고 한다.체스판은 검은색/ 흰색이 번갈아 칠해져있어야 하는데, 보드는 그렇지 않다.보드를 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해서 체스판을 만들 때, 칠해야 하는 최소 정사각형 개수를 구하면 된다. 접근 방법N과 M의 범위가 50보다 작거나 같다고 해서 모든 원소는 최대 2500개이고, 그 중에서도 8*8 크기의 체스판이면 64개로 4중 for문을 돌아도 시간 초과는 나지 않는다.따라서 완전 탐색으로 접근했다. 시작점이 되는 원소를 기준으로 8*8 크기의 체스판을 만들고, 그 체스판 원소 중 색칠을 다시 해야 하는 부분을..

https://school.programmers.co.kr/learn/courses/30/lessons/42839문제 정의문자열로 주어진 종이조각으로 만들 수 있는 소수가 몇 개인지 계산해야한다. 접근 방법문자열로 주어진 종이조각을 분리한 후 조합을 이용해 만들 수 있는 모든 숫자를 만든다.그 다음에 그 숫자가 소수인지 판단하면 된다.이 때 쓸 수 있는 유용한 함수에는 itertools의 permutations이 있다.문제 해설permutations의 인자로 들어갈 리스트를 만들어 주기 위해서 numbers를 분리했다. (numbers는 문자열로, 공백이 없이 주어졌기에 split() 함수를 사용할 수 없었다. 따라서 for문으로 일일히 분리했다.)permutations을 사용해 모든 조합을 구하고 jo..

24444번: 알고리즘 수업 - 너비 우선 탐색 1https://www.acmicpc.net/problem/24444 문제 정의입력으로 주어지는 간선 정보로 BFS를 수행하고 각 노드의 방문 순서를 출력한다. 접근 방법BFS 탐색 문제 해설각 노드 정보를 이차원 리스트 정보로 받는다.무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.시작 노드인 R 부터 DFS를 수행한다. 풀이import sys from collections import deque input = sys.stdin.readline N, M, R = map(int, input().split()) graph = [[] for _ in range(N+1)] visited = [False] * (N+1) order = [0..

24479번: 알고리즘 수업 - 깊이 우선 탐색 1https://www.acmicpc.net/problem/24479문제 정의입력으로 주어지는 간선 정보로 DFS를 수행하고 각 노드의 방문 순서를 출력한다. 접근 방법DFS 알고리즘 활용 문제 해설각 노드 정보를 이차원 리스트 정보로 받는다.무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.시작 노드인 R 부터 DFS를 수행한다. 풀이import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N, M, R = map(int, input().split()) # 정점 개수, 간선 수, 시작 정점 graph = [[] for _ in range(N+1)] # 연결 그래프 vis..