Algorithm

문제) N가지 화폐 종류가 주어진다. 이 화폐들을 사용해서 M원을 만들어야 한다. 이 때 최소한의 화폐 개수를 사용해서 M원을 만들어야 하며 화폐 구성은 같지만 순서가 다른 경우에는 같은 경우로 구분한다. 입력조건) 첫째 줄에 N, M이 주어진다. (1

문제) 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 바닥을 타일로 모두 채워야 한다. 이 때 타일의 종류는 3가지 존재한다. 1 x 2 직사각형 타일 2 x 1 직사각형 타일 2 x 2 정사각형 타일 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 입력조건) 첫째 줄에 N이 주어진다. (1 2 x 1 타일로 덮는 경우 1가지 i-2까지 타일이 채워져 있는 경우 => 가로로 두칸을 채우면 된다. => 1 x 2 타일로 덮는 경우 + 2 x 2 타일로 덮는 경우, 즉 2가지 따라서 결과 리스트의 현재 인덱스 i 에는 결과 리스트[i-1] + 결과 리스트[i-2] * 2 를 저장하고 결과 리스트의 N번째 인덱스에 해당하는 값을 출력하면 원하는 출력 결과를 얻을 수 있을 것이다.

문제) N개의 식량 창고에 대한 정보를 입력받는다. 이 때 입력받은 순서대로 식량 창고가 인접해 있다고 생각한다. 개미 전사는 일직선 상에 존재하는 식량 창고 중에서 서로 인접하지 않은, 즉 최소한 한 칸 이상 떨어진 식량 창고들을 약탈할 수 있다. 이 때 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오. 입력조건) 첫째 줄에 식량창고의 개수 N이 주어진다. (3 결과 리스트[i-2] + 입력 리스트[i] 위의 두 가지 경우의 최댓값을 결과 리스트의 현재 리스트에 저장하면서 결과 리스트를 채워 나가면 문제를 해결할 수 있다. 최종적으로 입력받은 N 번째 인덱스의 값이 원하는 문제의 답이 된다.

문제) 정수 X가 주어질 때, 다음 4가지 연산을 통해서 X를 1로 만들어야 한다. X가 5로 나누어떨어지면, 5로 나눈다. X가 3으로 나누어떨어지면, 3으로 나눈다. X가 2로 나누어떨어지면, 2로 나눈다. X에서 1을 뺀다. 이때, 주어진 연산을 통해서 X를 1로 만드는 가장 최소 연산 횟수를 출력하시오. 입력조건) 첫째 줄에 정수 X가 주어진다. (1

코딩테스트에서는 각 문제 당 메모리와 시간이 제한되어 있다. 비교적 적은 입력이나 짧은 알고리즘에서는 이러한 제한이 큰 장애가 되지는 않는다. 그러나 입력이 많은 문제 (예를 들어 10억개의 입력 등) 거나 재귀적인 알고리즘에서는 메모리 혹은 시간 제한에 걸리게 된다. 따라서 우리는 최대한 연산 속도와 메모리 공간을 효율적으로 활용하는 알고리즘을 구현해야 한다. 몇몇 문제에서는 메모리 공간을 조금 더 사용할 수록 비약적으로 연산속도를 줄일 수 있는 경우가 존재한다. 이는 뒤에서 설명할 다이나믹 프로그래밍 기법을 사용하는 경우이다. 다이나믹 프로그래밍이란 동적 계획법이라고도 표현하며 2가지 방식이 존재한다. 이는 아래와 같다. 탑다운 방식 바텀업 방식 먼저 다이나믹 프로그래밍의 기본적인 아이디어는 다음과 ..

문제) 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이 (H) 를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M..

문제) 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이 때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다. 입력 조건) 첫째 ..

이진 탐색이란 데이터가 모두 정렬된 상태에서 탐색 범위를 절반씩 쪼개면서 탐색을 진행하는 알고리즘이다. 즉, 이진 탐색은 중간지점 (이하 중간점) 의 데이터를 찾고자 하는 데이터와 비교하여 탐색 범위를 좁힌다는 특징을 갖고 있다. 여기서 중간점 = (시작점 + 끝점) // 2 의 식으로 구하게 되며, 이때 // 는 버림 나눗셈 연산자로 나눗셈을 진행하고 몫의 정수 부분만 취하는 파이썬 연산자이다. 이진 탐색을 진행하는 과정을 살펴보자. 0 1 2 3 4 5 6 7 8 9 위와 같이 오름차순 정렬되어 있는 데이터가 있다고 가정하자. 여기서 우리는 3이라는 데이터가 어디에 위치해있는지를 탐색하고 싶다. 가장 먼저 시작점 = 0, 끝점 = 리스트의 마지막 인덱스 로 초기화 한다. 중간점 = (시작점 + 끝점)..