본문 바로가기

백준99

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.
수 정렬하기 3 - 10989번 수를 효율적으로 정렬하는 방법을 강구해야하는 문제이다. 먼저 for문에서 input을 넣어서 사용하면 느리기 때문에 sys모듈의 readline을 이용해주었다. 그냥 sort를 써주면 메모리 초과가 발생하기 때문에 문제에서 주어진 숫자의 범위제한을 이용해준다. 10000이하의 수들만 입력받아 정렬해줘야 하므로, 적절한 크기의 배열을 만들어두고 입력받은 수를 index로 하여 배열에 1을 더해준다. 입력이 끝나면 배열을 검사하여 2중for문을 이용해 배열의 값이 0이 아닐 때만 출력해준다. import sys n = int(sys.stdin.readline()) a = [0]*(10001) for i in range(n): a[int(sys.stdin.readline())] += 1 for i in ran.. 2022. 9. 21.
계단 오르기 - 2579번 점화식을 이용해야하는 다이나믹프로그래밍 문제이다. 그리디처럼 보이는 최대값, 최소값 등을 찾는데 동적 프로그래밍(다이나믹프로그래밍을 이렇게 부르기도 한다)을 사용하기도 한다. 문제에 제시된 규칙을 지키며 최대값을 구해야 한다. 첫번째 계단부터 하나씩 올라가면서 각 계단에서의 최대값을 구해보도록 나눠서 생각했다. 이문제에서 특히 고려해야할 점은 3계단을 연속으로 올라갈 수 없는 규칙이다. 변수('cant_go')를 하나 만들어서 계단을 올라가면 1을 더해주고 연속된 계단을 올라갈때 누적으로 1을 계속 더해준다. 변수의 값이 3이 됬을 때 계단을 3칸 연속으로 오른 경우가 되므로 한칸밑에 있는 계단을 스킵할 지, 2칸 밑에있는 계단을 스킵할지 정해줘야한다. 각 경우의 점수중 큰수를 해당 계단에서의 획득할 수.. 2022. 9. 20.
A와 B - 12904번 s와 t를 입력받아서 s를 t로 바꿀 수 있는지 알아보는 문제이지만 반대로 뒤집어서 t를 s로 바꿀 수 있는지를 확인해보면 간단하게 해결할 수 있다. 끝에 A를 추가하는 것은 끝이 A이면 끝에있는 A를 삭제해준다. 뒤집고 B를 추가해주는 것은 끝이 B이면 끝에있는 B를 삭제해주고 뒤집어준다. import sys s = sys.stdin.readline().strip() t = sys.stdin.readline().strip() while True: if t[-1]=='A': t = t[:-1] elif t[-1]=='B': t = t[:-1] t = t[::-1] if len(s) >= len(t): if s==t: print(1) else: print(0) break 2022. 9. 19.
스택 - 10828번 파이썬의 모듈인 데큐를 쓰든 안쓰든 값을 input받을 때, readline을 쓰지 않으면 시간초과가 뜬다. input받는 명령들은 단순하게 조건문을 사용해 처리해주었다. from collections import deque import sys dq = deque() n = int(sys.stdin.readline()) for _ in range(n): com = sys.stdin.readline() a = com[:3] if a == 'pus': dq.append(int(com[5:])) elif a == 'pop': try: print(dq.pop()) except: print(-1) elif a == 'siz': print(len(dq)) elif a == 'emp': if len(dq)>0: pr.. 2022. 9. 18.
숫자 카드 - 10815번 몇일 전에 풀었던 숫자카드 2와 같은 코드를 사용했다 마찬가지로 해시맵을 사용하면 시간초과가 안뜨는데 이분탐색을 사용하니 시간초과가 떴다. # 해시 맵을 사용하여 푼 코드, 이진탐색에 비해 더 간단한 느낌이 든다... n = int(input()) n_arr = list(map(int, input().split())) m = int(input()) m_arr = list(map(int, input().split())) result = [] dict = {} for i in n_arr: if i in dict: dict[i] +=1 else: dict[i] = 1 for i in m_arr: if i in dict: print(dict[i],end=' ') else: # 이진탐색을 이용하여 푼 코드, 시간.. 2022. 9. 17.
숫자 카드 2 - 10816번 이분탐색을 연습하고 싶어서 고른 문제이다. 하지만 이상하게도 이분탐색을 사용하여 풀면 시간초과가 뜬다. 따라서 key로 데이터를 접근하고 관리하는 map 을 사용하여 풀었다. 이진탐색트리는 O(log n)의 속도를 가지고, 해시 맵은 O(1)의 속도를 가진다. # 해시 맵을 사용하여 푼 코드, 이진탐색에 비해 더 간단한 느낌이 든다... n = int(input()) n_arr = list(map(int, input().split())) m = int(input()) m_arr = list(map(int, input().split())) result = [] dict = {} for i in n_arr: if i in dict: dict[i] +=1 else: dict[i] = 1 for i in m_a.. 2022. 9. 16.

티스토리툴바