[Python] BOJ 13422 도둑 t = int(input()) for i in range(t): # n 집의 개수 # m 연속된 집의 개수 # k 최소 돈의 양 (k를 넘으면 안됨) n, m, k = map(int, input().split()) lst = list(map(int, input().split())) if m != n: for i in range(m-1): lst.append(lst[i]) sum_lst = [0] total = 0 for i in lst: total += i sum_lst.append(total) start = 0 end = m count = 0 while end != len(sum_lst): if sum_lst[end] - sum_lst[start] < k: count += 1 start += 1 end..
[Python] 백준 1806 부분합 n, s = map(int, input().split()) lst = list(map(int, input().split())) # 1. 누적합을 구해놓는다 sum_lst = [0] total = 0 for l in lst: total += l sum_lst.append(total) # 누적합 배열이 0부터 시작하기 때문에 # start = 1, end = 2 부터 시작하기 # m은 n+1로 최대값으로 만들어 놓기 start = 1 end = 2 m = n + 1 # 만약 누적합 배열의 첫번째에 내가 찾고자하는 값이 있으면 -> 길이가 1인게 있다는 뜻! if sum_lst[1] == s: m = 1 # 그런게 없다면 else: # 투포인터로 계속 탐색하기 while end = s: m = min(m, e..
[Python] 백준 13414 수강신청 https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net n, k = map(int, input().split()) dic = dict() for i in range(k): num = input() dic[num] = i sorted_dic = {key : dic[key] for key in sorted(dic, key=lambda x: dic[x])} count = 0 for i in sorted_dic: if n == count: bre..
[Python] 백준 10825번 국영수 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 풀이 n = int(input()) list = [] for i in range(n): list.app..
[BOJ] 2003번 수들의 합2 - 구간합, 투포인터 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 방법 1 : 구간합 n, m = map(int, input().split()) list = list(map(int, input().split())) # 합배열 만들기 total = 0 sum_list = [0] for i in range(len(list)): total += list[i] sum_list.append(total) # 구가합을 빼면서 m이랑 ..
[Python] 백준 1260 DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 코드 from collections import deque import sys input = ..
[Python] 백준 2178 미로탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 코드 from collections import deque n, m = map(int, input().split()) board = [input() for _ in range(n)] # 101111, 101010, 101011, 111011 들어갈 것임 checkArray = [[False] * m for _ in range(n)] q = deque() q.append((0, 0, 1)) checkArray[0][0] = ..
[Python] 백준 1764 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 조건 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 듣보잡의 수와 그 명단을 사전순으로 출력한다. 어떤 자료구조를 택할까? 먼저 문제를 봤을 때, 듣도 못한 사람과 보지 못한 사람을 입력받고 → 듣도보도못한(듣보잡) 사람을 찾는 문제였다. 결국 듣보잡은 (듣도 못한 사람 + 보지 못한 사람) 두 조건을 모두 만족해야하는 사람이다. 그러면 각 리스트의 ..
[Python] 백준 1417 국회의원 선거 https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 문제 다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다. 다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다. 현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마..
[Python] 백준 13417 카드 문자열 https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net 문제 해설 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력해야함 처음 뽑은 카드를 기준으로 문자열을 비교하여 사전순이 빠른 문자는 왼쪽에, 그렇지 않으면 오른쪽에 붙임 즉, 왼쪽 오른쪽에 자유롭게 푸쉬를 할 수 있는 자료구조는 ? → Deque from sys import stdin from collections import deque t = int(stdin.read..
[Python] 백준 10799 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어..
[Python] 백준 1874 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해설 처음에 풀 때 문제 이해가 잘 안되었다.. 결국 어떤 분의 설명을 블로그에서 읽고 겨우 이해했는데 만약 처음으로 4를 입력했다면 내가 첫 번째로 pop한 숫자가 4가 되어야 하고, 그러기 위해서는 1,2,3,4가 이미 스택안에 있어야 한다. 그래서 입력한 수를 만날 때 까지는 계속 push를 해서 1,2,..
라이브러리 브랜드 그룹 | Hi

티스토리툴바