📌문제 출처 솔브닷 3++ 클래스 단계 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 설정하는 높이가 h이고 나무의 높이가 tree일때 상근이가 가져가는 나무 길이 l l = tree - h if tree > h else 0 h를 0에서 max(trees)까지 이분 탐색하며 전체 나무 길이가 m 이상인 지점을 찾자 똑같은 높이의 나무에 대해서는 여러번 연산해줄 필요없이 개수..
📌문제 출처 솔브닷 3++ 클래스 단계 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' dp[i][j] = i번째 계단에 [한 칸 만 올라온 경우, 두 칸 올라온 경우] 마지막 계단에서 얻을 수 있는 점수 중 최대값을 반환하자 dp[i][0] = 계단을 한 칸 만 올라와서 얻는 점수 = i-1번째 계단에 두 칸 올라온 경우 + 이번 계단 점수 = dp[i-1][1]+steps[i] dp[i][1] = 계단을 두 칸 올라와서 얻..
📌문제 출처 솔브닷 3++ 클래스 단계 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ❓ 문제 📗 풀이 코드 from collections import defaultdict, deque input = open(0).readline def bacon(x) : # x에서 출발해서 각 노드에 도착하는 최단 경로 bfs tmp_dic = {i:-1 for i in range(1,n+1)} # 노드 방문..
📌문제 출처 솔브닷 3++ 클래스 단계 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 고장난 버튼을 제외한 나머지 버튼을 통해 최대한 가까운 채널을 만들어야한다. 0번부터 1,000,000까지 모든 채널을 확인하며 그것이 최대한 가까운 채널인지를 확인해야한다. 0에서부터 채널을 올리는 것이 최대 500,000번이므로 내리는 것 또한 1,000,000번부터 확인한다. 버튼을 누르지 않고 채널 변경..
📌문제 출처 솔브닷 3++ 클래스 단계 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net ❓ 문제 📗 풀이 코드 input = open(0).readline def solution(n,xs): # 해당 좌표보다 값이 작은 중복되지 않는 원소의 개수를 뽑아야한다. # 중복을 제거한 좌표 배열을 오름차순한다면 좌표의 인덱스가 압축 결과가 될 것이다. # 좌표의 원래 순서대로 출력되어야하므로 좌표:인..
📌문제 출처 백준 단계별 문제풀이 - 스택 2 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 from collections import Counter input = open(0).readline def solution(n,nums): # key point : 시간복잡도를 줄이기위해 반복을 줄여야한다. # 한 인덱스를 확인할 때마다 더 큰 등장횟수를 찾기 위해 뒤의 인덱스들을 매번 확인하는 것은 비효율적 # for 문을 한번만 돌면서..
📌문제 출처 백준 단계별 문제풀이 - 스택 2 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net ❓ 문제 ❗ 풀이 stack 활용 📗 풀이 코드 import sys input = sys.stdin.readline s, ex = input().rstrip(), input().rstrip() stack = [] lx = len(ex) for i in s : stack.append(i) if ''.join(stack[-lx:]) == e..
📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ❓ 문제 ❗ 풀이 stack, bfs 활용 📗 풀이 코드 import sys from collections import defaultdict,deque input = sys.stdin.readline def is_bps(n): # node n이 포함된 그래프의 이분 그래프 여부 확인 set_no = 1 # 노드 n이 포함될 집합, 계속 변경될 값..
