본문 바로가기

분류 전체보기149

N과 M (1) - 15649 번 백트래킹 알고리즘의 기본문제이다. 재귀적으로 돌아가는 dfs 이며, 탐색이 끝나면 바로 전 단계로 돌아가는 형식을 취한다. n,m = map(int,input().split()) # 입력값들의 최대값이 8이므로 넉넉히 10칸으로 만들어줌 arr = [0]*10 is_used = [False]*10 # backtracking funtion def bt(idx): if idx == m: for i in range(m): print(arr[i],end=' ') print() return for i in range(1,n+1): if not is_used[i]: arr[idx] = i is_used[i] = True print('다음 bt', idx + 1) print(arr) print(is_used) bt(.. 2022. 10. 2.
ACM 호텔 - 10250 번 예제를 보며 패턴을 파악하여 코드를 짜면 된다. 반례 참고 : 1 6 12 59 답 : 510 import sys t = int(input()) for _ in range(t): h, w, n = map(int, sys.stdin.readline().split()) gh = 1 floor = 1 while True: if n = 10: print(f'{floor}{gh}') else: print(f'{floor}0{gh}') 2022. 10. 1.
이항 계수 1 - 11050번 combination 계산 방식을 구현해주었다. a, b = map(int, input().split()) s = 1 for i in range(1,b+1): s *= a s /= i a-=1 print(int(s)) 2022. 10. 1.
분해합 - 2231번 이론상 가능한 작은 최소 생성자부터 시작해서 1씩 증가시키면서 탐색하는 방식으로 문제를 해결했다. 특정 값들에서 오류가 발생하여 여러 반례를 찾아가면서 코드를 마무리 지었다. 반례 2 -> 1, 1 -> 0, 1000000 -> 0 ... n = int(input()) # 만약 n 이 3자리수라면 9 + 9 + 9 = 27 , # 9*3 보다 작은 수가 최소 생성자의 한계이다. # n 이 k자리수의 수면 k - 9*k 부터 1씩 증가시키면서 탐색 k = len(str(n)) # print(k, n - 9 * k) def ten_sum(n): # print(n) a = str(n) aa = 0 for i in a: aa += int(i) return aa + n if n - 9 * k > 0: for i .. 2022. 9. 30.
팰린드롬수 - 1259번 입력받을 수를 문자로 입력받아 뒤집어서 같은지 확인해준다. 문자열[::-1]을 하면 뒤에서부터 문자열 슬라이싱이 들어가 뒤집은 것과 같다. while True: n = input() if n == '0': break elif n == n[::-1]: print('yes') else: print('no') 2022. 9. 30.
RGB거리 2 - 17404번 RGB거리 - 1149번 위 문제와 비슷하지만 가장 마지막 집의 색이 가정 첫번째 집과는 달라야하는 다른점이 있다. 가장 첫번째 집이 선택됬는지 확인하면서 코드를 짤 필요가 있다. 각 색이 선택되었을 때 N번째 집까지 코드를 돌린 후, 선택한 색의 집을 뺀 나머지 두 집의 최소값을 저장한다. 그렇게 색 3가지를 모두돌린 후 각 색을 선택했을 때 나온 최소값 3개를 비교하여 가장 작은 수를 출력한다. 색을 선택하는 것을 코드화 할 때, 선택한 색을 제외한 나머지 색들은 1번 집에서 1001의 비용이 든다고 가정하면 무조건 선택이 되지 않을 것이다. N번째 집까지 코드가 돌아가면 선택한 색을 빼고 나머지 2개의 색만 비교하면 된다. 처음에 입력받은 house를 복사하는 과정에서 얕은 복사를 사용하여 예제가 .. 2022. 9. 29.
RGB거리 - 1149번 다이나믹프로그래밍으로 문제를 풀면 된다. 각 단계별로 전체 색에대한 최소값을 구하려다 실패하였다. 각 단계별로, 각 색에대해 최소값을 구한 뒤, 마지막에 최소값을 구해주면 문제를 해결할 수 있다. 예제 3 26 40 83 49 60 57 13 89 99 -> 26 40 83 89 86 83 96 172 185 최소값 : 96 import sys n = int(sys.stdin.readline()) house = [[] for i in range(n+1)] for i in range(n): house[i+1] = list(map(int, sys.stdin.readline().split())) cost = house.copy() for i in range(2,n+1): cost[i][0] += min(cos.. 2022. 9. 29.
바이러스 - 2606번 DFS 깊이우선탐색으로 문제를 해결하였다. 방문했던곳은 True로 표시를 하면서 진행하기 때문에 DFS가 끝나고 나면 True가 몇개인지 세주면 된다. import sys l = int(sys.stdin.readline()) c = int(sys.stdin.readline()) graph = [[] for i in range(l+1)] check = [False] * (l+1) # print(graph) for _ in range(c): a,b = map(int,sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) for i in graph: i.sort() def DFS(start): check[start] = True for i in.. 2022. 9. 28.
골드바흐의 추측 - 9020번 소수 범위 제한이 적으므로 먼저 아리스토테네스의 체를 만든다. n을 입력 받을 때 미리 만들어둔 아리스토테네스의 체를 이용해 문제에 만족하는 두 소수를 구한다. python3로 제출하면 9%에서 시간초과가 뜨는데, pypy3로 제출하면 4620ms로 성공한다. 좀더 시간을 줄여야 한다. import sys t = int(sys.stdin.readline()) prime = [] prime_bool_check = [True]*(10001) for i in range(2,int(10001**(1/2))): for j in range(i*i, 10001, i): prime_bool_check[j] = False for i in range(2, 10001): if prime_bool_check[i]: prime.. 2022. 9. 27.
알고리즘 수업 - 깊이 우선 탐색 2 - 24480번 알고리즘 수업 -깊이 우선 탐색 1과 비슷한 문제로 방문하는 정점을 내림차순으로 정렬해주면 된다. 정점을 정렬한 다음 reverse해주면 된다. 1. 방문하지 못하는 정점에 대해서 0으로 출력될 수 있도록 방문한 정점들을 리스트에 차례대로 추가해줘야한다. 2. 파이썬으로 재귀방법으로 풀 경우 런타임에러가 뜰 수 있다. 파이썬의 재귀 깊이는 1000으로 매우 얕은 편이기 때문에 재귀의 제한을 풀어줘야한다. sys.setrecursionlimit(10 ** 6) 으로 제한을 적절하게 풀어줘야한다. 3. for 문으로 입력받을 때, readline을 사용하여 런타임을 줄여준다. import sys sys.setrecursionlimit(10 ** 6) n, m, r = map(int, sys.stdin.rea.. 2022. 9. 26.
알고리즘 수업 - 깊이 우선 탐색 1 - 24479번 DFS를 해결해야하는 문제이다. 정점 개수, 간선 개수, 시작지점을 입력받고 그래프를 입력받는다. i 번째에는 정점 i 의 방문 순서를 출력하고, 방문하지 못하는 정점은 0을 출력해야한다. 1. 방문하지 못하는 정점에 대해서 0으로 출력될 수 있도록 방문한 정점들을 리스트에 차례대로 추가해줘야한다. 2. 파이썬으로 재귀방법으로 풀 경우 런타임에러가 뜰 수 있다. 파이썬의 재귀 깊이는 1000으로 매우 얕은 편이기 때문에 재귀의 제한을 풀어줘야한다. sys.setrecursionlimit(10 ** 6) 으로 제한을 적절하게 풀어줘야한다. 3. for 문으로 입력받을 때, readline을 사용하여 런타임을 줄여준다. import sys sys.setrecursionlimit(10 ** 6) n, m, r.. 2022. 9. 25.
약수 - 1037번 입력된 약수들을 정렬하고 가장작은수와 큰수를 곱해준다. 단, 입력된 약수가 1개라면 그 약수를 제곱한다. n = int(input()) a = list(map(int,input().split())) if len(a)==1: print(a[0]*a[0]) else: a.sort() print(a[0]*a[-1]) 2022. 9. 22.

티스토리툴바