본문 바로가기

알고리즘90

Algorithm - 다이아몬드 모양의 합 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [다이아몬드 모양의 사과나무 합] 현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어져 있다. N의 크기는 항상 홀수이며, 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사과를 수확할 때 다이아몬드 모양의 격자판만을 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다. 만약 N이 5이면, 아래 그림과 같이 진한 부분의 사과를 수확한다. 현수가 수확하는 사과의 총 개수를 출력하는 프로그램을 작성하시오. *입력 설명 첫 줄에 자연수 N(홀수)이 주어진다. (3 ≤ N ≤ 20) 두 번째 줄부터 N줄에 걸쳐 각 줄에 .. 2021. 11. 17.
Algorithm - 격자판 최대합 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [격자판 최대합] 5*5 격자판에 아래와 같이 숫자가 적혀있습니다. N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가장 큰 합을 출력하는 프로그램을 작성하시오. *입력 설명 첫 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. (1 ≤ N < 100) *출력 설명 최대합을 출력합니다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_16.txt', 'rt') n = int(input()) a = [list(map(int, in.. 2021. 11. 17.
Algorithm - 수의 합 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [수의 합] N개의 수로 된 수열 A[1], A[2], ... , A[N]이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + A[i+2] + ... + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. *입력 설명 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], ..., A[N]이 공백으로 분리되어 주어지며, 각각의 A[x]는 30,000을 넘지 않는 자연수이다. *출력 설명 첫째 줄에 경우의 수를 출력한다. 풀이(Py.. 2021. 11. 7.
Algorithm - 두 리스트 합치기 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [두 리스트 합치기] 오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 첫 번째 리스트의 크기 N(1 ≤ N ≤ 100)이 주어진다. 두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어진다. 세 번째 줄에 두 번째 리스트의 크기 M(1 ≤ M ≤ 100)이 주어진다. 네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어진다. 각 리스트의 원소는 int형 변수의 크기를 넘지 않는다. *출력 설명 오름차순으로 정렬된 리스트를 출력한다. 풀이(Python) 답안 import sys s.. 2021. 11. 7.
Algorithm - 카드 역배치 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [카드 역배치] 1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓여 있다. 각 카드의 위치는 카드 위에 적힌 숫자와 같이 1부터 20까지로 나타낸다. 이제 다음과 같은 규칙으로 카드의 위치를 바꾼다. 구간 [a, b]가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다. (단, 1 ≤ a ≤ b ≤ 20) 예를 들어, 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [5, 10]으로 주어진다면 위치 5부터 위치 10까지의 카드 5, 6, 7, 8, 9, 10을 역순으로 하여 10, 9, 8, 7, 6,.. 2021. 11. 7.
Algorithm - 숫자만 추출 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [숫자만 추출] 문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만든다. 만들어진 자연수와 그 자연수의 약수 개수를 출력하는 프로그램을 작성하시오. 만약, 't0e0a1c2h0er' 에서 숫자만 추출하면 0, 0, 1, 2, 0이고 이것을 자연수를 만들면 120이 된다. 즉, 첫 자리 0은 자연수로 만들 때 무시한다. 이처럼 결과는 첫 줄에 120을 출력하고, 다음줄에 120의 약수의 개수를 출력하면 된다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않는다. *입력 설명 첫 번째 줄에는 숫자가 섞인 문자열이 주어.. 2021. 11. 7.