20200306 알고리즘
1. 증가수열 만들기
1부터 N까지의 자연수로 구성된 길이 N의 수열이 주어집니다. 이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열 을 만듭니다. 예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다. 맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4, 왼쪽끝에서5를가져와 2345증가수열을만들수있습니다.
▣ 입력설명 첫째 줄에 자연수 N(3<=N<=100)이 주어집니다. 두 번째 줄에 N개로 구성된 수열이 주어집니다.
▣ 출력설명 첫째 줄에 최대 증가수열의 길이를 출력합니다. 두 번째 줄에 가져간 순서대로 왼쪽 끝에서 가져갔으면 ‘L’, 오른쪽 끝에서 가져갔으면 ’R’를 써 간 문자열을 출력합니다.(단 마지막에 남은 값은 왼쪽 끝으로 생각합니다.)
▣ 입력예제 1
5 2 4 5 1 3
▣ 출력예제 1
4 LRLL
Solution1
import sys
sys.stdin = open("input30.txt", "rt")
n = int(input())
a = list(map(int, input().split()))
res = ''
lt = 0
rt = n-1
last = 0
tmp = []
while lt <= rt:
if a[lt] > last:
tmp.append((a[lt], 'L'))
if a[rt] > last:
tmp.append((a[rt], 'R'))
tmp.sort()
if len(tmp) == 0:
break
else:
if tmp[0][1] == 'L':
lt += 1
res += 'L'
last = tmp[0][0]
else:
rt -= 1
res += 'R'
last = tmp[0][0]
tmp.clear()
print(len(res))
print(res)Solution2
import sys
sys.stdin = open("input30.txt", "rt")
n = int(input())
a = list(map(int, input().split()))
char = ''
lt = 0
rt = n-1
last = 0
while last < a[lt] or last < a[rt]:
if len(char) == n-1:
char += 'L'
break
if last < a[lt] and last < a[rt]:
if a[lt] > a[rt]:
last = a[rt]
rt -= 1
char += 'R'
elif a[rt] > a[lt]:
last = a[lt]
lt += 1
char += 'L'
else:
if a[rt] > last:
last = a[rt]
rt -= 1
char += 'R'
elif a[lt] > last:
last = a[lt]
lt += 1
char += 'L'
print(len(char))
print(char)2. 역수열
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 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출 력하는 프로그램을 작성하세요.
▣ 입력설명 첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 역수열이 숫자 사이에 한
칸의 공백을 두고 주어진다.
▣ 출력설명
원래 수열을 출력합니다.
▣ 입력예제 1
8
5 3 4 0 2 1 1 0▣ 출력예제 1
4 8 6 2 5 1 3 7
Solution ( n 부터 푸는 방법 )
import sys
sys.stdin = open("input31.txt", "rt")
n = int(input())
a = list(map(int, input().split()))
res = []
for v in a[::-1]:
res.insert(v, n)
n -= 1Solution ( 1 부터 푸는 방법 )
import sys
sys.stdin = open("input31.txt", "rt")
n = int(input())
a = list(map(int, input().split()))
res = [0] * n
for i in range(n):
for j in range(n):
if a[i] == 0 and res[j] == 0:
res[j] = i+1
break
elif res[j] == 0:
print(res)
a[i] -= 1
print(res)3. 가장 큰 수
선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하 여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는 유지해야 합니다) 만약 5276823 이 주어지고 3개의 자릿수를 제거한다면
7823이 가장 큰 숫자가 됩니다
▣ 입력설명 첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다.
▣ 출력설명 가장 큰 수를 출력합니다.
▣ 입력예제 1
5276823 3
▣ 출력예제 1
7823
▣ 입력예제 2
9977252641 5
▣ 출력예제 2
99776
Solution
import sys
sys.stdin = open("input32.txt", "rt")
n, m = map(int, input().split())
numbers = list()
while n > 0:
numbers.insert(0, n % 10)
n //= 10
stack = list()
for a in numbers:
while stack and m > 0 and stack[-1] < a:
stack.pop()
m -= 1
stack.append(a)
if m != 0:
stack = stack[:-m]
print(stack)4. 쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에 서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레 이저의 배치는 다음 조건을 만족한다.
• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
- 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반 드시 레이저를 표현한다.
- 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
▣ 입력설명 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.
▣ 출력설명 잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
▣ 입력예제 1
()(((()())(())()))(())
▣ 출력예제 1
17
▣ 입력예제 2
(((()(()()))(())()))(()())
▣ 출력예제 2
24
Solution1
import sys
sys.stdin = open("input33.txt", "rt")
lasers = input()
stack = list()
res = 0
for i in range(len(lasers)):
if lasers[i] == '(':
stack.append(lasers[i])
else:
stack.pop()
if lasers[i-1] == '(':
res += len(stack)
else:
res += 1
print(res)Solution2
import sys
sys.stdin = open("input33.txt", "rt")
lasers = list(input())
stack = list()
cnt = 0
res = 0
for a in lasers:
if a == '(':
cnt += 1
else:
if stack[-1] == '(':
cnt -= 1
res += cnt
else:
cnt -= 1
res += 1
stack.append(a)
print(res)- 값을 참조 하는 경우에도 반복문에서 값 자체를 꺼내서 순회 하는것보다 index를 참조 하는편이 더 효율이 좋았었던 문제였다.
5. 후위표기식 만들기
중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요. 중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있 으면 중위표기식입니다. 후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식입니다. 예를 들어 중위표기식이 3+52 를 후위표기식으로 표현하면 352+ 로 표현됩니다. 만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)2 이면 35+2 로 바꾸어야 합니다.
※후위 표기식이 이해가 안되면 구글링으로 공부해보는 것도 좋습니다.
▣ 입력설명 첫 줄에 중위표기식이 주어진다. 길이는 100을 넘지 않는다. 식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.
▣ 출력설명 후위표기식을 출력한다.
▣ 입력예제 1
3+5*2/(7-2)▣ 출력예제 1
352*72-/+Solution
import sys
sys.stdin = open("input34.txt", "rt")
a = input()
stack = []
res = ''
for i in a:
if i.isdecimal():
res += i
else:
if i == '+' or i == '-':
while stack and stack[-1] != '(':
res += stack.pop()
stack.append(i)
elif i == '*' or i == '/':
while stack and (stack[-1] == '*' or stack[-1] == '/'):
res += stack.pop()
stack.append(i)
elif i == '(':
stack.append(i)
else:
while stack and stack[-1] != '(':
res += stack.pop()
stack.pop()
while stack:
res += stack.pop()
print(res)
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)