본문 바로가기

Algorithm

 (252)
[백준] 1149 : RGB거리 python 전체 비용이 최소가 되기 위해서 마지막집이 R일 때, G일 때, B일 때 모두를 계산하고 그중 최소인 것을 출력한다. 이때 i번째 집은 i-1번째 집과 다른 색이어야 한다는 조건이 있기 때문에 i번째 집이 R인 경우에는 i-1번째 집이 G거나 B여야 하고 i번째 집이 G인 경우에는 i-1번째 집이 R이거나 B여야 하고 i번째 집이 B인 경우에는 i-1번째 집이 R이거나 G여야 한다. n = int(input()) color = [0]*(n) for i in range(n): color[i] = list(map(int,input().split())) for i in range(1,n): color[i][0] += min(color[i-1][1],color[i-1][2]) color[i][1] += min(..
[백준] 24416 : 알고리즘 수업 - 피보나치 수 1 문제에서 말하는 대로 풀었는데 Python3으로 제출하니 시간초과가 나왔고, PyPy3로는 정답판정이 나왔다. n = int(input()) def recursive_fibo(x): global cnt_recursive if x==1 or x==2: cnt_recursive +=1 return 1 return recursive_fibo(x-1)+recursive_fibo(x-2) def dp_fibo(x): global cnt_dp dp = [1]*(x+1) for i in range(3,x+1): dp[i] = dp[i-1]+dp[i-2] cnt_dp += 1 cnt_recursive = 0 cnt_dp = 0 recursive_fibo(n) dp_fibo(n) print(cnt_recursive, c..
[다이나믹 프로그래밍] 피보나치 수열, 개미 전사, 1로 만들기, 효율적인 화폐 구성, 금광, 병사 배치하기 python 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 계산한 결과를 메모리에 저장해(Memoization) 다시 계산하는 일이 없게 함 구현 방식은 일반적으로 탑다운방식과 보텀업방식이 있음 탑다운방식-큰 문제를 잘게 쪼개어 푸는 것 보텀업방식-작은 문제들을 해결해 큰 문제를 해결하는 것 다이나믹 프로그래밍의 조건 주어진 문제가 다음의 조건들을 만족할 때 다이나믹 프로그래밍을 사용할 수 있음 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나누고 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복..
[백준] 16928 : 뱀과 사다리 게임 python 1. 사다리와 뱀을 만나면 무조건 이동한다. 2. 사다리와 뱀이 있는 칸은 여러 번 방문할 수도 있으니, 주사위 던진 횟수가 최소가 되게 신경써야 한다. 이 두 가지만 신경쓰면 크게 어렵지 않은 문제였다. from collections import deque import sys input = sys.stdin.readline def bfs(start): q = deque() # 시작점을 큐에 넣고 방문체크 q.append(start) visited[start] = True while q: # 현재 위치를 cur에 저장 cur = q.popleft() # 주사위를 굴려서 갈 수 있는 곳을 확인함 for i in range(1,7): ncur = cur+i # 100번 칸에 도달했다면 주사위 던진 횟수를+1..
[백준] 1012 : 유기농 배추 python 배추들이 상하좌우로 인접해있는 곳에는 배추흰지렁이가 한 마리만 있어도 되기 때문에 모든 배추들이 탐색완료가 될 때까지 BFS나 DFS를 수행하고 그 횟수를 세주면 되는 간단한 문제다. 평소엔 행을 x로 열을 y로 두고 푸는 경우가 많은데 이 문제에선 반대라서 그게 좀 헷갈렸다. from collections import deque import sys input = sys.stdin.readline def bfs(ay,bx): q = deque() q.append((ay,bx)) visited[ay][bx] = True while q: y,x = q.popleft() for i in range(4): ny = y+dy[i] nx = x+dx[i] if 0
[백준] 12015 : 가장 긴 증가하는 부분 수열 2 python https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12015-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%EA%B3%A8%EB%93%9C2-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89 위 포스트를 참고해서 문제를 풀었다. 우선 arr라는 리스트에 입력받은 값들을 저장한다. 그리고 res라는 리스트를 만들고 arr[0]를 저장한 뒤에, arr에 저장된 값과 res의 마지막값을 비교하며 더 클 경우에는 res에 추가하고 작거나 같을 경우에는 res안에서 적절한 ..
[백준] 2110 : 공유기 설치 python 이분탐색 문제들은 어떤 값을 이분탐색할 것인지 결정하는 게 가장 어려운 것 같다... 이 문제는 공유기 사이의 거리값으로 이분탐색을 해서 풀어야 하는 문제였다. # 집의 개수와 공유기의 개수를 입력받음 n,c= map(int,input().split()) # 집의 좌표들을 입력받고 정렬한 리스트 house를 생성 house = sorted([int(input()) for _ in range(n)]) # 공유기 사이의 거리값들을 이분탐색 하는 것이기 때문에 # 최소거리인 1과 최대거리인 house[-1]-house[0]을 start와 end로 지정함 start,end = 1, house[-1]-house[0] # 인접한 공유기의 거리의 최대값을 저장할 변수 answer = 0 # 이분탐색이 가능할 동안 반..
[백준] 10816 : 숫자 카드 2 python N개의 카드를 오름차순으로 정렬한 리스트 card에서 bisect라이브러리의 내장함수인 bisect_right와 bisect_left를 이용해서 각각의 숫자가 몇개씩 있는지 세고, 딕셔너리에 추가한 뒤 출력하는 방식을 생각했는데 자꾸 시간초과가 나왔다. bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 위치를 알려주고 bisect_left(list, value)는 왼쪽 위치를 알려줘서 정렬된 list에 사용하면 오른쪽위치-왼쪽위치=list내에서 그 숫자의 개수가 된다. 그런데 생각해보니 굳이 다시 저장하고 끄집어낼 필요가 없는 거다. 그래서 딕셔너리를 쓰지 않고 그냥 바로 출력해버리니까 정답판정을 받았다. import bisect n = int(input()) ..

티스토리툴바