자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1≤ A2≤ ... ≤ AK-1≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
dfs를 통해 풀었다
python코드
# 15652 N과 M (4)
def dfs(n):
if len(arr) == M:
print(*arr)
return
else:
for i in range(n,N+1):
arr.append(i)
dfs(i)
arr.pop()
N, M = map(int,input().split())
arr = []
dfs(1)
# 2407 조합
n, m = map(int,input().split())
num = 1
den = 1
n_m = 1
for i in range(1, n+1):
num *= i
for i in range(1, m+1):
den *= i
for i in range(1, (n-m)+1):
n_m *= i
print(num // (den * n_m))
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
무려 4중 for문을 사용해서 문제를 해결했다. 입력 값의 최대 값이 모두 50이하라서 통과지 조금만 더 컸다면 시간초과로 통과하지 못했을 효율적이지 않은 코드라고 생각한다.
일단 풀이는
진실을 알고 있는 사람을 list에 담아준다.
그리고 파티에 방문하여 그 파티에 사람들 중 진실을 알고 있는 사람이 있는지 검사한다.
만약 진실을 알고 있는 사람이 있다면 그 파티에 있는 모든 사람들을 진실을 알고 있는 리스트에 추가한다
해당 파티를 cnt 에 저장한다.
모든 파티를 돌고 나서 모든 파티의 개수(M) - 진실을 아는 사람이 있는 파티(cnt)의 갯수를 뺀다
이렇게 하면 문제가 발생한다!
예제 5번의 경우에 7번째 파티에 10번은 진실을 모르는 상태이기 때문에 지민이는 10번에게 과장된 말을 하고
이후에 8번째 파티에서 과장된 진실을 아는 10번과 진실을 아는 3번이 만나게 되는 것이다...!＼(º □ º l|l)/
그럼 꼼짝 없이 지민이는 거짓말쟁이가 되버린다.
이걸 해결하기 위해 해당 과정을 파티의 개수만큼 반복해줬다
그럼 cnt의 값이 어마무시하게 많아지는데 set()으로 중복을 제거하면 해결!
다른 사람들의 코드를 보고 더 효율적인 방법을 찾아야겠다.
python 코드
# 1043 거짓말
N, M = map(int,input().split())
know = list(map(int,input().split()))
knowNum = know[0]
know.pop(0)
party = []
cnt = []
for i in range(M):
p = list(map(int,input().split()))
p.pop(0)
party.append(p)
for a in range(M):
for i in range(M):
for j in range(len(know)):
if know[j] in party[i]:
cnt.append(i)
for k in party[i]:
if k not in know:
know.append(k)
break
cnt = set(cnt)
print(M - len(cnt))
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
dfs로 함수를 돌며 문제를 해결했다
1부터 채워넣기 위해 make(1)로 시작
그리고 n부터 N+1까지 돌았다. n 이 아닌 1부터 시작하면
[1, 2] [2, 1]과 같은 배열도 포함이 되어버린다.
그리고 [1, 1] [2, 2] 같이 중복이 되는 것도 피하기 위해서
if i not in arr로 중복을 피했다
python코드
# 15650 N과 M (2)
def make(n):
if len(arr) == M:
print(*arr)
return
for i in range(n, N + 1):
if i not in arr:
arr.append(i)
make(i)
arr.pop()
N, M = map(int,input().split())
arr = []
make(1)
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
풀이
[1, 2, 3, 4, 5, 6, 7] 순열이 있을 때
1. 6개의 숫자중 3번째 (arr[2])값을 지워준다
2. 6개의 숫자중에서는 6번째겠지만 3이 지워지면서 5개의 숫자중에는 5번째인 (arr[4])값을 지워준다
숫자가 1개씩 지워지기 때문에 K값 이후가 아닌 K-1값 이후의 숫자가 지워지는 규칙을 찾을 수 있었다
그리고 숫서대로 원을 그리고 있기 때문에 마지막 순번 다음은 첫번째 순번이다. 이것을 구현하기 위해서는
현재 순열의 갯수를 나눠서 나머지 값을 통해 값을 구할 수 있었다!
그리고 출력시 배열의 원소 사이에 ', '를 포함하기 위해 .join을 사용하였다
python코드
# 11866 요세푸스 문제 0
N, K = map(int,input().split())
arr = []
num = 0
ans = []
for i in range(N):
arr.append(i+1)
while(len(arr) > 0):
num = ((K - 1) + num) % len(arr)
ans.append(arr[num])
arr.pop(num)
print('<',end='')
print(', '.join(map(str,ans)),end='')
print('>')
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.
매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.
출력
첫째 줄에 최소 비교 횟수를 출력한다.
풀이
가장 효율적인 방법으로 카드를 비교하기 위해서는 가장 작은 숫자들을 더해나가야한다.
가장 작은 숫자들을 더하기 위해 처음에는 정렬을 통해 매번 가장 작은 숫자가 앞으로 오게 한 후
그 숫자들을 더해주는 방법을 생각했었지만, 실패
알고리즘 분류에 우선순위 큐가 있었고, 또 다른 코드들을 살펴보니 heapq를 사용한 풀이가 많아 찾아보았다
그래서 해당 문제처럼 언제나 가장 작은 값을 필요로 하는 경우 엄청 효율적으로 사용할 수 있을 것 같았다
a = heapq.heappop(arr)
b = heapq.heappop(arr)
로 그 순간 가장 작은 값을 pop하여 값을 더해주고, 더해진 값은 ans에 한번 더해지고 또 다른 연산을 위해 arr에 push된다.
arr에 들어간 값은 만약 가장 적은 값이라면 자동으로 arr의 0번 인덱스로 이동하게 되는 것이다...!
헉 너무 쉽게 풀이가 가능해서 놀랐다...! 이래서! 모듈을 사용하는구나!!!!!
python 코드
# 1715 카드 정렬하기
import heapq
n = int(input())
arr = []
for i in range(n):
heapq.heappush(arr, int(input()))
print(arr)
if n == 1:
print(0)
else:
ans = 0
while len(arr) > 1:
a = heapq.heappop(arr)
b = heapq.heappop(arr)
ans += a + b
heapq.heappush(arr, a + b)
print(ans)
그래서 3의 배수를 구한 후 받은 값에 '0'이 있는지 아닌지 판별하여 30의 배수인지 아닌지 구할 수 있었다.
python코드
# 10610 30
N = list(input())
hap = 0
for i in N:
hap += int(i)
if '0' in N:
if hap % 3 != 0:
print(-1)
else:
N.sort()
N.reverse()
for i in range(len(N)):
print(N[i],end='')
else:
print(-1)
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
풀이
단순히 숫자를 찾아서 풀면 시간 초과가 난다.
이분 탐색을 사용해서 풀이를 해야한다!
처음에는 파이썬 재귀 초과가 나길래 무슨 문제일까 고민 많이 했는데
binery함수로 재귀 이동할 때 return을 해주지 않으면 계산 후 다시 전 재귀 단계로 돌아오기 때문에,,, return을 필수로 작성해줘야했다.
이분탐색법은 미리 입력받은 배열을 정렬한 후 배열의 가운데 숫자와 비교숫자를 비교한 후
입력받은 숫자가 비교 숫자보다 큰 경우 시작점을 가운데 숫자 + 1로
적은경우 끝점을 가운데 숫자 - 1로 바꾸어 계속 비교한다
시간복잡도는 O(logN)으로 중간을 기준으로 탐색을 대상을 절반씩 줄여가서 빠른 편이다!
python코드
# 1920 수 찾기
import sys
def binery(i, start, end):
if start > end:
return 0
middle = (start+end)//2
if i == nArr[middle]:
return 1
elif(i < nArr[middle]):
return binery(i, start, middle - 1)
else:
return binery(i, middle + 1, end)
N = int(input())
nArr = list(map(int,sys.stdin.readline().split()))
nArr.sort()
M = int(input())
mArr = list(map(int,sys.stdin.readline().split()))
for i in mArr:
print(binery(i,0,N-1))
선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.
배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.
다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi≤ 100)
전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
풀이
예이예~!
시간 초과에 대한 풀이법 :
R이 입력되면 배열을 뒤집어 주어야 하고, D 가 입력되면 가장 앞에 있는 값을 없애준다. 여기서 R이 입력될때 마다 reverse를 해주면 시간 초과가 일어난다
R 이 짝수번 있다면 뒤집지 않은것과 같은 상태이기 때문에 R이 입력된 횟수를 카운팅 하며 R이 짝수번이라면 배열의 가장 앞의 값을, R이 홀수번이라면 배열의 가장 뒤의 값을 지우고 최종적으로 R이 홀수일때 배열을 뒤집어 주었다.
틀렸습니다에 대한 풀이법 :
맞왜틀의 연속
결국은 문제에 대한 이해도 부족이었다.
배열의 값이 비어있을 때 error를 반환해야한다고 생각했는데, 배열의 값이 비어있는데 D가 입력되는 경우에 error 반환이었다!
그 외에도 홀수 카운팅을 하면서 0으로 갱신하는 과정을 추가해서 풀었었는데 그것도 갱신할 필요 없이 카운팅을 연속으로 해주면 되는거였다!
입력 받기 :
입력 자체가 [1,2]이런 구성으로 들어왔기 때문에 입력받을때도 고민이 필요했다
slicing을 통해 가장 앞에 값'[' 과 ']'를 지워줬고, 중간에 ','는 split(',')로 없앴다
arr = input()[1:-1].split(',')
에서 시간초과를 방지하기 위해
sys.stdin.readline().rstrip()
로 바꿔주었다
.rstrip()을 사용하지 않고
arr = sys.stdin.readline()[1:-2].split(',')
로 진행해도 잘 풀리지만 .rstrip()을 사용하는게 더 가독성이 좋지 않을가...?
python 코드
# 5430 AC
import sys
T = int(sys.stdin.readline())
for tc in range(T):
p = sys.stdin.readline().rstrip()
n = int(sys.stdin.readline().rstrip())
arr = sys.stdin.readline().rstrip()[1:-1].split(',')
flag = 1
rCnt = 0
if n == 0:
arr = []
for pc in range(len(p)):
if p[pc] == "R":
rCnt += 1
if p[pc] == "D":
if len(arr) == 0:
flag = -1
break
if rCnt % 2 != 0:
arr.pop()
else:
arr.pop(0)
if pc == len(p)-1:
if rCnt % 2 != 0:
arr.reverse()
# print(arr)
if flag == -1:
print("error")
else:
print("[",end='')
print(','.join(arr),end='')
print("]")
2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
풀이
보자마자 아! 이건 람다 식으로 풀어야겠다! 하는 생각이 들었던 문제
y 좌표가 증가하는 순으로 정렬 후 y 좌표가 같다면 x 좌표 증가 순이지만 실제로 문제를 풀때는 미리 x 좌표를 정렬시켜둔 후 y 좌표 순으로 정렬을 했다.
문제를 푸는 방법에 도달하는 데에는 시간이 별로 걸리지 않았지만, 람다 식을 별로 써본 적이 없어 람다식 사용법 자체는 검색해봐야 했다ㅠ
그냥 input()을 사용하면 시간초과에 걸리는데 그건 sys.stdin.readline()으로 쉽게 해결 가능했다.
python 코드
# 11651 좌표 정렬하기 2
import sys
N = int(sys.stdin.readline())
arr = []
for tc in range(N):
arr.append(list(map(int,sys.stdin.readline().split())))
arr.sort(key=lambda x:(x[0]))
arr.sort(key=lambda x:(x[1]))
for i in range(N):
print(*arr[i])
