본문 바로가기

알고리즘90

Algorithm - 랜선 자르기(결정 알고리즘) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [랜선 자르기] 엘리트 학원은 전체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 선생님은 K개의 랜선을 잘라서 N개의 동일한 길이를 가지는 랜선으로 만들고 싶어한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야한다. 참고로, 이미 자른 랜선은 다시 붙일 수 없다. 편의를 위해 랜선을 자를 때, 손실되는 길이는 없다고 가정하며 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정한다. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정한다. N개보다 많이.. 2021. 11. 19.
Algorithm - 이분 검색 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [이분 검색] 임의의 N개의 숫자가 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면, 이분 검색으로 M이 정렬된 상태에서 몇 번째에 있는지를 구하는 프로그램을 작성하시오. (단, 중복값은 존재x) *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 1,000,000)과 M이 주어진다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어진다. *출력 설명 첫 줄에 정렬 후 M값의 위치를 번호로 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_22.txt', '.. 2021. 11. 19.
Algorithm - 격자판 회문수 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [격자판 회문수] 1부터 9까지의 자연수로 채워진 7x7 격자판이 주어지면, 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성하시오. (회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 의미함) 단, 빨간색처럼 구부러진 경우(87178)는 회문수로 간주하지 않는다. *입력 설명 1부터 9까지의 자연수로 채워진 7x7 격자판이 주어진다. *출력 설명 5자리 회문수의 개수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_21.txt', 'rt.. 2021. 11. 19.
Algorithm - 스도쿠 검사 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [스도쿠 검사] 스도쿠는 매우 간단한 숫자 퍼즐이다. 9x9 크기의 보드가 있을 때, 각 행과 각 열 그리고 9개의 3x3 보드에 1부터 9까지 숫자를 중복 없이 채우면 된다. 위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오며, 각 3x3짜리 사각형(9개)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다. 완성된 9x9 크기의 스도쿠가 주어지면 정확하게 풀었으면 'YES', 잘 못풀었으면 'NO'를 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 완성된 9.. 2021. 11. 19.
Algorithm - 봉우리 찾기 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [봉우리 찾기] 지도의 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여있다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이며, 봉우리 지역이 몇 개 인지를 알아내는 프로그램을 작성하시오. 단, 격자의 가장자리는 0으로 초기화 되었다고 가정하며 만약 N=5이고 격자판의 숫자가 아래과 같다면 봉우리의 개수는 10개이다. *입력 설명 첫 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. (단, 각 자연수는 100을 넘지 않음) *출력 설명 봉우리의 개수를 구.. 2021. 11. 17.
Algorithm - 모래시계 모양의 합 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [모래시계 모양의 곳감 합] 현수는 곳감을 만들기 위해 감을 깍아 마당에 말리고 있다. 현수의 마당은 N*N 격자판으로 이루어져 있으며, 현수는 각 격자단위로 말리는 감의 수를 정한다. 그런데 해의 위치에 따라 특정 위치의 감은 잘 마르지 않기 때문에, 격자의 행을 기준으로 왼쪽 또는 오른쪽으로 회전시켜 위치를 변경해 모든 감이 잘 마르도록 해야한다. 만약, 회전명령 정보가 2 0 3이면 2번째 행을 왼쪽으로 3만큼 아래 그림처럼 회전시키라는 의미이다. 첫 번째 수는 행번호이고 두 번째 수는 방향이며 0이면 왼쪽, 1이면 오른쪽이다. 마지막으로 세 번째 수는 회전.. 2021. 11. 17.

티스토리툴바