728x90 반응형 Python3173 2022.02.26 [백준] (python 파이썬) 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 이 문제는 arr1, arr2에 모두 속하는 데이터를 뽑은 뒤 갯수를 출력하고, 사전순으로 데이터를 출력하면 된다. 처음 쉽게 생각하고 두개의 배열을 모두 리스트로 만들어 코드를 작성했지만 시간초과가 발생했다..... 그래서 시간 복잡도를 생각하던 중 set은 포함유무를 체크하는데 O(1)이라는 시간이 걸린다는 것이 생각났다!! 참고로 list는 포함유무를 체크하는데 O(N)이다... 그래.. 2022. 2. 26. 2022.02.26 [백준] (python 파이썬) 나는야 포켓몬 마스터 이다솜 문제 내용 생략....(문제를 푸는데 아무 쓸모 없는 긴 글...) 풀이 이 문제는 포켓몬의 이름과 번호를 저장하고 이름이 주어지면 번호를, 번호가 주어지면 이름을 출력해야한다. 번호는 이름이 입력된 순서이므로 처음엔 리스트에 인덱스0번째에 dump값을 넣고 채웠다. 이 후 이름이 주어지면 list.index로 번호를 출력했지만 시간복잡도가 O(N)이라 시간초과가 발생했다. 그래서 딕셔너리에 키 값을 이름:번호, 번호:이름 으로 저장하고 이름이든 번호든 딕셔너리 키값에 넣고 출력했다. sys.stdin.readline을 사용하면 문자열뒤에 \n이 붙어있기 때문에 rstrip을 해주어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys input=sys.stdin.readli.. 2022. 2. 26. 2022.02.25 [백준] (python 파이썬) 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 이 문제를 어떻게 풀어야 할까 고민했지만 전체를 확인하는 방법 말고는 생각이 나지 않았다. 그래서 모든 경우의 수를 체크했고 python3로 제출하니 시간초과,,,,, 여기서 시간복잡도를 줄일 방법이 생각이 나지않아 pypy3로 제출하니 통과했다...! 우선 최소시간을 저장할 변수를 지정했다. 변수 초기 값은 가장 오래걸리는 시간+1을 했다. 그리고 모든 높이를 확인하기 위해 0~256까지.. 2022. 2. 25. 2022.02.25 [백준] (python 파이썬) 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이 문제에서 필요한 나무를 가져가기 위한 절단기의 높이를 완전탐색으로 모두 확인하면 시간초과가 발생할 것이다. 그래서 이분탐색을 이용하여 코드를 작성했다. 우선 이분탐색을 할 범위를 정해줘야한다. 그래서 시작점을 0, 끝점을 입력받은 나무 중 가장 높은 나무로 설정했다. 그리고 binary_search함수를 만들어 이분탐색을 했다. while문에서 mi.. 2022. 2. 25. 이전 1 ··· 18 19 20 21 22 23 24 ··· 44 다음 728x90 반응형
