백준

2024년 5월 6일 알고리즘 문제풀이 문제 별 찍기 - 10 난이도 골드 5 코드 길이가 3인 정사각형에서 가운데만 비어있는 형태로 반복하여 쌓이게 된다. 정사각형을 9등분하여 가운데에만 제외하고 8개를 복사해준다고 생각했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import sys n = int(sys.stdin.readline()) board = [[' ' for _ in range(n)] for _ in range(n)] # 재귀함수 정의 def main(num:int): # 사각형이 최소크기면 if num == 3: for i in range(3): for j in range(3): # 가운데(좌표 1,1)를 제외하고 *을 그려준다. if i != 1 or j != 1: board[i][j] = '*' return # 3등분하여 재귀를 반복 p = num//3 main(p) for i in range(0, num, p): for j in range(0, num, p): # 가운데가 아닐 때를 제외하곤 똑같은 모양을 넣어준다. if i != p or j != p: for x in range(p): board[i+x][j:j+p] = board[x][:p] # 함수 실행 main(n) # 결과 출력 for i in range(n): for j in range(n): print(board[i][j], end='') print() 출처 : TaxFree ...

2024년 4월 30일 알고리즘 문제풀이 문제 코코넛 그 두 번째 이야기 난이도 실버 5 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import sys def check(num: int): cnt = 1 for i in range(2,num): tmp = num for _ in range(i): tmp -= 1 tmp *= (i-1) if not tmp%i: tmp //= i else: break else: cnt = i return cnt while True: n = int(sys.stdin.readline()) if n == -1: break tmp = check(n) if tmp < 2: print(f"{n} coconuts, no solution") else: print(f"{n} coconuts, {tmp} people and 1 monkey") 문제에서 처리하는 순서대로 그대로 구현했다. 약간 헷갈렸던건, 예시에선 5명이였는데 인원수대로 처리하면 된다는 걸 생각못하고 무조건 5명이라 생각했다.. ...

2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 실버 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys k,n = map(int,sys.stdin.readline().split()) lan = [] for _ in range(k): lan.append(int(sys.stdin.readline())) low = 0 high = 2**31-1 while low <= high: mid = (low+high)//2 cnt = 0 for thing in lan: cnt += thing//mid if cnt >= n: low = mid+1 else: high = mid-1 print((high+low)//2) 생각보다 평범한 이진탐색문제였다. ...

2024년 4월 3일 알고리즘 문제풀이 문제 소수 경로 난이도 골드 4 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import sys from heapq import heappop, heappush def check(k:int): if not k%2: return False for i in range(3,int(k**(0.5))+1): if not k%i: return False else: return True prime_numbs = [ False for _ in range(10000)] for i in range(1000,10000): if check(i): prime_numbs[i] = True def change_num(arr: list): result = [] for i in range(10): for j in range(4): tmp = arr.copy() tmp[j] = str(i) if int("".join(tmp)) > 999 and prime_numbs[int("".join(tmp))] and tmp != arr: result.append(tmp) return result t = int(sys.stdin.readline()) for _ in range(t): answer = 'Impossible' a,b = map(int,sys.stdin.readline().split()) visited = [False for _ in range(10000)] visited[a] = True q = [] a_arr = list(str(a)) b_arr = list(str(b)) heappush(q,[0,a_arr]) while q: cnt, now = heappop(q) if now == b_arr: answer = cnt break change_arr = change_num(now) for num in change_arr: if not visited[int("".join(num))]: visited[int("".join(num))] = True heappush(q,[cnt+1, num]) print(answer) 매 번 소수 여부를 체크하지 않고, 1000부터 9999까지 소수 여부를 표시한 배열을 만들었다. change_num() 함수는 특정 수에서 1자리만 바꾼 수이다. 배열에 넣을 때, 몇 번 바뀌었는지를 함께 넣고 최소힙을 이용하여 최대한 적게 바꿀때를 찾을 수 있도록 했다. ...

2023년 9월 18일 알고리즘 문제풀이 문제 1 백준 1946 문제 링크 1차 시도 나의 생각 서류에서 1등을 한 사람의 면접 성적을 기준으로 삼았다. 이 기준보다 면접 성적이 높은 사람만 합격할 수 있다. 기준보다 면접 성적이 낮은 사람은 서류 성적도 당연히 낮다. 서류 1등의 성적을 기준으로 하였으니까.. 문제는 이 기준에서 설정한 사람들 내에서도 문제의 조건으로 탈락하는 사람이 생길 수 있다. 리스트를 2번 순회하였더니 시간초과가 나서 큐를 이용해 최소 힙을 구현하여 수행 시간을 줄였지만 오답처리 되었다. ...

2023년 9월 16일 알고리즘 문제풀이 문제 1 백준 1030 문제 링크 1차 시도 나의 생각 분할정복으로 풀면 되겠다고 생각했다. 정사각형 한 변의 길이는 1초마다 n이 곱해져 결국 s초 후 n의 s제곱 형태가 된다. s는 최대 10, n은 최대 8이므로 한 변의 길이는 최대 2의 30제곱이나 된다. 전체 정사각형 배치를 그린 후 원하는 부분만 출력하기엔 너무 크다는 뜻이다. 문제에서 출력하라고 요구하는 부분만 출력해야 한다. 이 부분이 너무 어려워서 다른 사람들의 풀이를 보고 공부한 코드이다. l은 위에서 말했던 n의 s제곱이자 s초 후 정사각형의 한 변의 길이이다. main 함수는 평면의 한 변의 길이와 검은색인지 확인할 곳의 행렬을 x,y로 받는다. 중앙의 k x k 크기의 사각형에 포함된다면 검은색이므로 1을 반환한다. ...

2023년 9월 15일 알고리즘 문제풀이 문제 1 백준 11047 문제 링크 1차 시도 나의 생각 최소한의 동전을 사용하기 위해선 최대한 가치가 큰 동전을 많이 사용해야 한다. 이를 위해 입력받은 동전을 큐에 저장해 최대 힙을 사용하였다. 가장 큰 동전부터 가능한 갯수만큼 사용했다. 기존에는 이중 반복문을 사용해서 가장 큰 동전을 여러번 쓰도록 구현했지만 시간초과가 문제가 되었다. 따라서 몫과 나머지를 이용해서 한번만 실행되도록 바꾸었더니 통과되었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys from heapq import heappush, heappop n, k = map(int, sys.stdin.readline().split()) coins = [] for _ in range(n): heappush(coins, -1*int(sys.stdin.readline())) cnt = 0 while k > 0 and coins: val = -1*coins[0] if k >= val: tmp = k//val cnt += tmp k %= val heappop(coins) print(cnt) 문제 2 백준 1541 문제 링크 ...

2023년 9월 9일 알고리즘 문제풀이 문제 1 백준 12865 문제 링크 1차 시도 나의 생각 입력값을 받을 때 무게 제한보다 무거운 물건은 아예 받지 않도록 조건을 추가한다. 큐를 이용한 최소힙을 통해 물건의 무게와 가치를 원소로 하는 배열에서 무게가 낮은 순서로 하나씩 pop한다. 배낭을 나타내는 배열에 [0,0]을 추가하여 아무것도 없는 상태를 만든다. pop할 때마다 기존 가방에 있는 것에 현재 물건을 더한 것을 추가해준다. 이 방식이면 원소갯수가 2배씩 늘어난다. 비어있는것 1개 => 첫번째 물건 더한것과 안더한것 2개 => 앞의 2개에 각각 두번째 물건을 더한것과 안더한 것 해서 총 4개 => 8개 => … ...

2023년 9월 8일 알고리즘 문제풀이 문제 1 백준 9273 문제 링크 1차 시도 나의 생각 결국 두 자연수 a,b에 대하여 1/n = 1/a + 1/b 가 성립해야 한다고 생각했다. 따라서 이 수식을 고쳐서 b = na/(a-n) 으로 만들었다. 이 함수를 a,b 에 대한 함수로 이해해보자. b-n = (n^2)/(a-n). 유리함수중에 분수 함수라고 할 수 있다. 점근선은 x =n, y = n이다. 아래와 같은 함수이다. 이 그래프에서 x,y가 모두 자연수인 함수 위 좌표를 찾았다. x가 0일 때 y가 n이다. x가 1이면 y는 자연수일 수 없다. 따라서 x가 2부터 1씩 증가하다가 y값이 음수면 멈췄다. ...

2023년 9월 7일 알고리즘 문제풀이 문제 1 백준 2748 문제 링크 1차 시도 나의 생각 기본적인 다이나믹 프로그래밍 문제였다. 재귀를 이용하면 시간초과가 되니 정의한 함수를 저장하는 배열을 만들어서 이를 참조하자. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n+1)] dp[1] = 1 def fibo(x): if x == 0: return dp[0] elif x == 1: return dp[1] else: if dp[x]: return dp[x] else: dp[x] = fibo(x-1) + fibo(x-2) return dp[x] print(fibo(n)) 문제 2 백준 1904 문제 링크 ...