알고리즘/백준 문제풀이

문제 https://www.acmicpc.net/problem/15666 문제 풀이 백트래킹 기본 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) LIST = sorted(list(set(map(int,input().split())))) total = [] def back(s): if len(total) == M: print(*total) return for i in range(s,len(LIST)): total.append(LIST[i]) back(i) total.pop() back(0)

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 풀이 이분탐색으로 찾을 값 : 블루레이의 길이 블루레이의 길이를 바꿔가며 그 길이로 나눴을 때 group의 수가 M개 초과면 블루레이 길이를 더 길게 M개 이하면 블루레이 길이를 더 작게 코드 import sys input = sys.stdin.readline import bisect N, M = map(int,input().split()) video_list = list(map(int,inp..

문제 https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 문제 풀이 가장 큰 섬을 찾는 bfs문제 응용 코드 import sys input = sys.stdin.readline import collections M, N = map(int,input().split()) MAP = [list(map(int,input().split())) for _ in range(M)] visited = [[0 for _ in range(N)] for _ in range(M)] def bfs(MAP, sx, sy): q = collections.deque() q.app..

문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 풀이 cost가 작은 순간이동을 우선으로 하여 bfs 돌림 코드 import sys input = sys.stdin.readline import collections N, K = map(int,input().split()) q = collections.deque() q.append((N,0)) visited = [0 for _ in range(100..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀이 문제에서 주어진 좌표가 일반적인 이차원배열 인덱스와 반대인 것만 잘 체크해주면 되는 bfs 문제 코드 import sys input = sys.stdin.readline import collections def fill_MAP(MAP, x,y,rx,ry): for i in range(M-ry, M-y): for j in range(x, rx): MAP[i][j]..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹 기본 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) LIST = list(range(1,N+1)) res = [] def back(s): if len(res) == M: print(*res) for i in range(s, N): res.append(LIST[i]) back(i+1) re..

문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹 기본 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) res = [] def back(): if len(res) == M: print(*res) for i in range(N): if i+1 not in res: res.append(i+1) back() res.pop() back()

문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 풀이 비가 올 수 있는 모든 경우에 대해서, 비(height) 높이를 초과하는 높이의 영역의 갯수 bfs로 찾기. 섬 갯수 찾기 bfs 문제와 유사함. 유니온 파인드로 푸는게 훨씬 효율적,, 나는 뇌가 bfs에 절여진듯,, 코드 import sys input = sys.stdin.readline import collections N = int(input().strip()) MAP = [list..