[백준/Python] - 1018번 체스판 다시 칠하기
·
백준[파이썬]
https://www.acmicpc.net/problem/1018 📜제출코드 N, M = map(int, input().split())board = list()res = []for _ in range(N): board.append(input())# 0부터 N, M -7까지for i in range(N-7): for j in range(M-7): draw_1 = 0 draw_2 = 0 for a in range(i, i+8): for b in range(j, j+8): if (a + b) % 2 == 0: #하나의 짝수일때 시작점이 W와 B인 것을 모두 구할 수 있다. ..
[백준/Python] - 1929번 소수 구하기
·
백준[파이썬]
https://www.acmicpc.net/problem/1929📜제출코드 import sysimport mathinput = sys.stdin.readlineM, N = map(int, input().split())#1과 0은 무조건 True이기 때문prime = [True for _ in range(N+1)]prime[0], prime[1] = False, Falsefor i in range(2, int(math.sqrt(N))+1): if prime[i] == True: j = 2 while j * i N: prime[i*j] = False j += 1for i in range(M, N+1): if prime[i] == ..
[백준/Python] - 2485번 가로수
·
백준[파이썬]
https://www.acmicpc.net/problem/2485 📜제출코드 #최대 공약수를 활용해서 푸는 문제import sysinput = sys.stdin.readlineN = int(input())N_list = [int(input())]intervals = []# 유클리드 호제법def gcd(a,b): while b >0: a, b = b, a % b return afor _ in range(1,N): N_list.append(int(input())) intervals.append(N_list[_] - N_list[_-1])# 최대 공약수로 구하는 간격의 초기값을 입력해주고max_num = intervals[0]for i in range(1,len(interv..
[백준/Python] - 24511번 queuestack
·
백준[파이썬]
https://www.acmicpc.net/problem/24511 📜제출코드 from collections import dequeimport sysinput = sys.stdin.readlineN = int(input())A = list(map(int,input().split()))B = list(map(int,input().split()))M = int(input())C = list(map(int,input().split()))q = deque([])for i in range(N): # 큐인 자료구조만 모아주기기 if A[i] == 0: q.append(B[i])#오른쪽으로 갈 수록 나중에 들어온 값으로 처리했다.# ex) deque([1,4])# --> deque([2,1..
[백준/Python] - 1790번 수 이어 쓰기 2
·
백준[파이썬]
https://www.acmicpc.net/problem/1790 📜제출코드 N, K = map(int, input().split())#1의 자리와 숫자 개수 초기화digits, count, start_num = 1, 9, 1while K > digits * count: K -= (digits * count) digits += 1 count *= 10 start_num *= 10num = str(start_num + (K-1) // digits)if int(num) > N: print(-1)else: num_idx = (K-1) % digits print(num[num_idx]) 📜풀이단순한 수학적인 개념과 구현에 대한 개념이 있으면 풀 수 있는 문제이다. 📜..
[백준/Python] - 11399번 ATM
·
백준[파이썬]
https://www.acmicpc.net/problem/11399 제출코드N = int(input())N_list = list(map(int,input().split()))N_list.sort()ans = 0for i in range(N): temp = 0 for j in range(i+1): temp += N_list[j] ans += tempprint(ans) 풀이문제에서 가장 돈 인출하는데 걸리는 시간 가장 작게 걸리는 사람들부터 뽑으니까오름차순으로 정렬해준다. 각 순번마다 걸리는 시간을 구해줘야되니까 2중 for문으로 순번마다 걸리는 시간을 구해줬다.i번째가 걸리는 시간을 다음과 같이 정해주고temp에 걸리는 시간을 다 넣어준다.그리고 마지막에 ans에 누적저장 내가..
[백준/Python] - 24479번 알고리즘 수업 - 깊이 우선 탐색 1
·
백준[파이썬]
https://www.acmicpc.net/problem/24479✅제출코드import syssys.setrecursionlimit(int(1e6))input = sys.stdin.readlineN ,M, R = map(int,input().split())node = [[] for _ in range(N+1)]result = [0] * (N+1)visited = [0] *(N+1)for _ in range(M): u,v = map(int,input().split()) #무방향 그래프이기때문에 연결된 노드들은 해당 노드번호에 바꿔서 넣어준다 node[u].append(v) node[v].append(u)#인접정점은 오름차순으로 방문한다고 했으니 오름차순 정렬해준다.for i in ra..
[백준/Python] - 2556 별 찍기 10
·
백준[파이썬]
https://www.acmicpc.net/problem/2447 제출코드N = int(input())def recur(n): if n == 1: return ['*'] stars = recur(n // 3) arr = [] for i in stars: arr.append(i*3) for i in stars: arr.append(i + ' '*(n//3) + i) for i in stars: arr.append(i*3) return arrprint('\n'.join(recur(N))) 이런 문제는 어떻게 내고 어떻게 푸는거지? 진짜 신기하네...일단 안풀려서 블로그를 참고하면서 풀었다.전체적인 흐름도는 이렇다...
[백준/Python] - 11660 구간 합 구하기 5
·
백준[파이썬]
https://www.acmicpc.net/problem/11660 제출코드import sysinput = sys.stdin.readlineN , M = map(int,input().split())N_list = []dp = [[0] *(N+1) for _ in range(N+1)]for _ in range(N): N_list.append(list(map(int,input().split())))for i in range(1,N+1): for j in range(1,N+1): dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + N_list[i-1][j-1] # i = 1 j = 2 N_list[0][2] => 2for _ in range(M)..
[백준/Python] - 2559 수열
·
백준[파이썬]
https://www.acmicpc.net/problem/2559시간초과 코드import sysinput = sys.stdin.readlineN ,K = map(int, input().split())N_list = list(map(int, input().split()))ans = -1000000for i in range(N-K): if sum(N_list[i:i+K]) > ans: ans = sum(N_list[i:i+K])print(ans)그냥 무작정 N까지 돌면서 슬라이싱을 했다.이러면 당연히 N과 K의 단위가 커지면 O(N^2)에 수렴한다....※슬라이싱의 시간복잡도슬라이싱은 O(K)의 시간복잡도를 가진다. 슬라이싱의 길이에 비례하는 시간이 걸리므로 O(K)의 시간복잡도를 가지는 ..