본문 바로가기

분류 전체보기

 (402)
[백준 9527번] 1의 개수 세기 (Python3) 조금 당황했던 문제 일단 알고리즘을 찾는거 자체가 조금 까다롭다. 내가 생각한 방법은 이진법으로 1,10,100,1000,10000 등의 수 일때의 일반항을 구하고, 그 이후에는 1은 계속 켜져있으므로, 차수만큼을 뺀 후 재귀함수를 불러오는 방식이다. 예를 들면 이진법으로 1010인 10의 경우, 이진법 1000은 8이므로 8일때의 일반항 값을 구하고, 10-8=2에서 2만큼을 더한 뒤, 2일때의 재귀함수를 불러온다. import sys input = sys.stdin.readline from collections import deque def binary(x): if x 0: dq.append(x1%2) x1 //= 2 C =..
[백준 1644번] 소수의 연속합 (Python3) 기본적인 알고리즘은 일단 에라토스테네스의 체 방식으로 소수 리스트를 구한 뒤 소수의 연속합을 구하면 된다. 처음에는 이중 for문을 이용해서 돌렸다. import sys input = sys.stdin.readline from collections import deque N = int(input()) DP = [True]*(N+1) DP[0] = DP[1] = False prime = deque() for i in range(1,N+1): if DP[i]: prime.append(i) c = 2 while True: if i*c > N: break DP[i*c] = False c+=1 cnt = 0 l = len(prime) for i in range(l): SUM = 0 No = i while True..
[백준 17404번] RGB거리 2 (Python3) import sys input = sys.stdin.readline from collections import deque INF = sys.maxsize N = int(input()) cost = [[]] for i in range(N): cost.append(list(map(int,input().split()))) sol = [[[0]*3 for i in range(N+1)] for i in range(3)] for i in range(3): for j in range(3): if i==j: sol[i][1][j] = cost[1][i] else: sol[i][1][j] = INF for case in range(3): s = sol[case] for i in range(2,N+1): s[i][0] =..
[백준 10942번] 팰린드롬? (Python3) import sys input = sys.stdin.readline N = int(input()) num = list(map(int,input().split())) M = int(input()) Q = [] for i in range(M): start,end = map(int,input().split()) Q.append((start-1,end-1)) palin = [1]*(2*N-1) for x,y in Q: answer = 1 center = x+y gap = y-x+1 if palin[center] >= gap: print(1) else: while True: if x>=y: palin[center] = gap print(1) break if num[x] != num[y]: print(0) brea..
[백준 2239번] 스도쿠 (Python3) import sys input = sys.stdin.readline sudoku = [] for i in range(9): sudoku.append(list(map(int,list(input().strip())))) def check(y,x,n): for i in range(9): if sudoku[y][i] == n or sudoku[i][x] == n: return False for i in range(3): for j in range(3): if sudoku[y-y%3+i][x-x%3+j] == n: return False return True finish = False def solsudoku(y,x): global finish if finish: return if x==9: solsudoku(y..
[백준 1987번] 알파벳 (Python3) import sys input = sys.stdin.readline R,C = map(int,input().split()) alpha = [] for i in range(R): alpha.append(input().strip()) dy = [1,-1,0,0] dx = [0,0,1,-1] check = [0]*26 check[ord(alpha[0][0])-65] = 1 result = 0 def go(y,x,num): global result result = max(result,num) for i in range(4): y1 = y+dy[i] x1 = x+dx[i] if R>y1>=0 and C>x1>=0: if check[ord(alpha[y1][x1])-65]==0: check[ord(alpha[y1]..
[백준 1806번] 부분합 (Python3) import sys input = sys.stdin.readline N,S = map(int,input().split()) seq = list(map(int,input().split())) SUM = [0]*(N+1) result = N+1 for i in range(1,N+1): SUM[i] = SUM[i-1]+seq[i-1] if SUM[i] >= S: for j in range(1,i+1): if j >= result: break if SUM[i]-SUM[i-j] >= S: result = min(result,j) break if result == N+1: print(0) else: print(result) 위 코드는 수열의 0~n까지의 합을 SUM 리스트에 저장하고, SUM 리스트의 차를 이용해서..
[백준 2467번] 용액 (Python3) import sys input = sys.stdin.readline import heapq N = int(input()) sol = list(map(int,input().split())) hq = [] for i in range(N): heapq.heappush(hq,(abs(sol[i]),sol[i])) SUM = sys.maxsize last = heapq.heappop(hq)[1] while hq: now = heapq.heappop(hq)[1] if abs(last+now) < SUM: SUM = abs(last+now) result = sorted([last,now]) last = now print(result[0],result[1]) 힙큐를 이용해서 구현하였다. 힙큐에 모든 데이터를 절댓값을 ..

티스토리툴바