Total

[2003] 수들의 합2 (투 포인터)

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 풀이 n,m = map(int, input().split()) a = list(map(int, input().split())) # 투 포인터 lt=0 rt=1 tot=a[0] cnt=0 while True: if tot

[11659] 구간합 구하기4 (합배열)

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 분석 합 배열 공식 : S[i] = S[i-1] + A[i], 구간합 공식 : S[j] - S[i-1] 세그먼트 트리 : 2023.03.23 - [Algorithm PS/Tree] - 세그먼트 트리, 인덱스 트리, 구간합 풀이 import sys input=sys.stdin.readline n,k = map(int, input().split()) list = list(map(int, input().split())) # 구간합 배열 sumLi..

정렬된 두 리스트 합치기 (sort 함수, 투 포인터)

문제 오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력 3 1 3 5 5 2 3 6 7 9 1 2 3 3 5 6 7 9 분석 sort()의 시간복잡도 : nlogn ➔ 정렬된 두 리스트 합치기 시간복잡도 : n 풀이 # 시간복잡도 n n=int(input()) a=list(map(int,input().split())) m=int(input()) b=list(map(int,input().split())) c=[] # 정답 리스트 p1=p2=0 while p1

카드 역배치 (파이썬 리스트 뒤집기)

문제 1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓여있다. 구간 [a, b] (단, 1 ≤ a ≤ b ≤ 20)가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다. 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [5, 10]으로 주어진다면, 위치 5부터 위치 10까지의 카드 5, 6, 7, 8, 9, 10을 역순으로 하여 10, 9, 8, 7, 6, 5로 놓는다. 오름차순으로 한 줄로 놓여있는 20장의 카드에 대해 10개의 구간이 주어지면, 주어진 구간의 순서대로 위의 규칙에 따라 순서를 뒤집는 작업을 연속해서 처리한 뒤 마지막 카드들의 배치 출력 5 10 9 13 1 2 3 4 5 6 1 2 3 4 5 6 1 20 1 20 1 2 3..

숫자만 출력

문제 문자와 숫자가 섞여있는 문자열(~50) 중 숫자만 추출하여 그 순서대로 만들어진 자연수와 그 자연수의 약수 개수 출력 만약 “t0e0a1c2h0er”에서 숫자만 추출하면 0, 0, 1, 2, 0이고 이것을 자연수를 만들면 120 120를 출력하고 다음 줄에 120 의 약수의 개수를 출력 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다. 풀이1 str=input() disStr="" for i in str: if i.isdecimal(): disStr+=i num=int(disStr) print(num) cnt=0 for i in range(1, num+1): if num%i==0: cnt+=1 print(cnt) 풀이2 str=input() res=0 for i in str: if..

[17609] 회문 (유사회문, 투 포인터)

17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 분석 회문 검사 : i번째 문자와 j번째 문자가 같은지 비교하며 i를 1씩 증가시키고 j를 1씩 감소시켜 가운데로 이동 while문을 이용하여 i가 j보다 작을 때까지 반복 반복문을 순회하면서 i와 j가 다른 문자가 있을 경우, 회문이 아니므로 유사회문 검사 유사회문 검사 : 유사회문은 1문자를 제외하고 회문인 경우므로, 다른 문자가 있을때 i를 한칸 건너 뛰고 검사하거나 j를 한칸 건너 뛰고 검사 했을 때 회문 따라서 secondCheck함수에 각각 인자를 i+1, j-1로 변경하여 검사 ..

[1253] 좋다 (좋은 수 구하기, 투 포인터)

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 분석 투 포인터 이동원칙 A[i] + A[j] > K : j--; A[i] + A[j] < K : i++; A[i] + A[j] == K : count++; 프로세스 종료 풀이 n = int(input()) list = list(map(int, input().split())) list.sort() cnt = 0 # 다른 두 수의 합인 수의 개수 for k in range(n): val = list[k] i = 0 j = n-1 while i < j: # 투 포인터 알고리즘 if list[i..

회문 문자열 검사

문제 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열)이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력 첫 줄에 정수 N(1

[1541] 잃어버린 괄호 (최솟값을 만드는 괄호 배치하기)

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 분석 가능한 큰 수를 빼야함 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행 풀이 """ +-괄호를 이용해 수식 생성 -> 다시 배치, 괄호 넣어서 최소값 100-40+50+74-30+29-45+43+11 """ prefix = input() arr = prefix.split("-") result = 0 for i in range(len(arr)): arr2 = list(map(int, arr[i].split("+"))) print(..

위상정렬(그래프 정렬)

분석 [1516번] 게임 개발하기 (위상정렬) 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. karla.tistory.com 풀이 """ 첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다. 두 번째 줄부터 M개의 정보가 주어집니다. 6 6 1 4 5 4 4 3 2 5 2 3 6 2 전체 일의 순서를 출력합니다. 1 6 2 5 4 3 """ import sys input=sys.stdin.readline from collections import deque # 일의개수, 순정보개수 n,m= map(int, input()...