Leta Learns

문제 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 소수 판별만 하면 되는 문제였다. 입력 범위를 100까지로 착각해서 최솟값 구할 때 비교하는 초기값을 101로 설정했더니 계속 틀렸었다. 반례 찾으려고 게시판 돌아다니다가 문제를 다시 읽어봤는데 10000까지길래 10001로 수정했다. 문제를 잘 읽자 ! import sys input = sys.stdin.readline def is_prime(x): for i in range(2, x): if x %..

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net dp 규칙 찾느라 오래 걸렸다.. 0번째 행은 j+1랑 같은 수가 된다. dp를 만들 때 인덱스를 고려해서 맨 앞에 값을 하나씩 더 넣어줬으면 편리했을텐데 귀찮아서 안 했다. 이걸 해줬으면 아마 j+1이 아니라 j랑 같은 수가 될 것이다. i == j인 경우 다리 놓는 방법이 1가지이므로 해당 조건을 추가해주었다. 그 후부터는 dp[i][j] = dp[i][j-1] + dp[i-1][j-1]..

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 코드 풀이는 주석으로 적어놓았다. 모각코 시간에 풀었던 문제인데 감이 안 잡혀서 일단 무턱대고 풀었더니 말도 안 되는 코드가 나와서 구글링을 했다. 찾아보니 for - else문을 사용한 코드가 있길래 궁금해서 for-else문에 대해 조금 찾아보았다. for - else문은 for문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행된 경우 else문이 실행되는 구문이다..

문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 시간초과가 나서 다른 방법이 있는지 구글링했다. 중복 제거를 위해 set을 사용하고 그 후 딕셔너리를 사용하면 쉽게 풀리는 문제였다.. 딕셔너리 연습을 해야 하나.. import sys input = sys.stdin.readline n = int(input()) x = list(map(int, input().split())) x2 = sor..

문제 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 딕셔너리 value값 기준으로 정렬할 때 lambda를 사용해야 하는지 몰랐다. lambda 사용해서 정렬하면 튜플 형태로 바뀌기 때문에 유의해야 한다. 정렬 방법 모를 때는 웬만하면 lambda로 접근하면 된다고 생각해도 되려나. https://hello-bryan.tistory.com/78 [Python] Dictionary Sort (정렬) lambda Dictionary Sort Lambda 저번 ..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아 디피 어렵다!!!!!!! 어떻게 풀어야 하나 감이 안 잡혔는데 시간제한이 0.5초라서 이중 for문은 절대 쓰면 안 됐고,, 혹시 DP인가... 하면서 알고리즘 분류를 확인했더니 DP가 맞았다. 처음에 for문을 0번 인덱스부터 돌려서 좀 헤맸다. 1번 인덱스부터 돌리면 바로 전 집의 최솟값과 자신의 값을 더해서 값을 갱신해주면 된다. import sys input ..

문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net import sys input = sys.stdin.readline k = int(input()) num = [] for i in range(k): n = int(input()) if n == 0: del num[-1] else: num.append(n) print(sum(num))

문제 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net import sys input = sys.stdin.readline n, m = map(int, input().split()) pwinfo = {} for _ in range(n): site, pw = input().rstrip().split() pwinfo[site] = pw for _ in range(m): want = input().rstrip() prin..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 처음에 while문 하나 for문 하나를 사용해서 O(N^2) 으로 풀었다. 코드 짜면서 뭔가 무조건 시간초과 날 것 같다고 생각했는데 역시나... 이분탐색으로 다시 풀었다. 그런데 웃긴 점은.. 오늘 백준 자체가 느린 것인지..? 같은 코드로 제출했는데 한 번은 맞고 한 번은 시간초과가 난다. 혹시나 내가 틀린 걸까 싶어서 구글링 해보았는데 다른 사람..

문제 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 처음에는 전체적인 로직을 생각하지 않고 그냥 테스트케이스만 보고 풀었더니 틀렸다. 하나씩 비교해가면서 노가다하는 방법으로 풀었는데 한 번 틀리고 다시 생각해보니 왠지 조합 같아서 알고리즘 분류를 확인했다. -> 조합론 맞았음 그리고 나서 조합으로 어떻게 풀 지 생각해보는데 잘 떠오르지 않고 헷갈려서 ..