문제 정수 X가 주어질 때 사용할 수 있는 연산은 다음과 같이 4가지이다. 1. 5로 나누어떨어지면, 5로 나눈다. 2. 3으로 나누어떨어지면, 3으로 나눈다. 3. 2로 나누어떨어지면, 2로 나눈다. 4. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 이 때 연산을 사용하는 최소 횟수를 출력하시오. 입력 조건 1. 첫째 줄에 정수 X가 주어진다. 출력 조건 1. 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 내 코드 n = int(input()) d=[0]*(n+1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 ==..
다이나믹 프로그래밍 컴퓨터를 사용한 문제 해결에 있어서, 일반적으로 효율적인 설계라 함은 연산속도나 메모리 공간을 줄여나가는 것이다. 그러나 본 장에서 배울 다이나믹 프로그램과 같이, 조금의 메모리 공간을 더 할애하여 비약적인 성능을 끌어낼 수 있는 경우도 존재한다. 이를 동적 계획법이라고도 부르며, 프로그래밍에서 사용되는 동적 할당의 의미와는 다르다는 것을 인지할 필요가 있다. 다이나믹 프로그래밍의 대표적인 유형으로는 피보나치 수열이 존재한다. 이전 두 항의 합을 현재 항으로 설정하는 특징을 갖는 수열이다. 수학적인 표현으로 점화식을 사용하지만, 프로그래밍에서는 배열이나 리스트를 사용한다. 파이썬에서는 리스트를 사용한다. 이를 구현하기 위해서는 재귀 함수를 사용하면 된다. 재귀 함수를 이용한 피보나치 ..
문제 절단기에 높이를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 그렇게 높이보다 많이 잘린 떡을 손님이 가져간다. 손님이 길이가 M인 떡을 요청했을 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오 입력 조건 1. 첫째 줄에 떡의 개수 n과 떡의 길이 m이 주어진다. 2. 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 m 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 출력 조건 1. 적어도 m만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다. 내 코드 #1 탐색을 이용한 풀이 n,m = list(map(int,..
문제 동빈이네 전자 매장에는 부품이 N개 있다. 어느 날 손님이 M개 종류의 부품을 구매하기 위한 견적서를 요청하였다. 손님이 요구한 부품이 매장에 전부 있는지 확인하는 프로그램을 작성해보자. 입력 조건 1. 첫째 줄에 정수 n이 주어진다. 2. 둘째 줄에는 공백으로 구분하여 n개의 정수가 주어진다. (매장 내의 부품코드) 3. 셋째 줄에는 정수 m이 주어진다. 4. 넷째 줄에는 공백으로 구분하여 m개의 정수가 주어진다. (손님이 요구한 부품코드) 출력 조건 1. 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 Yes를, 없으면 No를 출력한다. 내 코드 n = int(input()) a = list(map(int,input().split())) m = int(input()) b = list(map(in..
순차탐색 앞서 공부한 알고리즘을 구현하는 과정에서도 굉장히 빈번하게 사용한 탐색 방법이며, 굉장히 단순하다. 리스트 내의 특정 값을 찾기 위해 맨 앞부터 차례대로 확인하는 방법이다. def sequential_search(n,target,array): for i in range(n): if array[i] == target: return i+1 print("생성할 원소 개수를 입력한 다음 한 칸을 띄고 찾을 문자열을 입력하세요") input_data = input().split() n = int(input_data[0]) target = input_data[1] print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.") array = input().split() p..
1. 위에서 아래로 문제 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오 입력 조건 1. 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1
선택정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 2중 반복문을 사용하기 때문에 O(N**2)의 시간복잡도를 갖고 다른 정렬 알고리즘에 비해 다소 비효율적이다. array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1,len(array)): if array[min_index] > array[j]: min_index = j array[i],array[min_index] = array[min_index],array[j] 삽입정렬 데이터를 하나씩 순회하며, 각 데이터를 적절한 위치에 삽입. 선택정렬에 비해 효..
문제 동빈이는 NxM 크기의 미로에 갇혀 있다. 동빈이의 위치는 (1,1)이고 출구는 (N,M)의 위치에 존재한다. 괴물이 있는 부분은 0으로, 이동 가능한 길은 1로 표시한다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오 입력 조건 1. 첫째 줄에 맵의 크기 N,M을 입력받는다. 2. 둘째 줄에 맵의 모양을 공백없이 입력받는다. 출력 조건 1. 동빈이가 탈출하기 위해 이동하는 블럭의 최소 개수를 출력한다. 내 코드 n,m = list(map(int,input().split())) mmap = [] for i in range(n): mmap.append(list(map(int,input()))) from collections import deque def maze(x,y): q..
문제 NxM 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 있는 부분을 1로 설정한다. 구멍이 뚫린 부분이 서로 붙어 있다면 큰 한 덩어리로 간주한다. 얼음 틀이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하라. 입력 조건 1. 첫 번째 줄에 얼음틀의 세로 길이 N과 가로 길이 M이 주어진다. 2. 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다. 출력 조건 1. 한 번에 만들 수 있는 아이스크림의 개수를 출력한다. 내 코드 # 맵 크기 입력받는다. n,m = map(int,input().split()) # 맵 모양 입력받는다. graph = [] for i in range(n): graph.append(list(map(int,input()))) def icy(x,y): if..
DFS와 BFS에 들어가기 전에 DFS, BFS 알고리즘은 코딩 테스트의 대표적인 탐색 문제 유형이다. 이를 제대로 이해하기 위해서는 스택과 큐에 대한 사전지식이 전제되어야 한다. 스택과 큐는 자료구조에서 핵심적인 개념으로, 삽입(Push)과 삭제(Pop)로 구성된다. 이 외에도 수용가능한 크기를 넘어서는 상태에서 데이터가 삽입되는 오버플로, 비어있는 데이터에 삭제연산을 수행하여 발생하는 언더플로 등을 고려해주어야 한다. 스택 박스쌓기로 비유하면 편하다. 가장 최근에 쌓은 박스가 가장 먼저 빠진다. (후입선출) 명령어는 빈 배열에서 삽입 시 append(), 삭제 시 pop()를 사용한다. 리스트의 가장 뒤 쪽에서 데이터를 삽입(순방향)하고, 가장 뒤 쪽에서 데이터를 꺼낸다. 큐 큐는 역방향으로 데이터를..
