전체 글

브루트포스) 14888.연산자 끼워넣기

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net n=int(input()) nums=list(map(int,input().split())) ops = list(map(int,input().split())) max_ans=-1000000001 min_ans=10000000001 def dfs(index,s): global max_ans,min_ans # 종료 조건 if index==n: # ..

브루트포스) 14225.부분수열의 합

https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net n=int(input()) nums=list(map(int,input().split())) c=[False]*(n*100000+10) def go(index,s): if index==n: c[s] = True return go(index+1,s+nums[index]) go(index+1,s) go(0,0) ans=1 while T..

브루트포스) 1182.부분수열의 합

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net n,s = map(int,input().split()) nums=list(map(int,input().split())) answer=0 # solution 1 def dfs(index,arr,m): global answer # 정답을 찾은 경우 if len(arr) == m: if sum(arr) == s: answer+=1 return # 불가능한 경우 if ..

브루트포스) 6603. 로또

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net def recur(a,index,arr): # 종료 조건 # 정답을 찾은 경우 if len(arr) == 6: print(' '.join(map(str,arr))) return # 불가능한 경우 if index == len(a): return recur(a,index+1,arr+[a[index]]) recur(a,index+1,arr) while(1): data = list(map(in..

브루트포스) 2580. 스도쿠

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net # solution. # 빈 칸에 넣을 숫자를 판별하기 위해서는 해당 칸이 속한 행, 열, 3x3 크기의 정사각형 이 3개에 존재하는 숫자를 살펴야 한다. # 이 3개를 row, col, sqaure 배열로 설정하여, 각 숫자를 포함하고 있는지를 Boolean형으로 나타내게 한다. # 가령 row[i][j] = True 는 i번째 행은 j라는 숫자를 포함하고 있다는 뜻이다. # 작은 정사각형은 총..

[Python] 알고리즘 요구사항 분석 (시간 복잡도)

🦄 시간 복잡도 코딩테스트 문제의 시간제한은 대략 5초 Python이 초당 2000만번의 연산만 가능하다고 가정하는 것이 좋음 5초에 1억번 🦄 시간제한에 따른 알고리즘 설계 N의 max빅오 500 (5백) O(N³) 2,000 (2천) O(N²) 100,000 (10만) O(NlogN) 10,000,000 (천만) O(N) https://velog.io/@jehjong/Python-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9A%94%EA%B5%AC%EC%82%AC%ED%95%AD-%EB%B6%84%EC%84%9D-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84 [Python] 알고리즘 요구사항 분석 (시간 복잡도) 참고동빈나 이코테시간..