본문 바로가기

알고리즘90

Algorithm - 후위 표기식 연산(스택) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [후위 표기식 연산] 후위 연산식이 주어지면, 연산한 결과를 출력하는 프로그램을 작성하시오. 예를 들어, 중위 연산식 3*(5+2)-9을 후위 연산식으로 표현하면 352+*9-이 되고 후위 연산식의 연산 결과는 12가 된다. *입력 설명 첫 번째 줄에 후위 연산식이 주어진다. (연산식의 길이는 50을 넘지 않음) 연산식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다. *출력 설명 연산한 결과를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_35.txt', 'rt') a = input(.. 2021. 12. 3.
Algorithm - 후위 표기식 만들기(스택) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [후위 표기식 만들기(스택)] 중위 표기식은 우리가 흔히 쓰는 표현식이다. 예를 들어, 3+5와 같이 연산자가 피연산자 사이에 있으면 중위 표기식이다. 후위 표기식은 35+와 같이 연산자가 피연산자 뒤에 있는 표기식이다. 즉, 중위 표기식 3+5*2를 후위 표기식으로 표현하면 352*+로 표현된다. 만약 다름과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)*2의 중요 표기식이 35+2*의 후위 표기식으로 바뀐다. 위의 예시를 참고하여 중위 표기식이 입력되면, 후위 표기식으로 변환하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 중위 표기식이 주어진다... 2021. 12. 3.
Algorithm - 쇠막대기 절단(스택) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [쇠막대기 절단(스택)] 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기를 자른다. 쇠막대기와 레이저의 배치는 다음조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 이상 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래의 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵.. 2021. 12. 3.
Algorithm - 가장 큰 수 찾기(스택) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [가장 큰 수 찾기(스택)] 선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했다. (단, 숫자의 순서는 유지해야 함) 만약, 5276823이 주어지면 3개의 자리수를 제거하여 7823이 가장 큰 숫자가 된다. 위의 조건을 모두 충족시키는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 숫자(길이는 1000을 넘지 않음)와 제거해야 할 자리수의 개수가 주어진다. *출력 설명 가장 큰 수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_32.txt.. 2021. 12. 2.
Algorithm - 역수열로 원수열 찾기(그리디) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [역수열로 원수열 찾기] 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라고 한다. 예를 들어, 다음과 같은 (원)수열의 경우를 고려해보자. 4 8 6 2 5 1 3 7 1 앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5로 5개이고, 2 앞에 놓인 2보다 큰 수는 4, 8, 6으로 3개이며, 3 앞에 놓인 3보다 큰 수는 4, 8, 6, 5로 4개이이다. ... 따라서, 4 8 6 2 5 1 3 7의 역수열은 5 3 4 0 2 1 1 0이 된다... 2021. 11. 22.
Algorithm - 증가수열 만들기(그리디) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [증가수열 만들기] 1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어진다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만든다. 이 때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거된다. 예를들어, 2 4 5 1 3이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4이다. 맨 처음 왼쪽 끝에서 2, 그 다음 오른쪽 끝에서 3, 그다음 맨 왼쪽 끝에서 4, 그다음 맨 왼쪽 끝에서 5를 가져와서 2 3 4 5의 증가수열을 만들 수 있다. *입력 설명 첫 번째 줄에 자연수.. 2021. 11. 22.

티스토리툴바