여러가지 블로그

문제링크 괄호가 들어감으로써 답이 달라지는 경우는 어떨 떄일까? 괄호를 넣지 않았을경우 55-50+40=45 괄호를 넣었을경우 55-(50+45)=-35 즉 -가 오고 그후에 +가 오면 무조건 괄호로 묶는게 이득이다 따라서 묶는 조건은 -후에 +가 왔을때 그후에 +가 올경우 괄호를 확장할수있다 1-(2+3+4) -가 올경우 괄호를 닫는다 1-(2+3)-4 연산중에 -가 한번이라도 나오면 그뒤에는 어떤 연산부호든지 관계없이 모두 뺄셈으로 계산된다는것을 발견했다 예를들어 1-2+3-4+5-6+7-8+9 라는 수식이 있다고 해보자 괄호로 묶으면 1-(2+3)-(4+5)-(6+7)-(8+9)가 된다 이부분은 노트에 몇번 끄적여보면 누구나 납득하게 될것이다 하지만 이렇게 간단하게 풀수있다고? 일단 구현해보았다 e..

프로그래밍/백준풀이 2022. 8. 20. 19:14

문제 예제로 입력 5 3 1 2 3 1 2 출력 7 이주어졌다 첫번째 아이디어 수가 주어졌을때 그수로 만들수있는 모든 조합을 구한다 (구간을 구하는것이니 요소숫자는 2이다) 그조합의 합이 만약 M으로 나누어 떨어진다면 ans의 개수를 하나 올린다 첫번째 아이디어에 누적합기능을 추가하면 구간합을 구할때 더 빠르게 할수있다 이것을 구현해보자 조합을 이용해서 구간의 넓이가 2이상인 모든 구간의 경우를 계산하고 구간의 길이가 1인경우에는 또 따로 조사를 해서 나눠떨어질경우 더했다 구현후 제출 from itertools import combinations N, M=map(int, input().split()) la=list(map(int, input().split())) print(la) # 누적합 리스트 만들기..

프로그래밍/백준풀이 2022. 8. 9. 16:20

문장이 주어지고 주어진 범위내에 특정한 글자가 몇개있는지 알아보는 문제이다 문제마다 사용글자가 주어지는것에대해 의아하게 생각했는데 왜냐면 모든문제에서 물어보는 글자가 같았기때문이다 그래서 나는 같은 글자만 나올수있는줄알았다 아래는 내가 첫번째로 제출한 코드이다 # import sys # input=sys.stdin.readline string=input() q=int(input()) # 어떤 알파벳인지 알아야함 alpha=input().split() alphabet=alpha[0] # 누적합 계산 시작 sumed_num=[0] alpha_num=0 for i in string: if i==alphabet: alpha_num+=1 sumed_num.append(alpha_num) else: sumed_nu..

프로그래밍/백준풀이 2022. 8. 7. 18:35

한문제만 더풀면 백준 골드티어 달성이기에 안쉬고 계속 문제풀이를 달려보도록한다 문제를 보자마자 든 생각은 이게 실버..3? 브론즈 문제 수준 아닌가 곧바로 구현하고 제출해보았다 import sys input=sys.stdin.readline N,M=map(int,input().split()) # N숫자의 길이, M문제의 개수 num=list(map(int,input().split())) # 숫자 for i in range(M): a,b=map(int,input().split()) print(sum(num[a-1:b])) 시간초과가 떳다 혹시몰라 파이파이3으로도 제출해보았는데 똑같이 시간초과가 났다 단계별로 풀어보기에 있는 도움말을 보면 누적합 테크닉을 사용한다고한다 저장해놓고 가져다 써서 시간을 아끼는것..

프로그래밍/백준풀이 2022. 8. 4. 04:05

먼저 바이토닉수열이란게 뭘까? 난 봉우리(꼭대기)를 가지고 있는 수열로 이해했다 4 3 2 1: 4가 꼭대기이다 1 2 3 4 5 4 3 2 1: 5가꼭대기이다 5 4 3 2 1: 5가 꼭대기이다 즉 꼭대기를 중심으로 증가수열과 감소수열이 완성된다 꼭대기는 배열의 양끝에도 올수있으며 이때는 단순한 증가수열 또는 감소수열이 된다 접근방식은 어떤곳에서 바이토닉 수열을 만들던 항상 꼭대기는 존재하기때문에 배열의 어떤 부분이 꼭대기가 되었을때 가장 긴 바이토닉 수열이 완성되는가에 있다 그리고 배열의 어떤한부분을 꼭대기로 가질때의 바이토닉함수의 길이는 어떤한부분의 인덱스를 3이라고했을때 3까지의 최대 증가수열길이 + 3부터 시작하는 최대감소수열길이 -1이다 이걸 구현해보면 # 끝나는 지점에서의 증가함수 N=int..

프로그래밍/백준풀이 2022. 7. 31. 23:26

링크 문제 이해하기 문제를 보자마자 저번에 풀었던 그 계단 건너기 문제가 떠올랐다 하지만 계단문제와다르다 계단문제는 모든 숫자를 다 건너가야하고, 맨끝 계단을 반드시 밟아야했다 이문제는 최대값이 되게 숫자를 집으라는것뿐 모든 숫자를 집으라는 말은 없었다 뭐 어차피 최대값을 나오게 하려면 대부분의 경우 모든 숫자를 다 집어야겠지만 그게 차이점이다 배열된 숫자들이 있고 거기서 고른 숫자가 최댓값이 되게 고른다 단. 연속으로 3숫자를 선택할수없다는 조건이 있다 입력 첫째줄에 포도주 잔의 개수 n이 주어짐 1 ≤ n ≤ 10,000 둘째줄부터 n+1줄까지 포도주잔안에 들어있는 포도주의 양이 순서대로 주어짐 포도주의 양은 음이 아닌 정수 출력 첫째줄에 최대로 마실수있는 포도주의 양을 출력 첫번째 아이디어 입력으로..

프로그래밍/백준풀이 2022. 7. 24. 22:27

금요일부터 풀기시작한 문제를 방금 끝냈다 이번 포스팅에서부터는 그냥 풀이과정이란말을 나의 풀이과정으로 바꿀생각이다 솔직히 검색하시는분은 아마 정답을 보고싶어서 검색하실텐데 그냥 풀이과정이라고 써놓으면 오해를 살것같아서 말이다 n-queen과 정말 유사한 문제라 빨리풀거라고 생각했는데 생각보다 오래걸린것같다 역시 난 똑똑한 편은 아닌걸로... n-queen에서 시간초과가 났던 그방법 그대로를 재현해서 도전하였다 ㅋㅋ 이번엔 다르겠지 이생각이었었던것같다 a=list(map(int,input().strip().split())) board=[ a[i*9:(i+1)*9] for i in range(9)] printed=0 x=set([1,2,3,4,5,6,7,8,9]) # import numpy as np imp..

프로그래밍/백준풀이 2022. 6. 26. 02:19

현재 머신러닝 프로젝트가 한창이다 대강의 모델링은 끝났고 최고의 결과물을 향해 개선중이다 프로젝트가 진행될수록 뭐랄까 점점 자신감이 붙는기분이다 어려움을 만나고 어떻게든 극복해나가면서 작은 성공을 여러번 반복해왔기때문이다 개발자의 삶은 수많은 실패와 수많은 성공의 반복 끊임없는 도전인것같다 다만 하나 수정할때마다 코드를 다시 실행하다보면 제대로 제보진 않았지만 3~5분정도가 걸린다 가장 빠른 모델을 사용해서 이정도지 이상한거쓰면 메모리다쓰고 다운되거나(대부분의 경우) 프로그램이 팅기거나 30분정도 걸린다 애초에 행수가 많긴하다 400만개정도 된다 현재는 캐글리더보드 기준 상위 10퍼센트를 목표로 하고있다 그래서 이번에 머신러닝중간에 기다리는시간이 좀 아까워서 백준을 풀었는데 쉽게 풀리지않았고 잠깐 짬내서..

프로그래밍/백준풀이 2022. 6. 12. 00:15