본문 바로가기
728x90

코딩/이코테-파이썬32

다이나믹 프로그래밍: 1로 만들기 숫자 x를 입력받는다. x가 5로 나누어 떨어지는 경우 5로 나눌 수 있고, 3으로 나누어 떨어지는 경우 3으로 나눌 수 있고, 2로 나누어 떨어지는 경우 2로 나눌 수 있으며, 그냥 -1을 할 수도 있다. 이 네가지 연산을 사용하여 x를 1로만드는 최소 연산 횟수를 구하라. 처음에는 x에서 5로 나눌 수 있으면 5로 나누고, 3으로 나눌수 있으면 3으로 나누고..하는식으로 무조건 큰걸로 나눌 수 있으면 더 빨리 1이 나올거라 생각했는데, 그건 아니었다 x=int(input()) #숫자입력 d=[0]*30001 #d[n]은 숫자n이 1이 될 때까지의 연산 횟수를 저장함 #bottom up for i in range(2,x+1): d[i]=d[i-1]+1 #i에서 (-1)연산 한번만 하면 i-1이 되므로,.. 2022. 7. 19.
다이나믹 프로그래밍: 개미 전사 리스트에 값이 들어있는데, 몇 개의 칸을 선택해서 선택한 칸들의 값의 합을 최대로 만들어야한다. 조건: 칸을 선택할 때 인접한 칸을 선택할 수 없다 x=int(input()) k=list(map(int,input().split())) d=[0]*3001 d[0]=k[1] #1번창고까지의 최대 식량 d[1]=max(k[1],k[2]) #2번창고까지의 최대 식량 for i in range(2,x): d[i]=max(d[i-1],d[i-2]+k[i]) #이전것까지의 식량 vs 전전것+이번것까지 식량 print(d[x-1]) 식량창고의 개수가 x 각 식량창고에 있는 식량의 크기를 저장할 리스트 k=[] n번째 식량창고까지 있다고 가정했을 때 최대로 훔칠 수 있는 식량의 양=d[n] d[i]= max(d[n-1].. 2022. 7. 19.
다이나믹 프로그래밍 이미 계산된 결과(작은 문제)는 별도의 메모리 공간에 저장해 둠으로써 중복 연산을 줄여 수행시간을 줄일 수 있다 다이나믹 프로그래밍을 사용할 수 있는 조건 1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야 함 다이나믹 프로그래밍 방식으로는 1. 탑다운(메모이제이션) 2. 보텀업 두가지가 있다. 탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이고, 보텀업 방식은 단순히 반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식이다. 탑다운 방식은 보통 재귀함수를 이용하는데, 재귀함수 깊이 제한 때문에 문제가 생길 수 있으므로 보텀업 방식을 권장한다. 고한다... 2022. 7. 19.
이진 탐색: 떡볶이 떡 만들기 떡을 자르기 위해 칼날의 높이를 설정해야 한다. 길이가 일정하지 않은 여러개의 떡이 있는데, 떡이 칼날 높이보다 높으면 잘린 만큼 떡을 가져갈 것이고 떡이 칼날 높이보다 낮으면 잘리지 않는다. 떡의개수n,필요한 떡의 총 길이m을 첫 줄에 입력받고 두번째 줄에서 떡의 개별 높이를 한 줄에 입력받는다. m만큼의 떡을 얻기 위해 최대한으로 높일 수 있는 칼날의 높이를 구하라. n,m=map(int,input().split()) #떡의개수n, 용청한 떡의길이m h=list(map(int,input().split())) #개별떡의길이 k=max(h)-1 #절단기 높이 초기값 for kal in range(k,0,-1): sum=0 for teok in h: if teok>kal: sum+=teok-kal if s.. 2022. 7. 18.
정렬 알고리즘: 이진 탐색 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색: 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. (시작점, 끝점, 중간점 이용함) n, target = list(map(int,input().split())) #데이터개수와 찾을 값 array = list(map(int,input().split())) def binary_search(array, target, start, end): if start> end: return None mid = (start + end) // 2 #중간점 인덱스 if array[mid] == target: #타깃을 찾은 경우 return mid elif array[mid] > target:.. 2022. 7. 17.
정렬 알고리즘: 계수정렬 계수정렬.. 조건만 잘 맞으면 퀵정렬보다 빠른.. 그런 정렬.. 시간복잡도가 O(N+K)라고한다. N은 숫자개수 K는 최대숫자 근데 이게.. 숫자들이 일단 정수여야함 그리고 배열을 하나 더 만들기 때문에 공간복잡도가 높음. 어떻게하냐면.. 배열을 쭉 돌면서 어떤 숫자가 몇번 나왔는지를 다 카운트함 그러고나서 그냥 0부터 시작해서~최대값까지 각 숫자를 카운트만큼 출력해주면됨 array = [7,5,9,0,3,1,6,2,9,1,4,8,0,6,2] count=[0]*(max(array)+1) for i in range(len(array)): count[array[i]]+=1 #각 숫자가 나오는 횟수를 셈.. for i in range(len(count)): for j in range(count[i]): pri.. 2022. 7. 15.
정렬 알고리즘: 퀵 정렬 배열이 있을 때.. 1. 배열의 맨 앞에 있는 수를 pivot으로 설정한다 (피벗은 다른 수로 선택할 수도 있다는데 일단 난 맨 앞에걸로 하겠음) 2. 배열의 두 번째 수부터 오른쪽으로 진행하면서 pivot보다 큰 수를 찾는다 => 여기서 찾은 수의 인덱스를 left라고 하겠음 3. 배열의 끝부터 왼쪽으로 진행하면서 pivot보다 작은 수를 찾는다. => 여기서 찾은 수의 인덱스를 right라고 하겠음 4. 찾은 left와 right인덱스의 값을 서로 바꿈.. 근데~ 만약에 left가 right보다 오른쪽에있다?? 그러면 작은수랑 피벗이랑 바꿈.. 5. 이렇게되면 피벗을 기준으로 왼쪽엔 피벗보다 작은값, 오른쪽엔 피벗보다 큰값으로 대충 정리가 됨.. 그니까 피벗 기준으로 앞부분, 뒷부분을 또 퀵소트를 돌.. 2022. 7. 15.
정렬 알고리즘: 선택정렬 가장 작은 수를 찾아서 맨 앞이랑 바꾸고.. 그다음 또 작은수를 찾아서 맨앞으로 바꾸고... ' array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_idx=i for j in range(i+1,len(array)): if array[min_idx]>array[j]: min_idx=j array[i],array[min_idx]=array[min_idx],array[i] print(array) i번째 값과 i+1 ~ 끝까지의 범위 중 가장작은 값을 골라 i번째 값과 가장작은 값을 스왑 함 2022. 7. 15.
BFS - 미로 찾기 이코테 p.152 - 미로찾기 N x M 크기의 미로가 있다. (1,1)에서 (N,M)으로 가기위한 최소 이동 칸 수를 구하라. 괴물(0), 길(1) BFS를 이용하고.. 방문한 노드는 (이전 노드값+1)을 해서 방문표시를 한다. (N,M)위치의 노드 값을 읽으면 최소 발자취 수가 나온다. from collections import deque dx=[1,-1,0,0] dy=[0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y))#현재 노드 방문처리 while(queue): x, y= queue.popleft() #큐에서 좌표를 꺼냄 for i in range(4):#상하좌우 네방향 확인 nx=x+dx[i] ny=y+dy[i] if nx=N or ny=M.. 2022. 7. 13.
DFS - 음료수 얼려 먹기 이코테 p.149 N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 있는 부분은 1로 표시된다. 구멍이 뚫린 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로길이 M이 주어진다 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다 이때 구멍이 뚫린 부분은 0, 그렇지 않은 부분은 1이다 출력 조건 한 번에 만들 수 있는 아이스크림의 개수를 출력한다 기록 1. 상하좌우로 탐색하는 dfs함수 구현 2. 각 칸에 대하여 dfs를 수행하고, 그 칸이 방문하지 않은 곳이면 result값을 1 증가시킴 3.. 2022. 7. 13.
탐색 알고리즘 - BFS from collections import deque #BFS메서드 정의 def bfs(graph,start,visited): #큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) #시작 노드를 큐에 넣음 visited[start]=True #현재 노드 방문처리 #큐가 빌 때까지 반복 while queue: #큐에서 원소를 하나 뽑아 출력 v= queue.popleft() print(v,end=' ') for i in graph[v]: #뽑은 원소의 주변 노드 if not visited[i]:#방문하지 않았으면 queue.append(i) #큐에 삽입 visited[i]=True #삽입한 노드는 방문처리 #각 노드가 연결된 정보를 2차원 리스트로 표현 graph=[ [],.. 2022. 7. 12.
탐색 알고리즘 - DFS DFS (Depth-First Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. def dfs(graph, v, visited): visited[v] = True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드가 연결된 정보를 2차원 리스트로 표현 graph=[ [],#1번 [2,3,8], [1,7,], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #각 노드의 방문이력을 저장할 1차원리스트 visited=[False]*9 dfs(graph,1,visited) def dfs(graph, v, visited): visited[v] = T.. 2022. 7. 12.
728x90

티스토리툴바